C语言图的遍历算法实现(附代码示例)

#include <stdio.h> #include <stdlib.h>

#define MAX_VERTEX_NUM 20

// 定义邻接表中的边结点 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; // 顶点数 int arcnum; // 边数 } Graph;

// 初始化图 void InitGraph(Graph* G) { int i; G->vexnum = 0; G->arcnum = 0; for (i = 0; i < MAX_VERTEX_NUM; i++) { G->vertices[i].data = 0; G->vertices[i].firstarc = NULL; } }

// 添加顶点 void AddVertex(Graph* G, int data) { if (G->vexnum >= MAX_VERTEX_NUM) { printf('Exceed the maximum number of vertices!\n'); return; } G->vertices[G->vexnum].data = data; G->vexnum++; }

// 添加边 void AddEdge(Graph* G, int v1, int v2) { if (v1 >= G->vexnum || v2 >= G->vexnum) { printf('Invalid vertex index!\n'); return; } ArcNode* arcNode1 = (ArcNode*)malloc(sizeof(ArcNode)); arcNode1->adjvex = v2; arcNode1->nextarc = G->vertices[v1].firstarc; G->vertices[v1].firstarc = arcNode1;

ArcNode* arcNode2 = (ArcNode*)malloc(sizeof(ArcNode));
arcNode2->adjvex = v1;
arcNode2->nextarc = G->vertices[v2].firstarc;
G->vertices[v2].firstarc = arcNode2;

G->arcnum++;

}

// 深度优先搜索遍历算法 void DFS(Graph* G, int v, int* visited) { printf('%d ', G->vertices[v].data); visited[v] = 1; ArcNode* arcNode = G->vertices[v].firstarc; while (arcNode != NULL) { if (!visited[arcNode->adjvex]) { DFS(G, arcNode->adjvex, visited); } arcNode = arcNode->nextarc; } }

// 广度优先搜索遍历算法 void BFS(Graph* G, int v, int* visited) { int queue[MAX_VERTEX_NUM]; int front = 0; int rear = 0; printf('%d ', G->vertices[v].data); visited[v] = 1; queue[rear++] = v; while (front < rear) { int u = queue[front++]; ArcNode* arcNode = G->vertices[u].firstarc; while (arcNode != NULL) { if (!visited[arcNode->adjvex]) { printf('%d ', G->vertices[arcNode->adjvex].data); visited[arcNode->adjvex] = 1; queue[rear++] = arcNode->adjvex; } arcNode = arcNode->nextarc; } } }

int main() { Graph G; InitGraph(&G); AddVertex(&G, 1); AddVertex(&G, 2); AddVertex(&G, 3); AddVertex(&G, 4); AddVertex(&G, 5); AddEdge(&G, 0, 1); AddEdge(&G, 0, 2); AddEdge(&G, 0, 3); AddEdge(&G, 1, 4); printf('DFS: '); int visited[MAX_VERTEX_NUM] = {0}; DFS(&G, 0, visited); printf('\n'); printf('BFS: '); int visited2[MAX_VERTEX_NUM] = {0}; BFS(&G, 0, visited2); printf('\n'); return 0; }