本文共 3058 字，大约阅读时间需要 10 分钟。
关于图的两种遍历（DFS和BFS）代码
欢迎阅读罡罡同学的文章。在学习字符串处理以及相关操作时，本人做了一系列实验，内容如下。实际遇到代码异常问题，可以在评论区留言，我会尽力解答。
adjacency list
#include#include #define MAX 20typedef struct EdgeNode { int adjvex; struct EdgeNode *next; int weight;} EdgeNode;typedef struct VertexNode { char data; EdgeNode *firstedge;} VertexNode;typedef struct { VertexNode adjlist[MAX]; int n, e;} GraphAdjlist;int visited[MAX];void create(GraphAdjlist *G) { int i, j, k; EdgeNode *e; printf("请输入顶点数和边数："); scanf("%d%d", &G->n, &G->e); getchar(); printf("请输入顶点边号：\n"); for (i = 0; i < G->n; i++) { scanf("%c", &G->adjlist[i].data); G->adjlist[i].firstedge = NULL; getchar(); } for (k = 0; k < G->e; k++) { printf("输入边（Vi, Vj）上的顶点序号：\n"); scanf("%d%d", &i, &j); e = malloc(sizeof(EdgeNode)); e->adjvex = j; e->next = G->adjlist[i].firstedge; G->adjlist[i].firstedge = e; e = malloc(sizeof(EdgeNode)); e->adjvex = i; e->next = G->adjlist[j].firstedge; G->adjlist[j].firstedge = e; } printf("\n");}void BFS(GraphAdjlist *G, int v) { EdgeNode *p; int queue[MAX], front = 0, rear = 0; for (i = 0; i < G->n; i++) { visited[i] = 0; printf("%c", G->adjlist[v].data); if (visited[v] == 0) { visited[v] = 1; rear = (rear + 1) % MAX; queue[rear] = v; } } while (front != rear) { front = (front + 1) % MAX; w = queue[front]; p = G->adjlist[w].firstedge; while (p != NULL) { if (visited[p->adjvex] == 0) { printf("%c", G->adjlist[p->adjvex].data); visited[p->adjvex] = 1; rear = (rear + 1) % MAX; queue[rear] = p->adjvex; } p = p->next; } } printf("\n");}int main() { GraphAdjlist G; create(&G); printf("广度优先遍历："); BFS(&G, 0; return 0;}
#include#include typedef struct EdgeNode { int adjvex; struct EdgeNode *next; int weight;} EdgeNode;typedef struct VertexNode { char data; EdgeNode *firstedge;} VertexNode;typedef struct { VertexNode adjlist[MAX]; int n, e;} GraphAdjlist;int visited[MAX];void DFS(GraphAdjlist *G, int i) { if (visited[i] == 0) { visited[i] = 1; printf("%c ", G->adjlist[i].data); p = G->adjlist[i].firstedge; while (p != NULL) { if (visited[p->adjvex] == 0) { DFS(G, p->adjvex); } p = p->next; } }}void DFSTraverse(GraphAdjlist *G) { int i; for (i = 0; i < G->n; i++) { if (visited[i] == 0) { DFS(G, i); } }}int main() { GraphAdjlist G; create(&G); printf("深度优先遍历："); DFSTraverse(&G); return 0;}
以上是罡罡同学在学习图的遍历算法时所完成的实验代码。通过本系列文章，读者可以了解广度优先搜索（BFS）和深度优先搜索（DFS）两种图遍历算法的实现方法及其适用场景。代码基于邻接表存储图结构，支持逆向图等特性，是学习图 traversal 的基础实践。本文将持续为大家提供更多技术案例和解决方案，欢迎在评论区交流！
如果您觉得本文对您有帮助，请记得点赞、关注并转发，罡罡同学非常感谢您的支持！
转载地址：http://bxllz.baihongyu.com/