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

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

深度优先遍历：

#define MAX 100
int visited[MAX] = {0}; // 全局数组，用于标记节点是否被访问过

// 深度优先遍历算法
void DFS(AdjGraph *G, int v) {
    ArcNode *p;
    visited[v] = 1; // 标记节点v已被访问
    printf("%d ", v); // 输出被访问的节点编号
    p = G->adjlist[v].firstarc;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) { // 若节点未被访问，则递归访问它
            DFS(G, p->adjvex);
        }
        p = p->nextarc;    }
}

// 深度优先遍历入口函数
void DFSTraverse(AdjGraph *G) {
    int i;
    for (i = 0; i < G->n; i++) {
        visited[i] = 0; // 初始化visited数组
    }
    for (i = 0; i < G->n; i++) {
        if (visited[i] == 0) { // 若节点未被访问，则从该节点开始进行深度优先遍历
            DFS(G, i);
        }
    }
}

广度优先遍历：

#define MAX 100
int visited[MAX] = {0}; // 全局数组，用于标记节点是否被访问过

// 广度优先遍历算法
void BFS(AdjGraph *G, int v) {
    int queue[MAX], front = 0, rear = 0; // 定义队列
    ArcNode *p;
    visited[v] = 1; // 标记节点v已被访问
    printf("%d ", v); // 输出被访问的节点编号
    rear = (rear + 1) % MAX;
    queue[rear] = v; // 将节点v入队
    while (front != rear) { // 队列不为空时循环
        front = (front + 1) % MAX;
        v = queue[front]; // 出队一个节点
        p = G->adjlist[v].firstarc;
        while (p != NULL) {
            if (visited[p->adjvex] == 0) { // 若节点未被访问，则标记为已访问并入队
                visited[p->adjvex] = 1;
                printf("%d ", p->adjvex);
                rear = (rear + 1) % MAX;
                queue[rear] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
}

// 广度优先遍历入口函数
void BFSTraverse(AdjGraph *G) {
    int i;
    for (i = 0; i < G->n; i++) {
        visited[i] = 0; // 初始化visited数组
    }
    for (i = 0; i < G->n; i++) {
        if (visited[i] == 0) { // 若节点未被访问，则从该节点开始进行广度优先遍历
            BFS(G, i);
        }
    }
}