Graph.h
Vnode結構成員firstarc在定義時賦初值NULL，在Visual Stdio 2013下編譯通過，VC6.0就不行(非靜態數據成員不能初始化)

#include <stdio.h> #include <stdlib.h>#define MAX_VERTEX_NUM 20typedef int InfoType, VertexType; //在這里可以設置頂點和弧數據類型 typedef struct ArcNode {int adjvex; //弧指向頂點的位置struct ArcNode *nextarc; //指向下一條弧的指針InfoType *info; //弧相關信息的指針 例如弧長、權重等，這里用不到 }ArcNode; typedef struct VNode {VertexType data; //頂點信息ArcNode *firstarc = NULL; //指向第一條與該頂點相連的弧 }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct {AdjList vertices; //每個圖類型中包含一個頂點數組int vexnum, arcnum; //圖的頂點數和弧數int kind; //圖的種類標志 }ALGraph;void createG(ALGraph *G); void showG(ALGraph *G);void DFSTraverse(ALGraph G); void DFS(ALGraph G, int i, void(*visit) (VNode v)); inline void Print(VNode v) { printf("%d\n", v.data); } //訪問函數

Graph.cpp

#include "Graph.h"int vnum[MAX_VERTEX_NUM] = { false }; //vnum為訪問標識數組void createG(ALGraph *G) //以鄰接表存儲方式創建圖 {//char TemData[64]; //暫時存儲頂點數據int i, j; //函數局部變量i,j用來記錄弧的頂點ArcNode *s; //新建的弧printf("請輸入頂點數和邊數:\n");scanf("%d%d", &G->vexnum, &G->arcnum);for (int i = 0; i < G->vexnum; i++) //輸入頂點信息,這里可以用下標唯一標識每個頂點{/*scanf("%s", TemData);G->vertices[i].data = (VertexType)TemData[64];*/G->vertices[i].data = (VertexType)i;}for (int k = 0; k < G->arcnum; k++){scanf("%d%d", &i, &j);s = (ArcNode *)malloc(sizeof(ArcNode)); //將s插入到i頂點的表頭s->adjvex = j;s->nextarc = G->vertices[i].firstarc;G->vertices[i].firstarc = s;s = (ArcNode *)malloc(sizeof(ArcNode)); //將s插入到j頂點的表頭s->adjvex = i;s->nextarc = G->vertices[j].firstarc;G->vertices[j].firstarc = s;} }void showG(ALGraph *G) //輸出表的信息 {ArcNode* Tem;for (int i = 0; i < G->vexnum; i++){printf("%d->", i);Tem = G->vertices[i].firstarc;while (Tem != NULL){printf("%d->", Tem->adjvex);Tem = Tem->nextarc;}printf("\n");} }void DFSTraverse(ALGraph G) { for (int i = 0; i < G.vexnum; i++)if (!vnum[i]) DFS(G, i, Print); }void DFS(ALGraph G, int i, void(*visit) (VNode v)) //對表G從頂點i開始做深度優先遍歷 {vnum[i] = true; visit(G.vertices[i]);for (ArcNode *w = G.vertices[i].firstarc; w != NULL; w = w->nextarc)if (!vnum[w->adjvex]) DFS(G, w->adjvex, Print); }

main.cpp

#include "Graph.h" void main() {ALGraph G;createG(&G);showG(&G);DFSTraverse(G); }

總結

以上是生活随笔為你收集整理的图的邻接表存储与深度优先遍历代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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