本文共 1815 字，大约阅读时间需要 6 分钟。

在数据结构中，图的存储方法主要分为邻接矩阵、邻接表和边集三种形式，其中邻接表和邻接矩阵较为常用。对于初学者来说，直接使用邻接表可能会比较复杂，涉及到多个结构体的嵌套，因此在学习过程中，通常会选择一个更简单的工具来辅助实现。

下面是具体的实现过程：

由于vector的灵活性，可以通过创建一个顶点数为N的邻接表数组Adj[N]来存储图的邻接信息。这样可以根据实际图的边数动态分配存储空间，每个顶点对应的邻接列表可以通过vector来实现。

如果只需要存储每条边的终点编号，可以直接将邻接表的元素类型设为int，如vector

struct Node {    int v;    int weight;};

这样，添加一条从顶点1到顶点3的有向边，边权为4，只需创建一个Node实例temp，设定temp.v = 3，temp.weight = 4，然后将temp加入Adj[1]即可，代码如下：

Node temp;temp.v = 3;temp.weight = 4;Adj[1].push_back(temp);

测试数据示例：

560 1 10 2 20 3 31 4 42 4 23 4 5

下面是使用vector实现邻接表存储有向有权图并进行深度优先搜索的完整代码：

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct Node {    int v;    int weight;};vector
      
       
        > Adj;bool vis[MAX_SIZE] = {false};void dfs(int u) {    vis[u] = true;    cout << u << " ";    for (int i = 0; i < Adj[u].size(); i++) {        Node node = Adj[u][i];        int v = node.v;        if (!vis[v]) {            dfs(v);        }    }}int n, edges;int main() {    cout << "输入图中的顶点数: ";    cin >> n;    cout << endl;    cout << "输入图中的边数: ";    cin >> edges;    cout << endl;    cout << "输入图中的边信息（起始顶点, 结束顶点, 边权重）：" << endl;    for (int i = 0; i < edges; i++) {        cin >> u >> v >> weight;        Node newNode;        newNode.v = v;        newNode.weight = weight;        Adj[u].push_back(newNode);    }        // 输出邻接表结构    for (int i = 0; i < n; i++) {        if (!Adj[i].empty()) {            cout << i << " ";            for (int j = 0; j < Adj[i].size(); j++) {                Node pop = Adj[i][j];                cout << pop.v << " ";            }            cout << endl;        }    }        cout << "深度优先搜索顶点的结果如下: " << endl;    dfs(0);    return 0;}
       
      
     
    
   

以上代码实现了一个邻接表存储的有向有权图，并通过深度优先搜索算法遍历图中的顶点。通过输入图的顶点数和边数，以及每条边的起始顶点、结束顶点和权重，可以完成对图的构建和遍历。

转载地址：http://gewg.baihongyu.com/