圖 - 圖的存儲結構 - 鄰接表表示法（二）

　　鄰接表的形式說明及其建表算法

　　()鄰接表的形式說明

　　typedef struct node{//邊表結點

　　int adjvex; //鄰接點域

　　struct node *next; //鏈域

　　//若要表示邊上的權則應增加一個數據域

　　}EdgeNode;

　　typedef struct vnode{ //頂點表結點

　　VertexType vertex; //頂點域

　　EdgeNode *firstedge;//邊表頭指針

　　}VertexNode;

　　typedef VertexNode AdjList[MaxVertexNum];//AdjList是鄰接表類型

　　typedef struct{

　　AdjList adjlist;//鄰接表

　　int ne; 圖中當前頂點數和邊數

　　}ALGraph; //對於簡單的應用無須定義此類型可直接使用AdjList類型

　　()建立無向圖的鄰接表算法

　　void CreateALGraPh(ALGrahp *G)

　　{//建立無向圖的鄰接表表示

　　int ijk;

　　EdgeNode *s;

　　scanf(%d%d&G>n&G>e); //讀人頂點數和邊數

　　for(i=;in;i++){//建立頂點表

　　G>adjlist[i]vertex=getchar(); //讀入頂點信息

　　G>adjlist[i]firstedge=NULL;//邊表置為空表

　　for(k=;ke;k++){//建立邊表

　　scanf(%d%d&i&j);讀入邊(v i v j )的頂點對序號

　　s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成邊表結點

　　s>adjvex=j; //鄰接點序號為j

　　s>next=G>adjlist[i]firstedge;

　　G>adjlist[i]firstedge=s; //將新結點*s插入頂點v i 的邊表頭部

　　s=(EdgeNode *)malloc(sizeof(EdgeNode));

　　s>adjvex=i; //鄰接點序號為i

　　s>next=G>adjlist[j]firstedge;

　　G>adjlistk[j]firstedge=s; //將新結點*s插入頂點v j 的邊表頭部

　　}//end for

　　}CreateALGraph

　　該算法的時間復雜度是O(n+e)

　　注意

　　① 建立有向圖的鄰接表更簡單每當讀人一個頂點對序號時僅需生成一個鄰接序號為j的邊表結點將其插入到v j 的

　　出邊表頭部即可

　　② 建立網絡的鄰接表時需在邊表的每個結點中增加一個存儲邊上權的數據域

　　圖的兩種存儲結構比較

　　鄰接矩陣和鄰接表是圖的兩種最常用的存儲結構它們各有所長下面從及執行某些常用操作的時間這兩方面來作一比較

　　

From:http://tw.wingwit.com/Article/program/sjjg/201311/23842.html