C语言实现图的深度优先与广度优先遍历算法

## 图的深度广度遍历程序C语言实现 图是计算机科学中广泛使用的一种数据结构，用于模拟各种复杂的数据关系。图的遍历是图论中的一项基础操作，常见的遍历算法包括深度优先遍历（DFS）和广度优先遍历（BFS）。本篇将详细介绍如何使用C语言实现图的深度优先遍历和广度优先遍历。 ### 图的概念 在详细介绍算法之前，我们先要理解图的基本概念。图由顶点（节点）集合和边集合组成。在图中，节点之间的连接关系通过边表示。根据边是否有方向，图分为无向图和有向图；而根据边是否带权值，图又分为无权图和带权图。 ### 深度优先遍历（DFS） 深度优先遍历是一种用于遍历或搜索树或图的算法。该算法沿着图的深度遍历，尽可能深地搜索图的分支，当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。 #### 深度优先遍历步骤 1. 访问起始节点。 2. 从未被访问的节点中选取一个，将其标记为已访问，并递归地调用深度优先遍历。 3. 如果没有未访问的节点，回溯到上一个节点，并尝试其他未访问的节点。 4. 重复步骤2和3直到所有节点都被访问。 ### 广度优先遍历（BFS） 广度优先遍历算法是一种遍历或搜索树或图的算法。该算法从起始节点开始，逐层向外扩展，访问节点的所有相邻节点，然后再对这些相邻节点的未访问的邻居节点进行访问，直到所有节点都被访问到。 #### 广度优先遍历步骤 1. 访问起始节点，并将其放入队列。 2. 当队列非空时，进行如下操作： a. 从队列中取出首节点，并访问该节点。 b. 将首节点的所有未访问的邻居节点加入队列。 c. 重复步骤b直到队列为空。 3. 当队列为空时，所有可从起始节点到达的节点都被访问过。 ### C语言实现 在C语言中，图可以使用多种数据结构表示，如邻接矩阵和邻接表。在给定文件中提到了"Adjacency Multilist"，即邻接多重表。邻接多重表是一种用来存储图的数据结构，它以一种灵活的方式存储节点和边，适合于表示无向图。 #### 邻接多重表的数据结构定义 ```c #define MAX_VERTICES 100 typedef struct ArcNode { int adjvex; // 边所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 } ArcNode; typedef struct VNode { int data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附于该顶点的弧的指针 } VNode, AdjList[MAX_VERTICES]; typedef struct { AdjList vertices; int vexnum, arcnum; // 图的当前顶点数和边数 } GraphAdjList; ``` #### 深度优先遍历的C语言实现 ```c void DFS(GraphAdjList *G, int v, int visited[]) { visited[v] = TRUE; // 标记当前节点为已访问 printf("%d ", v); // 访问节点 ArcNode *arc = G->vertices[v].firstarc; while (arc) { if (!visited[arc->adjvex]) { DFS(G, arc->adjvex, visited); } arc = arc->nextarc; } } ``` #### 广度优先遍历的C语言实现 ```c void BFS(GraphAdjList *G, int v) { int visited[MAX_VERTICES] = {0}; // 初始化访问标记数组为0 queue q; InitQueue(&q); // 初始化队列 visited[v] = 1; printf("%d ", v); // 访问起始节点 EnQueue(&q, v); // 起始节点入队列 while (!QueueEmpty(q)) { DeQueue(&q, &v); // 出队列 ArcNode *arc = G->vertices[v].firstarc; while (arc) { if (!visited[arc->adjvex]) { visited[arc->adjvex] = 1; printf("%d ", arc->adjvex); EnQueue(&q, arc->adjvex); // 入队列 } arc = arc->nextarc; } } DestroyQueue(&q); // 销毁队列 } ``` ### 结语 在C语言中实现图的深度优先遍历和广度优先遍历，需要掌握图的基本概念、遍历算法原理以及C语言的数据结构。通过上述的介绍和示例代码，我们可以手动构建一个图，并通过深度优先或广度优先的方式对图进行遍历，这对于图论的学习和应用有着非常重要的意义。在实际应用中，图的遍历算法被广泛用于网络路径规划、社交网络分析、游戏开发中的地图探索等场景。