用C语言实现图的广度优先遍历和深度优先遍历

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

广度优先遍历：

#include <stdio.h>
#define MAXVEX 100  // 最大顶点数
#define INFINITY 65535  // 用65535来代表无穷大

typedef int EdgeType;  // 边的权值类型
typedef char VertexType;  // 顶点的数据类型

// 邻接表存储结构
typedef struct EdgeNode {
    int adjvex;  // 邻接点域，存储该顶点对应的下标
    EdgeType weight;  // 权值
    struct EdgeNode *next;  // 链域，指向下一个邻接点
} EdgeNode;

typedef struct VertexNode {
    VertexType data;  // 顶点信息
    EdgeNode *firstedge;  // 边表头指针
} VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;  // 邻接表
    int numVertexes, numEdges;  // 图中当前顶点数和边数
} GraphAdjList;

// 初始化邻接表
void InitGraph(GraphAdjList *G) {
    int i;
    for (i = 0; i < G->numVertexes; i++) {
        G->adjList[i].data = 'A' + i;  // 顶点信息
        G->adjList[i].firstedge = NULL;  // 边表头指针
    }
}

// 建立无向图的邻接表结构
void CreateGraph(GraphAdjList *G) {
    int i, j, k;
    EdgeNode *e;
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G->numVertexes, &G->numEdges);
    InitGraph(G);
    for (k = 0; k < G->numEdges; k++) {
        printf("请输入边(vi, vj)上的顶点序号：\n");
        scanf("%d%d", &i, &j);
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->next = G->adjList[i].firstedge;
        G->adjList[i].firstedge = e;
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->next = G->adjList[j].firstedge;
        G->adjList[j].firstedge = e;
    }
}

// 广度优先遍历
void BFS(GraphAdjList G, int i, int visited[]) {
    int j;
    EdgeNode *p;
    int queue[MAXVEX], front = 0, rear = 0;
    printf("%c ", G.adjList[i].data);
    visited[i] = 1;
    queue[rear++] = i;
    while (front != rear) {
        j = queue[front++];
        p = G.adjList[j].firstedge;
        while (p) {
            if (!visited[p->adjvex]) {
                printf("%c ", G.adjList[p->adjvex].data);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

// 深度优先遍历
void DFS(GraphAdjList G, int i, int visited[]) {
    EdgeNode *p;
    printf("%c ", G.adjList[i].data);
    visited[i] = 1;
    p = G.adjList[i].firstedge;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

int main() {
    GraphAdjList G;
    int visited[MAXVEX] = {0};
    CreateGraph(&G);
    printf("广度优先遍历结果：\n");
    BFS(G, 0, visited);
    printf("\n深度优先遍历结果：\n");
    DFS(G, 0, visited);
    return 0;
}

示例输入：

请输入顶点数和边数：
5 6
请输入边(vi, vj)上的顶点序号：
0 1
请输入边(vi, vj)上的顶点序号：
0 2
请输入边(vi, vj)上的顶点序号：
1 2
请输入边(vi, vj)上的顶点序号：
1 3
请输入边(vi, vj)上的顶点序号：
2 4
请输入边(vi, vj)上的顶点序号：
3 4

示例输出：

广度优先遍历结果：
A B C D E 
深度优先遍历结果：
A B C D E