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

好的，下面是C语言实现图的深度优先遍历和广度优先遍历算法的代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100

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

// 顶点节点
typedef struct VNode {
    int data; // 顶点的数据
    ArcNode *first; // 指向第一个邻接点的指针
} VNode;

// 邻接表图
typedef struct {
    VNode vexs[MAX_VERTEX_NUM]; // 顶点数组
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

// 初始化邻接表图
void InitGraph(ALGraph *G) {
    int i;
    G->vexnum = G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vexs[i].first = NULL;
    }
}

// 添加边
void AddArc(ALGraph *G, int v1, int v2) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = v2;
    p->next = G->vexs[v1].first;
    G->vexs[v1].first = p;
    G->arcnum++;
}

// 深度优先遍历
void DFS(ALGraph *G, int v, int *visited) {
    ArcNode *p;
    printf("%d ", G->vexs[v].data);
    visited[v] = 1;
    p = G->vexs[v].first;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 广度优先遍历
void BFS(ALGraph *G, int v, int *visited) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    ArcNode *p;
    printf("%d ", G->vexs[v].data);
    visited[v] = 1;
    queue[rear++] = v;
    while (front != rear) {
        v = queue[front++];
        p = G->vexs[v].first;
        while (p) {
            if (!visited[p->adjvex]) {
                printf("%d ", G->vexs[p->adjvex].data);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

int main() {
    ALGraph G;
    int visited[MAX_VERTEX_NUM] = {0};
    int i;
    InitGraph(&G);
    G.vexs[0].data = 0;
    G.vexs[1].data = 1;
    G.vexs[2].data = 2;
    G.vexs[3].data = 3;
    G.vexs[4].data = 4;
    G.vexs[5].data = 5;
    AddArc(&G, 0, 1);
    AddArc(&G, 0, 2);
    AddArc(&G, 0, 5);
    AddArc(&G, 1, 0);
    AddArc(&G, 1, 2);
    AddArc(&G, 1, 3);
    AddArc(&G, 2, 0);
    AddArc(&G, 2, 1);
    AddArc(&G, 2, 3);
    AddArc(&G, 2, 4);
    AddArc(&G, 3, 1);
    AddArc(&G, 3, 2);
    AddArc(&G, 3, 4);
    AddArc(&G, 4, 2);
    AddArc(&G, 4, 3);
    AddArc(&G, 4, 5);
    AddArc(&G, 5, 0);
    AddArc(&G, 5, 4);
    printf("DFS: ");
    DFS(&G, 0, visited);
    printf("\n");
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        visited[i] = 0;
    }
    printf("BFS: ");
    BFS(&G, 0, visited);
    printf("\n");
    return 0;
}

这里我们通过邻接表来表示图，其中`VNode`是顶点节点，包括了顶点的数据和指向第一个邻接点的指针，`ArcNode`是边表节点，包括了邻接点的下标和指向下一个邻接点的指针。`ALGraph`是邻接表图，包括了顶点数组和顶点数、边数。

`InitGraph`函数用于初始化邻接表图，将顶点数和边数都赋值为0，同时将每个顶点的第一个邻接点指向空。

`AddArc`函数用于添加边，首先分配一个边表节点，将邻接点的下标赋值给它，然后将该节点插入到顶点的邻接点链表的最前面，最后将边数加1。

`DFS`函数是深度优先遍历算法，从第v个顶点开始遍历，首先输出该顶点的数据，然后将该顶点标记为已访问，接着遍历该顶点的每一个邻接点，如果该邻接点没有被访问过，则递归调用DFS函数。

`BFS`函数是广度优先遍历算法，从第v个顶点开始遍历，首先输出该顶点的数据，然后将该顶点标记为已访问，并将其加入到队列中，接着从队列的最前面取出一个顶点，遍历该顶点的每一个邻接点，如果该邻接点没有被访问过，则输出它的数据，标记为已访问，并将其加入到队列的最后面。

最后在`main`函数中，我们创建了一个邻接表图，然后分别调用了DFS函数和BFS函数进行遍历。