图的遍历c++写一个完整版

以下是一个完整的图的遍历的 C 语言实现，包括深度优先遍历和广度优先遍历：

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100 // 定义图的最大顶点数

// 图的邻接表存储结构
typedef int Vertex;
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
    Vertex AdjV;  // 邻接点下标
    PtrToAdjVNode Next; // 指向下一个邻接点的指针
};
typedef struct VNode {
    PtrToAdjVNode FirstEdge; // 指向第一个邻接点的指针
} AdjList[MaxVertexNum];
typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv; // 顶点数
    int Ne; // 边数
    AdjList G; // 邻接表
};
typedef PtrToGNode Graph;

// 初始化图
Graph CreateGraph(int VertexNum) {
    Graph G = (Graph)malloc(sizeof(struct GNode));
    G->Nv = VertexNum;
    G->Ne = 0;
    for (Vertex V = 0; V < G->Nv; V++) {
        G->G[V].FirstEdge = NULL;
    }
    return G;
}

// 插入边
void InsertEdge(Graph G, Vertex V, Vertex W) {
    PtrToAdjVNode NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = W;
    NewNode->Next = G->G[V].FirstEdge;
    G->G[V].FirstEdge = NewNode;
}

// 深度优先遍历
void DFS(Graph G, Vertex V, int Visited[]) {
    Visited[V] = 1; // 标记 V 已访问
    printf("%d ", V); // 访问 V
    for (PtrToAdjVNode W = G->G[V].FirstEdge; W; W = W->Next) { // 对 V 的每个邻接点 W
        if (!Visited[W->AdjV]) { // 若 W 未被访问
            DFS(G, W->AdjV, Visited); // 递归访问 W
        }
    }
}

// 广度优先遍历
void BFS(Graph G, Vertex V, int Visited[]) {
    int Queue[MaxVertexNum], Front = 0, Rear = 0;
    Queue[Rear++] = V; // V 入队
    Visited[V] = 1; // 标记 V 已访问
    printf("%d ", V); // 访问 V
    while (Front != Rear) { // 队列非空
        Vertex F = Queue[Front++]; // 队头元素出队
        for (PtrToAdjVNode W = G->G[F].FirstEdge; W; W = W->Next) { // 对 F 的每个邻接点 W
            if (!Visited[W->AdjV]) { // 若 W 未被访问
                Queue[Rear++] = W->AdjV; // W 入队
                Visited[W->AdjV] = 1; // 标记 W 已访问
                printf("%d ", W->AdjV); // 访问 W
            }
        }
    }
}

int main() {
    Graph G = CreateGraph(5);
    InsertEdge(G, 0, 1);
    InsertEdge(G, 0, 4);
    InsertEdge(G, 1, 0);
    InsertEdge(G, 1, 2);
    InsertEdge(G, 1, 3);
    InsertEdge(G, 1, 4);
    InsertEdge(G, 2, 1);
    InsertEdge(G, 2, 3);
    InsertEdge(G, 3, 1);
    InsertEdge(G, 3, 2);
    InsertEdge(G, 4, 0);
    InsertEdge(G, 4, 1);

    int Visited[MaxVertexNum] = {0};
    printf("DFS: ");
    for (Vertex V = 0; V < G->Nv; V++) {
        if (!Visited[V]) {
            DFS(G, V, Visited);
        }
    }
    printf("\nBFS: ");
    for (Vertex V = 0; V < G->Nv; V++) {
        Visited[V] = 0;
    }
    for (Vertex V = 0; V < G->Nv; V++) {
        if (!Visited[V]) {
            BFS(G, V, Visited);
        }
    }

    return 0;
}

以上代码中，`CreateGraph` 函数用于创建一个空的具有 `VertexNum` 个顶点的图；`InsertEdge` 函数用于在图中插入从顶点 `V` 到顶点 `W` 的一条边；`DFS` 函数用于对图进行深度优先遍历，其中 `Visited` 数组用于标记每个顶点是否已被访问过；`BFS` 函数用于对图进行广度优先遍历，其中 `Queue` 数组用于存储待访问的顶点，`Front` 和 `Rear` 分别指向队列的队头和队尾。最后，`main` 函数用于测试图的遍历算法。