c++创建图的数据结构以及图的深度优先遍历

以下是C++创建图的数据结构以及图的深度优先遍历的介绍和演示：

1. 创建图的数据结构

在C++中，我们可以使用邻接矩阵或邻接表来表示图。邻接矩阵是一个二维数组，其中每个元素表示两个顶点之间是否有边。邻接表则是由每个顶点的邻接点列表组成的数组。每个邻接点列表包含与该顶点相邻的所有顶点。

下面是使用邻接表表示图的C++代码示例：

#include <iostream>
#include <vector>
using namespace std;

// 邻接点结构体
struct AdjNode {
    int v; // 相邻顶点的下标
    AdjNode* next; // 指向下一个邻接点的指针
    AdjNode(int _v) : v(_v), next(nullptr) {}
};

// 顶点结构体
struct Vertex {
    char data; // 顶点数据
    AdjNode* first; // 指向第一个邻接点的指针
    Vertex(char _data) : data(_data), first(nullptr) {}
};

// 图结构体
struct Graph {
    vector<Vertex> Vex; // 顶点数组
    int vexNum; // 顶点数
    int edgeNum; // 边数
    Graph(int n) : vexNum(n), edgeNum(0) {
        Vex.resize(n);
    }
};

// 添加边
void addEdge(Graph& G, int u, int v) {
    AdjNode* node = new AdjNode(v);
    node->next = G.Vex[u].first;
    G.Vex[u].first = node;
    G.edgeNum++;
}

// 创建图
Graph createGraph() {
    int n, m;
    cout << "请输入顶点数和边数：";
    cin >> n >> m;
    Graph G(n);
    cout << "请输入每个顶点的数据：";
    for (int i = 0; i < n; i++) {
        char data;
        cin >> data;
        G.Vex[i] = Vertex(data);
    }
    cout << "请输入每条边的起点和终点（下标从0开始）：" << endl;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(G, u, v);
        addEdge(G, v, u); // 无向图需要添加反向边
    }
    return G;
}

2. 图的深度优先遍历

深度优先遍历是一种递归算法，它从图的某个顶点开始遍历，沿着一条路径访问未访问过的顶点，直到到达最后一个顶点，然后回溯到前一个顶点，继续访问其他未访问过的顶点，直到所有顶点都被访问过。

下面是使用邻接表表示图的深度优先遍历的C++代码示例：

// 深度优先遍历
void DFS(Graph G, int v, vector<bool>& vis) {
    cout << G.Vex[v].data << "\t"; // 输出或存储
    vis[v] = true;
    AdjNode* p = G.Vex[v].first;
    while (p) {
        int w = p->v;
        if (!vis[w]) {
            DFS(G, w, vis);
        }
        p = p->next;
    }
}

// 深度优先遍历入口
void DFSTraverse(Graph G) {
    vector<bool> vis(G.vexNum, false); // 标记数组，记录每个顶点是否被访问过
    cout << "深度优先遍历结果：" << endl;
    for (int i = 0; i < G.vexNum; i++) {
        if (!vis[i]) {
            DFS(G, i, vis);
        }
    }
    cout << endl;
}