考研图C语言深度优先遍历代码及注释

好的，以下是C语言实现深度优先遍历的代码及注释： ```c #include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 // 最大顶点数 #define MAX_ARC_NUM 500 // 最大边数 typedef int VertexType; // 顶点的数据类型 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点数组 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum, arcnum; // 顶点数和边数 } MGraph; // 图的邻接矩阵表示法 typedef struct { VertexType data; // 数据域 int firstarc; // 头结点 } VNode; typedef struct { VNode adjlist[MAX_VERTEX_NUM]; // 邻接表 int vexnum, arcnum; // 顶点数和边数 } ALGraph; // 图的邻接表表示法 // 初始化邻接矩阵图 void InitMGraph(MGraph *G) { int i, j; for (i = 0; i < MAX_VERTEX_NUM; i++) { for (j = 0; j < MAX_VERTEX_NUM; j++) { G->arcs[i][j] = 0; // 初始化为0 } } G->vexnum = 0; G->arcnum = 0; } // 添加顶点到邻接矩阵图 void AddVertexToMGraph(MGraph *G, VertexType v) { G->vexs[G->vexnum++] = v; // 加入顶点数组 } // 添加边到邻接矩阵图 void AddEdgeToMGraph(MGraph *G, int v1, int v2) { G->arcs[v1][v2] = 1; G->arcs[v2][v1] = 1; // 无向图，所以要添加两条边 G->arcnum++; // 边数加1 } // 初始化邻接表图 void InitALGraph(ALGraph *G) { int i; for (i = 0; i < MAX_VERTEX_NUM; i++) { G->adjlist[i].firstarc = -1; // 初始化为-1 } G->vexnum = 0; G->arcnum = 0; } // 添加顶点到邻接表图 void AddVertexToALGraph(ALGraph *G, VertexType v) { G->adjlist[G->vexnum].data = v; // 加入数据 G->vexnum++; // 顶点数加1 } // 添加边到邻接表图 void AddEdgeToALGraph(ALGraph *G, int v1, int v2) { ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = v2; // 邻接点为v2 p->nextarc = G->adjlist[v1].firstarc; // 头插法 G->adjlist[v1].firstarc = p; // 头节点指向新节点 G->arcnum++; // 边数加1 } // 深度优先遍历邻接矩阵图 void DFSTraverseMGraph(MGraph G, int v, int visited[]) { printf("%d ", v); // 访问该顶点 visited[v] = 1; // 标记为已访问 int i; for (i = 0; i < G.vexnum; i++) { if (G.arcs[v][i] == 1 && !visited[i]) { // 如果存在边且未访问 DFSTraverseMGraph(G, i, visited); // 递归访问邻接点 } } } // 深度优先遍历邻接表图 void DFS(ALGraph *G, int v, int visited[]) { printf("%d ", v); // 访问该顶点 visited[v] = 1; // 标记为已访问 ArcNode *p = G->adjlist[v].firstarc; while (p != NULL) { if (!visited[p->adjvex]) { // 如果邻接点未访问 DFS(G, p->adjvex, visited); // 递归访问邻接点 } p = p->nextarc; // 访问下一个邻接点 } } int main() { MGraph G; InitMGraph(&G); AddVertexToMGraph(&G, 1); AddVertexToMGraph(&G, 2); AddVertexToMGraph(&G, 3); AddVertexToMGraph(&G, 4); AddVertexToMGraph(&G, 5); AddEdgeToMGraph(&G, 0, 1); AddEdgeToMGraph(&G, 0, 2); AddEdgeToMGraph(&G, 1, 3); AddEdgeToMGraph(&G, 1, 4); int visited[MAX_VERTEX_NUM] = {0}; DFSTraverseMGraph(G, 0, visited); ALGraph G; InitALGraph(&G); AddVertexToALGraph(&G, 1); AddVertexToALGraph(&G, 2); AddVertexToALGraph(&G, 3); AddVertexToALGraph(&G, 4); AddVertexToALGraph(&G, 5); AddEdgeToALGraph(&G, 0, 1); AddEdgeToALGraph(&G, 0, 2); AddEdgeToALGraph(&G, 1, 3); AddEdgeToALGraph(&G, 1, 4); int visited[MAX_VERTEX_NUM] = {0}; DFS(&G, 0, visited); return 0; } ``` 这里实现了两种图的表示方法：邻接矩阵和邻接表，分别对应 `MGraph` 和 `ALGraph` 结构体。其中，邻接矩阵使用二维数组表示，邻接表使用链表表示。在添加顶点和边的函数中，都是将数据存储到对应的结构体中，同时更新顶点数和边数。在深度优先遍历函数中，使用递归的方式遍历图，标记已访问的节点，避免重复访问。