用c语言实现一个图的两种遍历算法

以下是C语言实现图的深度优先遍历和广度优先遍历的示例代码：

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

#define MAXVEX 100  // 最大顶点数

typedef char VertexType;  // 顶点类型
typedef int EdgeType;     // 边权类型

typedef struct {
    VertexType vexs[MAXVEX];   // 顶点集合
    EdgeType arc[MAXVEX][MAXVEX];  // 邻接矩阵，可看作边表
    int numVertexes, numEdges;  // 图中当前的顶点数和边数
} MGraph;

// 初始化图
void initGraph(MGraph *G) {
    int i, j, k, weight, n;

    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G->numVertexes, &G->numEdges);

    // 读入顶点信息
    printf("请输入顶点信息：\n");
    for (i = 0; i < G->numVertexes; i++) {
        scanf("%c", &G->vexs[i]);  // 吸收换行符
        scanf("%c", &G->vexs[i]);
    }

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

    // 读入边信息，建立邻接矩阵
    printf("请输入边信息：\n");
    for (k = 0; k < G->numEdges; k++) {
        printf("请输入边（vi, vj）的下标i, j和权重：\n");
        scanf("%d%d%d", &i, &j, &weight);
        G->arc[i][j] = weight;
        G->arc[j][i] = weight;   // 无向图的边是双向的
    }
}

// 访问顶点
void visitVertex(VertexType vertex) {
    printf("%c ", vertex);
}

// 深度优先遍历
void DFS(MGraph G, int i, bool *visited) {
    int j;

    visited[i] = true;  // 标记当前顶点已访问
    visitVertex(G.vexs[i]);  // 访问当前顶点

    // 从当前顶点出发，递归访问所有未被访问的邻接顶点
    for (j = 0; j < G.numVertexes; j++) {
        if (G.arc[i][j] != 0 && !visited[j]) {
            DFS(G, j, visited);
        }
    }
}

// 深度优先遍历图
void DFSTraverse(MGraph G) {
    int i;
    bool visited[MAXVEX];

    // 初始化所有顶点都未被访问
    for (i = 0; i < G.numVertexes; i++) {
        visited[i] = false;
    }

    // 对每个未被访问过的顶点调用DFS，遍历整个图
    for (i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
}

// 队列结构体
typedef struct {
    int data[MAXVEX];
    int front, rear;
} Queue;

// 初始化队列
void initQueue(Queue *Q) {
    Q->front = Q->rear = 0;
}

// 入队
void enQueue(Queue *Q, int value) {
    Q->data[Q->rear++] = value;
}

// 出队
int deQueue(Queue *Q) {
    return Q->data[Q->front++];
}

// 判断队列是否为空
bool isQueueEmpty(Queue Q) {
    return Q.front == Q.rear;
}

// 广度优先遍历
void BFS(MGraph G, int i, bool *visited) {
    int j, k;
    Queue Q;

    initQueue(&Q);  // 初始化队列
    visited[i] = true;  // 标记当前顶点已访问
    visitVertex(G.vexs[i]);  // 访问当前顶点
    enQueue(&Q, i);  // 将当前顶点入队

    while (!isQueueEmpty(Q)) {
        j = deQueue(&Q);  // 出队顶点
        // 遍历所有未被访问的邻接顶点，入队并标记已访问
        for (k = 0; k < G.numVertexes; k++) {
            if (G.arc[j][k] != 0 && !visited[k]) {
                visited[k] = true;
                visitVertex(G.vexs[k]);
                enQueue(&Q, k);
            }
        }
    }
}

// 广度优先遍历图
void BFSTraverse(MGraph G) {
    int i;
    bool visited[MAXVEX];

    // 初始化所有顶点都未被访问
    for (i = 0; i < G.numVertexes; i++) {
        visited[i] = false;
    }

    // 对每个未被访问过的顶点调用BFS，遍历整个图
    for (i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
}

int main() {
    MGraph G;

    initGraph(&G);  // 初始化图

    printf("深度优先遍历结果：\n");
    DFSTraverse(G);  // 深度优先遍历图

    printf("\n广度优先遍历结果：\n");
    BFSTraverse(G);  // 广度优先遍历图

    return 0;
}

注意，在代码中的 `MGraph` 结构体中，`vexs` 数组存储的是顶点集合，`arc` 二维数组即邻接矩阵，表示顶点之间是否有边相连，如果有，权重为边的权重。在输入边信息时，输入的下标 i、j 分别对应的是邻接矩阵中的行和列。在遍历图时，用一个 `visited` 数组记录每个顶点是否被访问过，防止死循环。