C语言实现图的深度优先搜索和广度优先搜索的代码

好的，以下是C语言实现图的深度优先搜索和广度优先搜索的代码：

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

#define MAX_VERTEX_NUM 100

typedef int ElemType;

typedef struct ArcNode {
    int adjvex;
    struct ArcNode* next;
} ArcNode;

typedef struct {
    ElemType data;
    ArcNode* firstarc;
} VNode;

typedef struct {
    VNode vertices[MAX_VERTEX_NUM];
    int vexnum, arcnum;
} ALGraph;

// 访问节点
void Visit(int vertex) {
    printf("%d ", vertex);
}

// 深度优先搜索
void DFS(ALGraph* G, int v, int visited[]) {
    visited[v] = 1;
    Visit(G->vertices[v].data);
    ArcNode* p = G->vertices[v].firstarc;
    while (p != NULL) {
        int adjvex = p->adjvex;
        if (!visited[adjvex]) {
            DFS(G, adjvex, visited);
        }
        p = p->next;
    }
}

void DFSTraverse(ALGraph* G) {
    int visited[MAX_VERTEX_NUM];
    for (int i = 0; i < G->vexnum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
}

// 广度优先搜索
void BFSTraverse(ALGraph* G) {
    int visited[MAX_VERTEX_NUM];
    for (int i = 0; i < G->vexnum; i++) {
        visited[i] = 0;
    }

    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            Visit(G->vertices[i].data);
            queue[rear++] = i;
        }
        while (front != rear) {
            int j = queue[front++];
            ArcNode* p = G->vertices[j].firstarc;
            while (p != NULL) {
                int adjvex = p->adjvex;
                if (!visited[adjvex]) {
                    visited[adjvex] = 1;
                    Visit(G->vertices[adjvex].data);
                    queue[rear++] = adjvex;
                }
                p = p->next;
            }
        }
    }
}

int main() {
    // 构造如下的无向图
    /*
         1 --- 2 --- 3
         |   / |
         | /   |
         4 --- 5 --- 6
    */
    ALGraph G = {
        .vexnum = 6,
        .arcnum = 7,
        .vertices = {
            {.data = 1, .firstarc = NULL},
            {.data = 2, .firstarc = NULL},
            {.data = 3, .firstarc = NULL},
            {.data = 4, .firstarc = NULL},
            {.data = 5, .firstarc = NULL},
            {.data = 6, .firstarc = NULL},
        },
    };
    ArcNode* arcs[] = {
        &(ArcNode){.adjvex = 1, .next = &(ArcNode){.adjvex = 3, .next = NULL}},
        &(ArcNode){.adjvex = 0, .next = &(ArcNode){.adjvex = 2, .next = &(ArcNode){.adjvex = 4, .next = &(ArcNode){.adjvex = NULL}}}},
        &(ArcNode){.adjvex = 1, .next = &(ArcNode){.adjvex = 5, .next = NULL}},
        &(ArcNode){.adjvex = 0, .next = &(ArcNode){.adjvex = 4, .next = NULL}},
        &(ArcNode){.adjvex = 1, .next = &(ArcNode){.adjvex = 3, .next = &(ArcNode){.adjvex = 5, .next = NULL}}},
        &(ArcNode){.adjvex = 2, .next = &(ArcNode){.adjvex = 4, .next = NULL}},
    };
    for (int i = 0; i < G.arcnum; i++) {
        int v = i / 2;
        arcs[i]->next = G.vertices[v].firstarc;
        G.vertices[v].firstarc = arcs[i];
    }

    printf("DFS: ");
    DFSTraverse(&G);
    printf("\n");

    printf("BFS: ");
    BFSTraverse(&G);
    printf("\n");

    return 0;
}

这段代码实现了一个邻接表存储的无向图，使用深度优先搜索和广度优先搜索分别遍历整个图。其中，邻接表的数据结构定义如下：

typedef struct ArcNode {
    int adjvex;
    struct ArcNode* next;
} ArcNode;

typedef struct {
    ElemType data;
    ArcNode* firstarc;
} VNode;

typedef struct {
    VNode vertices[MAX_VERTEX_NUM];
    int vexnum, arcnum;
} ALGraph;

其中，`VNode` 表示图中每个节点（即顶点），`ArcNode` 表示每条边存储的信息（包括邻接点和下一个邻接边），`ALGraph` 是整个图的数据结构，包含所有节点和边的信息。

深度优先搜索和广度优先搜索还需要用到一个 `visited` 数组，用于记录每个节点是否被访问过，以避免重复遍历。

要注意的是，在 `main()` 函数中使用了一个嵌套的复合字面量，即使用了C99中的特性。这是为了方便初始化邻接表。