c语言编程实现图的深度优先遍历和广度优先遍历算法

图的深度优先遍历和广度优先遍历算法是图论中的基础算法，C语言可以通过邻接矩阵或邻接表实现。下面是基于邻接矩阵实现的代码：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INFINITY 65535 // 表示无穷大

typedef struct {
    int vexs[MAX_VERTEX_NUM]; // 存储顶点的数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的二维数组
    int vexnum, arcnum; // 存储顶点数和边数
} Graph;

bool visited[MAX_VERTEX_NUM]; // 存储节点是否被访问过

// 创建图
void CreateGraph(Graph *G)
{
    int i, j, k, w;

    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);

    // 初始化邻接矩阵
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = INFINITY;
        }
    }

    // 输入顶点
    printf("请输入%d个顶点：", G->vexnum);
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vexs[i]);
    }

    // 输入边
    printf("请输入%d条边：\n", G->arcnum);
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入第%d条边的起点、终点和权值：", k + 1);
        scanf("%d %d %d", &i, &j, &w);
        G->arcs[i][j] = w;
        G->arcs[j][i] = w; // 无向图，两个方向都要存储
    }
}

// 深度优先遍历
void DFS(Graph G, int v)
{
    int i;

    visited[v] = true;
    printf("%d ", G.vexs[v]);

    for (i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i] != INFINITY && !visited[i]) {
            DFS(G, i);
        }
    }
}

// 广度优先遍历
void BFS(Graph G, int v)
{
    int i, j;
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 定义队列

    visited[v] = true;
    printf("%d ", G.vexs[v]);
    queue[rear++] = v;

    while (front != rear) {
        i = queue[front++];

        for (j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j] != INFINITY && !visited[j]) {
                visited[j] = true;
                printf("%d ", G.vexs[j]);
                queue[rear++] = j;
            }
        }
    }
}

int main()
{
    Graph G;
    int i;

    CreateGraph(&G);

    // 初始化visited数组
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }

    printf("深度优先遍历：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }

    // 重新初始化visited数组
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }

    printf("\n广度优先遍历：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i);
        }
    }

    return 0;
}

这段代码实现了基于邻接矩阵的图的深度优先遍历和广度优先遍历算法。其中，`CreateGraph`函数用于创建图，`DFS`函数用于深度优先遍历，`BFS`函数用于广度优先遍历。在遍历过程中，首先需要初始化`visited`数组，然后对于每个未被访问过的节点，调用相应的遍历函数进行遍历。