vector 邻接表

### 使用 `vector` 创建邻接表实现图结构 在 C++ 中，可以利用标准模板库（STL）中的 `vector` 容器来高效地创建和管理邻接表表示的图结构。以下是具体方法以及其实现细节。 #### 基本概念 邻接表是一种用于存储稀疏图的有效数据结构。它通过列表的形式记录每个顶点及其相邻顶点的信息。对于无向图而言，如果存在一条连接顶点 A 和 B 的边，则该边会同时出现在 A 和 B 对应的邻接链表中；而对于有向图来说，仅需在一侧添加即可[^1]。 #### 数据结构设计 采用 `vector<int>` 来保存每一个节点的所有邻居节点索引值。整个图则由一个二维动态数组即 `vector<vector<int>>` 表达出来。下面展示了一个简单的例子： ```cpp #include <iostream> #include <vector> using namespace std; // 构造函数初始化图大小并设置为n个空集合 void addEdge(vector<vector<int>>& adj, int u, int v){ adj[u].push_back(v); // 添加u到v的一条边 } int main(){ int V = 5; // 节点数量设为5 vector<vector<int>> adj(V); addEdge(adj, 0, 1); addEdge(adj, 0, 4); addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 3, 4); // 输出邻接表的内容 for(int i=0;i<V;i++){ cout << "Adjacency list of vertex "<<i<<": "; for(auto j : adj[i]){ cout << "-> " <<j; } cout << endl; } return 0; } ``` 上述程序展示了如何构建一个具有五个顶点的小型图，并打印其对应的邻接表形式。 #### 结构体方式扩展功能 当需要更复杂的功能比如带权边或者标记访问状态时，可引入自定义结构体配合使用。例如，在引用[2]的基础上稍作修改得到如下版本: ```cpp struct Edge { int dest; // 边的目标节点ID int weight; // 边上的权重 }; class Graph{ private: int numVertices; vector<vector<Edge>> adjacencyList; public: Graph(int vertices):numVertices(vertices),adjacencyList(vertices){}; void addWeightedEdge(int src,int dst,int wt){ Edge edge={dst,wt}; this->adjacencyList[src].emplace_back(edge); } void printGraph() const{ for (size_t i = 0; i < numVertices ; ++i ){ printf("\n Vertex %d:\n",i ); for(const auto &edge:this->adjacencyList.at(i)){ printf(" -> %d(wt=%d)",edge.dest ,edge.weight ); } } } }; ``` 此代码片段进一步增强了原生矢量模型的能力，使其能够处理加权边缘的情况[^2]。 #### 应用实例分析 考虑这样一个场景：给定一组城市之间相互可达的关系矩阵，要求找出任意两座城池间最短路径长度。此时便可借助前述技术搭建起完整的交通网络拓扑关系图表，再辅以Dijkstra算法求解最优路线问题[^3]。 ---

邻接表是一种表示图的数据结构，其中每个节点都对应着一个链表，存储与其相邻的节点。使用vector实现邻接表的步骤如下： 1. 定义一个vector<vector<int>>类型的变量adj_list，其中adj_list[i]表示与节点i相邻的节点列表。 2. 对于每个节点i，将其相邻的节点存储在adj_list[i]中，可以使用push_back()函数将相邻节点逐个加入adj_list[i]中。 下面是一个简单的使用vector实现邻接表的示例代码： ```c++ #include <iostream> #include <vector> using namespace std; int main() { int n, m; // n表示节点数，m表示边数 cin >> n >> m; vector<vector<int>> adj_list(n); // 定义邻接表 for (int i = 0; i < m; ++i) { int u, v; // u, v表示一条边的两个端点 cin >> u >> v; adj_list[u].push_back(v); // 将v加入u的邻接表中 adj_list[v].push_back(u); // 将u加入v的邻接表中（无向图） } // 遍历邻接表输出 for (int i = 0; i < n; ++i) { cout << "Node " << i << " is adjacent to: "; for (int j = 0; j < adj_list[i].size(); ++j) { cout << adj_list[i][j] << " "; } cout << endl; } return 0; } ``` 这段代码读入了节点数n和边数m，然后使用vector<vector<int>>类型的变量adj_list表示邻接表。对于每条边，使用push_back()函数将相邻节点加入对应的邻接表中。最后遍历邻接表输出结果。 需要注意的是，这里使用的是无向图的邻接表实现方式，如果是有向图，需要分别将每条边的起点和终点加入对应节点的邻接表中。