代碼如下:

/* 圖的鄰接表表示法 */#define MaxVertexNum 100 /* 最大頂點數設為100 */ typedef int Vertex; /* 用頂點下標表示頂點,為整型 */ typedef int WeightType; /* 邊的權值設為整型 */ typedef char DataType; /* 頂點存儲的數據類型設為字符型 *//* 邊的定義 */ typedef struct ENode *PtrToENode; struct ENode{Vertex V1, V2; /* 有向邊<V1, V2> */WeightType Weight; /* 權重 */ }; typedef PtrToENode Edge;/* 鄰接點的定義 */ typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{Vertex AdjV; /* 鄰接點下標 */WeightType Weight; /* 邊權重 */PtrToAdjVNode Next; /* 指向下一個鄰接點的指針 */ };/* 頂點表頭結點的定義 */ typedef struct Vnode{PtrToAdjVNode FirstEdge;/* 邊表頭指針 */DataType Data; /* 存頂點的數據 *//* 注意：很多情況下，頂點無數據，此時Data可以不用出現 */ } AdjList[MaxVertexNum]; /* AdjList是鄰接表類型 *//* 圖結點的定義 */ typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 頂點數 */int Ne; /* 邊數 */AdjList G; /* 鄰接表 */ }; typedef PtrToGNode LGraph; /* 以鄰接表方式存儲的圖類型 */LGraph CreateGraph( int VertexNum ) { /* 初始化一個有VertexNum個頂點但沒有邊的圖 */Vertex V;LGraph Graph;Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立圖 */Graph->Nv = VertexNum;Graph->Ne = 0;/* 初始化鄰接表頭指針 *//* 注意：這里默認頂點編號從0開始，到(Graph->Nv - 1) */for (V=0; V<Graph->Nv; V++)Graph->G[V].FirstEdge = NULL;return Graph; }void InsertEdge( LGraph Graph, Edge E ) {PtrToAdjVNode NewNode;/* 插入邊 <V1, V2> *//* 為V2建立新的鄰接點 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V2;NewNode->Weight = E->Weight;/* 將V2插入V1的表頭 */NewNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = NewNode;/* 若是無向圖，還要插入邊 <V2, V1> *//* 為V1建立新的鄰接點 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V1;NewNode->Weight = E->Weight;/* 將V1插入V2的表頭 */NewNode->Next = Graph->G[E->V2].FirstEdge;Graph->G[E->V2].FirstEdge = NewNode; }LGraph BuildGraph() {LGraph Graph;Edge E;Vertex V;int Nv, i;scanf("%d", &Nv); /* 讀入頂點個數 */Graph = CreateGraph(Nv); /* 初始化有Nv個頂點但沒有邊的圖 */ scanf("%d", &(Graph->Ne)); /* 讀入邊數 */if ( Graph->Ne != 0 ) { /* 如果有邊 */ E = (Edge)malloc( sizeof(struct ENode) ); /* 建立邊結點 */ /* 讀入邊，格式為"起點 終點 權重"，插入鄰接矩陣 */for (i=0; i<Graph->Ne; i++) {scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); /* 注意：如果權重不是整型，Weight的讀入格式要改 */InsertEdge( Graph, E );}} /* 如果頂點有數據的話，讀入數據 */for (V=0; V<Graph->Nv; V++) scanf(" %c", &(Graph->G[V].Data));return Graph; }

總結

以上是生活随笔為你收集整理的图的建立-邻接表表示(C语言)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。