本文主要是介绍图用邻接表表示的深度优先和广度优先遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
邻接表表示法进行深度优先遍历的示例代码：
#include <stdio.h>
#include <stdlib.h>#define MAX_VERTEX_NUM 100// 边表节点结构体
typedef struct ArcNode {int adjvex; // 邻接顶点下标struct ArcNode* nextarc; // 指向下一个邻接顶点的指针
} ArcNode;// 顶点表结构体
typedef struct VNode {int data; // 顶点数据ArcNode* firstarc; // 指向第一个邻接顶点的指针
} VNode, AdjList[MAX_VERTEX_NUM];// 图结构体
typedef struct {AdjList vertices; // 邻接表int vexnum, arcnum; // 顶点数、边数
} ALGraph;// 初始化图
void InitGraph(ALGraph* G, int vexnum) {G->vexnum = vexnum;G->arcnum = 0;for (int i = 0; i < vexnum; i++) {G->vertices[i].data = i; // 顶点数据默认为下标G->vertices[i].firstarc = NULL;}
}// 添加边
void AddEdge(ALGraph* G, int v1, int v2) {ArcNode* arc1 = (ArcNode*)malloc(sizeof(ArcNode));arc1->adjvex = v2;arc1->nextarc = G->vertices[v1].firstarc;G->vertices[v1].firstarc = arc1;ArcNode* arc2 = (ArcNode*)malloc(sizeof(ArcNode));arc2->adjvex = v1;arc2->nextarc = G->vertices[v2].firstarc;G->vertices[v2].firstarc = arc2;G->arcnum++;
}// 深度优先遍历递归函数
void DFS(ALGraph* G, int v, int* visited) {visited[v] = 1; // 标记当前顶点为已访问printf("%d ", G->vertices[v].data);ArcNode* arc = G->vertices[v].firstarc;while (arc != NULL) {if (visited[arc->adjvex] == 0) {DFS(G, arc->adjvex, visited); // 递归访问邻接顶点}arc = arc->nextarc;}
}// 深度优先遍历
void DFSTraverse(ALGraph* G) {int visited[MAX_VERTEX_NUM] = { 0 }; // 访问标记数组，初始化为0for (int v = 0; v < G->vexnum; v++) {if (visited[v] == 0) {DFS(G, v, visited); // 从未访问的顶点开始进行深度优先遍历}}
}int main() {ALGraph G;int vexnum = 5; // 图的顶点数InitGraph(&G, vexnum);AddEdge(&G, 0, 1);AddEdge(&G, 0, 2);AddEdge(&G, 1, 3);AddEdge(&G, 2, 4);DFSTraverse(&G);return 0;
}
其中顶点表使用了数组 AdjList，每个顶点表项存储了顶点的数据和指向第一个邻接顶点的指针。边表节点使用了结构体 ArcNode，存储了邻接顶点的下标和指向下一个邻接顶点的指针。
DFS 函数是一个递归函数，用于从给定顶点开始进行深度优先遍历。它首先将当前顶点标记为已访问，并输出顶点的数据。然后，遍历当前顶点的邻接表，对于每个未被访问过的邻接顶点，递归调用 DFS 函数进行遍历。
DFSTraverse 函数用于遍历图中所有顶点，并对未访问过的顶点调用 DFS 函数进行深度优先遍历。
广度优先遍历（Breadth-First Search，BFS）是一种图遍历算法，它以广度优先的顺序遍历图的所有节点。下面是使用邻接表表示图，并进行广度优先遍历的示例代码：
#include <stdio.h>
#include <stdlib.h>#define MAX_VERTEX_NUM 100// 边表节点结构体
typedef struct ArcNode {int adjvex; // 邻接顶点下标struct ArcNode* nextarc; // 指向下一个邻接顶点的指针
} ArcNode;// 顶点表结构体
typedef struct VNode {int data; // 顶点数据ArcNode* firstarc; // 指向第一个邻接顶点的指针
} VNode, AdjList[MAX_VERTEX_NUM];// 图结构体
typedef struct {AdjList vertices; // 邻接表int vexnum, arcnum; // 顶点数、边数
} ALGraph;// 初始化图
void InitGraph(ALGraph* G, int vexnum) {G->vexnum = vexnum;G->arcnum = 0;for (int i = 0; i < vexnum; i++) {G->vertices[i].data = i; // 顶点数据默认为下标G->vertices[i].firstarc = NULL;}
}// 添加边
void AddEdge(ALGraph* G, int v1, int v2) {ArcNode* arc1 = (ArcNode*)malloc(sizeof(ArcNode));arc1->adjvex = v2;arc1->nextarc = G->vertices[v1].firstarc;G->vertices[v1].firstarc = arc1;ArcNode* arc2 = (ArcNode*)malloc(sizeof(ArcNode));arc2->adjvex = v1;arc2->nextarc = G->vertices[v2].firstarc;G->vertices[v2].firstarc = arc2;G->arcnum++;
}// 广度优先遍历
void BFSTraverse(ALGraph* G, int v) {int visited[MAX_VERTEX_NUM] = { 0 }; // 访问标记数组，初始化为0int queue[MAX_VERTEX_NUM]; // 存储待访问顶点的队列int front = 0; // 队列头指针int rear = 0; // 队列尾指针visited[v] = 1; // 标记当前顶点为已访问printf("%d ", G->vertices[v].data);queue[rear++] = v; // 将当前顶点入队while (front < rear) {int w = queue[front++]; // 从队列中取出一个顶点ArcNode* arc = G->vertices[w].firstarc;while (arc != NULL) {int adjvex = arc->adjvex;if (visited[adjvex] == 0) {visited[adjvex] = 1; // 标记邻接顶点为已访问printf("%d ", G->vertices[adjvex].data);queue[rear++] = adjvex; // 将邻接顶点入队}arc = arc->nextarc;}}
}int main() {ALGraph G;int vexnum = 5; // 图的顶点数InitGraph(&G, vexnum);AddEdge(&G, 0, 1);AddEdge(&G, 0, 2);AddEdge(&G, 1, 3);AddEdge(&G, 2, 4);BFSTraverse(&G, 0);return 0;
}
在 BFSTraverse 函数中，我们使用一个队列来存储待访问的顶点。初始时，将起始顶点入队，并将其标记为已访问。然后，从队列中取出一个顶点进行处理，输出其数据，并将其所有未访问的邻接顶点入队并标记为已访问。重复这个过程，直到队列为空。这样就实现了广度优先遍历。
在 main 函数中，首先初始化图并添加边。然后，调用 BFSTraverse 函数以开始广度优先遍历。
这篇关于图用邻接表表示的深度优先和广度优先遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
