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

本文提供一个使用C语言编写的图的遍历算法示例代码，包含图的创建、深度优先搜索、广度优先搜索以及输出遍历结果。

1. 采用邻接表存储结构创建一个图

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

#define MAX_VERTEX_NUM 100

// 邻接表中的边结点
typedef struct EdgeNode {
    int adjvex;                 // 邻接点的下标
    struct EdgeNode *next;      // 指向下一个邻接点的指针
} EdgeNode;

// 邻接表中的顶点结点
typedef struct VertexNode {
    int data;                   // 顶点的数据
    EdgeNode *firstEdge;        // 指向第一个邻接点的指针
} VertexNode;

// 图的邻接表结构
typedef struct {
    VertexNode adjList[MAX_VERTEX_NUM];     // 邻接表
    int numVertexes;                        // 顶点数
    int numEdges;                           // 边数
} Graph;

// 初始化图
void initGraph(Graph *G) {
    printf('请输入图的顶点数和边数：');
    scanf('%d %d', &(G->numVertexes), &(G->numEdges));
    getchar();  // 读取换行符

    // 初始化邻接表
    for (int i = 0; i < G->numVertexes; i++) {
        printf('请输入第 %d 个顶点的数据：', i + 1);
        scanf('%d', &(G->adjList[i].data));
        G->adjList[i].firstEdge = NULL;
    }

    // 建立边表
    int v1, v2;
    for (int k = 0; k < G->numEdges; k++) {
        printf('请输入第 %d 条边的两个顶点的序号（从1开始）：', k + 1);
        scanf('%d %d', &v1, &v2);

        // 创建边结点
        EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = v2 - 1;
        e->next = G->adjList[v1 - 1].firstEdge;
        G->adjList[v1 - 1].firstEdge = e;

        // 如果是无向图，还需要创建反向的边结点
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = v1 - 1;
        e->next = G->adjList[v2 - 1].firstEdge;
        G->adjList[v2 - 1].firstEdge = e;
    }
}

2. 编程实现图的深度优先搜索（或广度优先搜索）遍历算法

// 深度优先搜索遍历算法
void DFS(Graph G, int v, int visited[]) {
    visited[v] = 1;  // 标记该顶点已访问
    printf('%d ', G.adjList[v].data);

    EdgeNode *p = G.adjList[v].firstEdge;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 深度优先搜索遍历图
void DFSTraverse(Graph G) {
    int visited[MAX_VERTEX_NUM] = {0};  // 访问标记数组

    printf('深度优先搜索遍历结果：');
    for (int i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
    printf('
');
}


// 广度优先搜索遍历算法
void BFS(Graph G, int v, int visited[]) {
    int queue[MAX_VERTEX_NUM];  // 辅助队列
    int front = 0, rear = 0;

    visited[v] = 1;  // 标记该顶点已访问
    printf('%d ', G.adjList[v].data);
    queue[rear++] = v;  // 入队

    while (front != rear) {
        int u = queue[front++];  // 出队
        EdgeNode *p = G.adjList[u].firstEdge;
        while (p) {
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = 1;  // 标记该顶点已访问
                printf('%d ', G.adjList[p->adjvex].data);
                queue[rear++] = p->adjvex;  // 入队
            }
            p = p->next;
        }
    }
}

// 广度优先搜索遍历图
void BFSTraverse(Graph G) {
    int visited[MAX_VERTEX_NUM] = {0};  // 访问标记数组

    printf('广度优先搜索遍历结果：');
    for (int i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf('
');
}

3. 输出遍历结果

int main() {
    Graph G;
    initGraph(&G);
    DFSTraverse(G);
    BFSTraverse(G);
    return 0;
}

4. 给定具体数据调试程序

例如，输入以下数据：

程序将会输出：

深度优先搜索遍历结果：1 2 4 5 3 
广度优先搜索遍历结果：1 2 3 4 5

总结

本文介绍了使用C语言实现图的遍历算法，并提供了深度优先搜索和广度优先搜索两种算法的代码实现。代码清晰易懂，并附带详细注释，适合学习数据结构与算法的初学者参考学习。