C++ 邻接表

2025 年 3 月 17 日 | 23 分钟阅读

在本文中，您将学习 C++ 中的邻接表及其不同的方法和实现。

图的表示

图是节点（顶点）和连接这些节点的边的集合。图可以分为各种类型，包括有向图和无向图、加权图和无权图、有环图和无环图等。为了对图执行操作或算法，需要以计算机可以有效操作的方式表示它们。

邻接表

邻接表是一种流行的图表示方法，尤其是在图是稀疏的（包含的边少于最大可能边数）时。在邻接表中，图中的每个顶点都与一个其相邻顶点的列表相关联。这种表示方法有效地捕获了图的连通性。

邻接表是一种表示图中顶点之间连接的数据结构。它特别适用于稀疏图，其中边的数量远小于总可能边的数量。在邻接表中，图中的每个顶点都与一个其相邻顶点的列表相关联。

在 C++ 中，您可以使用各种数据结构实现邻接表，例如链表数组、向量的向量，或从顶点到其邻居的映射。

有向图

有向图，也称为有向图，是一种图类型，其中边具有特定的方向，表示顶点之间的一对一关系。与无向图不同，无向图中的边表示顶点之间的连接而没有方向，有向图捕获元素之间的不对称关系或依赖性。

在有向图中，每条边都有一个起始顶点（尾部）和一个终止顶点（头部），由一个从尾部指向头部的箭头表示。这个箭头表示由边表示的关系或流的方向。方向的概念赋予有向图与无向图不同的特性和行为。

方法 1：使用列表数组（或向量）

让我们举一个例子来理解 C++ 中使用列表数组的邻接表。

#include <iostream>
#include <vector>
class DirectedGraph {
private:
 int numVertices;
 std::vector<std::vector<int>> adjacencyList;
public:
 DirectedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList.resize(vertices);
 }
 void addEdge(int src, int dest) {
 // Adding directed edge from src to dest
 adjacencyList[src].push_back(dest);
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " has outgoing edges to: ";
 for (int neighbor : adjacencyList[i]) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 DirectedGraph graph(5);
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

输出

Vertex 0 has outgoing edges to: 1 3 
Vertex 1 has outgoing edges to: 2 
Vertex 2 has outgoing edges to: 3 4 
Vertex 3 has outgoing edges to: 4 
Vertex 4 has outgoing edges to:

说明

在此示例中，DirectedGraph 类使用向量数组来创建邻接表。addEdge 函数从源顶点到目标顶点添加有向边。printGraph 函数显示每个顶点的邻接表。
箭头表示边的方向。
顶点内的数字对应于顶点编号。
每个顶点指向其出度邻居。
它表示一个有向图，其中有向边从源顶点指向目标顶点。

有向图可视化

0 --> 1

| |

v v

3 --> 2 --> 4

说明

该代码定义了一个有向图类，它使用邻接表对有向图进行建模。
该类有一个私有成员变量 numVertices，用于存储顶点数，以及一个邻接表用于存储邻接表。
构造函数初始化numVertices并调整邻接表向量的大小以匹配顶点数。
addEdge 方法通过将目标顶点推入邻接表中对应于源顶点的向量来向图中添加有向边。
printGraph 方法打印邻接表表示。它遍历每个顶点，打印其出度邻居。
在main 函数中，创建了一个名为 graph 的DirectedGraph实例，包含5 个顶点。
使用addEdge 方法向图中添加各种边，定义有向关系。
最后，调用printGraph 方法显示有向图的邻接表表示。
程序的结果是显示有向图邻接表的输出，指示每个顶点连接到哪些顶点。

复杂度分析

时间复杂度

构造函数 (DirectedGraph)：O(V)，其中V是顶点数。

addEdge 函数：O(1)，因为添加边涉及向顶点的邻接表追加。

printGraph 函数：O(V + E)，其中V是顶点数，E是边数。这是因为它遍历每个顶点及其邻居。

主函数：O(E)，其中E是边数，因为我们在主函数中添加边。

空间复杂度

构造函数 (DirectedGraph)：O(V + E)，因为它初始化adjacencyList向量以及其中每个向量的边。

addEdge 函数：每条边 O(1)，因为它只将元素追加到向量。

printGraph 函数：O(V + E)，由于邻接表及其向量的存储。

主函数：O(V + E) 涉及创建图对象和添加边。

其中

V是顶点数。

E是图中的边数。

方法 2：使用从顶点到邻居的映射

让我们举一个例子来理解 C++ 中使用从顶点到邻居的映射的邻接表。

#include <iostream>
#include <map>
#include <vector>
class DirectedGraph {
private:
 int numVertices;
 std::map<int, std::vector<int>> adjacencyList;
public:
 DirectedGraph(int vertices) {
 numVertices = vertices;
 }
 void addEdge(int src, int dest) {
 // Adding directed edge from src to dest
 adjacencyList[src].push_back(dest);
 }
 void printGraph() {
 for (const auto& vertex : adjacencyList) {
 std::cout << "Vertex " << vertex.first << " has outgoing edges to: ";
 for (int neighbor : vertex.second) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 DirectedGraph graph(5);
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

输出

Vertex 0 has outgoing edges to: 1 3 
Vertex 1 has outgoing edges to: 2 
Vertex 2 has outgoing edges to: 3 4 
Vertex 3 has outgoing edges to: 4

以下是使用从顶点到邻居的映射的有向图的可视化表示

有向图可视化

顶点 0 --> [1] 顶点 1 --> [2]

| |

v v

顶点 3 --> [4] 顶点 2 --> [3, 4]

顶点 4 --> []

说明

在此示例中，代码定义了一个有向图类，它使用从顶点到其邻居顶点的映射来表示有向图。该映射存储为名为adjacencyList的私有成员变量。
构造函数初始化顶点数。
addEdge 函数通过将目标顶点追加到邻接列表映射中与源顶点键关联的向量来添加从源顶点到目标顶点的有向边。
printGraph 函数通过遍历映射并显示每个顶点的出边来打印图的邻接列表表示。
在main 函数中，创建了一个名为 graph 的DirectedGraph对象，包含5 个顶点。使用addEdge向图中添加边以创建有向图结构。
之后，调用printGraph函数显示图的邻接表表示，显示每个顶点连接到哪些顶点。

复杂度分析

时间复杂度

构造函数 (DirectedGraph)：O(V)，其中 V 是顶点数。

addEdge 函数：O(1)，因为添加边涉及向顶点的邻接表追加。

printGraph 函数：O(V + E)，其中V是顶点数，E是边数。这是因为它遍历每个顶点及其邻居。

主函数：O(E)，其中 E 是边数，因为我们在主函数中添加边。

空间复杂度

构造函数 (DirectedGraph)：O(V)，因为它初始化adjacencyList map来存储顶点映射。

addEdge 函数：O(E)，其中E是图中的边数，因为我们将所有边存储在邻接列表中。

printGraph 函数：O(V + E)，由于邻接表及其向量的存储。

主函数：O(V + E) 涉及创建图对象和添加边。

其中

V是顶点数。

E是图中的边数。

无向图

无向图是图论中的一个基本概念，它表示顶点（节点）和边（连接）的集合，其中边没有特定的方向。换句话说，顶点之间的关系是对称的——如果一条边将顶点 A连接到顶点 B，它也意味着从顶点 B到顶点 A有一条边。

方法 1：使用列表数组（或向量）

让我们举一个例子来理解 C++ 中使用列表数组的邻接表。

#include <iostream>
#include <vector>
class UndirectedGraph {
private:
 int numVertices;
 std::vector<std::vector<int>> adjacencyList;
public:
 UndirectedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList.resize(vertices);
 }
 void addEdge(int src, int dest) {
 // Adding undirected edge between src and dest
 adjacencyList[src].push_back(dest);
 adjacencyList[dest].push_back(src);
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " is connected to: ";
 for (int neighbor : adjacencyList[i]) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 UndirectedGraph graph(5);
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

输出

0 is connected to: 1 3 
Vertex 1 is connected to: 0 2 
Vertex 2 is connected to: 1 3 4 
Vertex 3 is connected to: 0 2 4 
Vertex 4 is connected to: 2 3

每个数字代表一个顶点。

顶点之间的线表示边。

该图是无向的，因此边表示顶点之间的相互连接。

说明

在此示例中，代码定义了一个UndirectedGraph类，它使用邻接表表示无向图。
该类有一个私有成员numVertices用于存储顶点数，以及一个邻接表用于存储邻接表。
构造函数初始化numVertices并调整邻接表向量的大小以匹配顶点数。
addEdge 方法通过更新两个顶点的邻接表来添加两个顶点之间的无向边。
printGraph 方法遍历顶点并打印它们的邻居，显示邻接表。
在main 函数中创建了一个名为 graph 的UndirectedGraph实例，包含5 个顶点。
使用addEdge 方法添加边以创建无向图中的连接。
调用printGraph 方法显示图的邻接表表示。

复杂度分析

时间复杂度

构造函数 (UndirectedGraph)：O(V)，其中V是顶点数。

addEdge 函数：O(1)，因为添加边涉及向两个顶点的邻接表追加。

printGraph 函数：O(V + E)，其中 V 是顶点数，E是边数。这是因为它遍历每个顶点及其邻居。

主函数：O(E)，其中E是边数，因为我们在主函数中添加边。

空间复杂度

构造函数 (UndirectedGraph)：O(V)，因为它调整邻接表向量的大小以匹配顶点数。

addEdge 函数：每条边 O(1)，因为它只将元素追加到向量。

printGraph 函数：O(V + E)，由于邻接表的存储。

主函数：O(V + E) 涉及创建图对象和添加边。

其中

V是顶点数。

E是图中的边数。

方法 2：使用双端队列数组

我们使用双端队列数组（双端队列），其中每个双端队列包含整数来表示无向图。每个双端队列中的整数表示与当前顶点共享边的相邻顶点。这种表示适用于无向图，其中边没有方向，并且双向连接顶点。

#include <iostream>
#include <deque>
class UndirectedGraph {
private:
 int numVertices;
 std::deque<int>* adjacencyList;
public:
 UndirectedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList = new std::deque<int>[vertices];
 }
 void addEdge(int src, int dest) {
 adjacencyList[src].push_back(dest);
 adjacencyList[dest].push_back(src); // For undirected graphs
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " is connected to: ";
 for (int neighbor : adjacencyList[i]) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
 ~UndirectedGraph() {
 delete[] adjacencyList;
 }
};
int main() {
 UndirectedGraph graph(5);
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

输出

Vertex 0 is connected to: 1 3 
Vertex 1 is connected to: 0 2 
Vertex 2 is connected to: 1 3 4 
Vertex 3 is connected to: 0 2 4 
Vertex 4 is connected to: 2 3

说明

在此示例中，代码定义了一个名为UndirectedGraph的类来表示无向图。
该类包含一个私有成员变量 numVertices，用于存储图中的顶点数。
邻接表实现为双端队列（双端队列）数组，其中每个双端队列表示图中的一个顶点。
类构造函数将顶点数作为参数并初始化numVertices 变量。
它为双端队列数组动态分配内存，每个双端队列对应于图中的一个顶点。
addEdge 方法允许在两个顶点（src和dest）之间建立无向边。
它将整数推入与源顶点和目标顶点关联的双端队列中。此操作确保图是无向的，双向添加边。
printGraph 方法用于显示图的邻接表表示。
它遍历图中的每个顶点（从0到numVertices - 1）并打印存储在相关双端队列中的邻居。
该类包含一个析构函数，用于在对象销毁时释放双端队列数组的动态分配内存。
在main 函数中，创建了一个UndirectedGraph 类的实例，包含5 个顶点。
使用addEdge 方法向图中添加了几条边以建立顶点之间的连接。
最后，printGraph 方法显示无向图的邻接表表示。

复杂度分析

时间复杂度

创建双端队列数组的时间复杂度为O(V)，其中 V 是顶点数。
之后，将整数推入双端队列需要常数时间，O(1)。
在两个顶点（src和dest）之间添加边会导致无向图的两次常数时间操作（每个方向一次）。
如果有E 条边，添加边的总时间复杂度为O(E)。
该方法遍历每个顶点 (V)及其邻居 (E)，导致时间复杂度为O(V + E)。
删除双端队列数组需要O(V)时间复杂度。
总的来说，时间复杂度由添加边和打印图支配，使其为O(V + E)。

空间复杂度

双端队列数组的空间复杂度为O(V)，其中 V 是顶点数。
对于每条边，存储两个整数（表示邻居），在无向图中每个方向一个。
如果有E 条边，存储整数的空间复杂度为O(2E)，简化为O(E)。
总空间复杂度是双端队列数组和其中整数所用空间的总和，即O(V + E)。

方法 3：使用从顶点到邻居的映射

这是一个如何使用从顶点到其邻居的映射在 C++ 中表示无向图的示例

#include <iostream>
#include <map>
#include <set>
class UndirectedGraph {
private:
 std::map<int, std::set<int>> adjacencyList;

public:
 void addEdge(int src, int dest) {
 // Adding undirected edge between src and dest
 adjacencyList[src].insert(dest);
 adjacencyList[dest].insert(src);
 }
 void printGraph() {
 for (const auto& vertex : adjacencyList) {
 std::cout << "Vertex " << vertex.first << " is connected to: ";
 for (int neighbor : vertex.second) {
 std::cout << neighbor << " ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 UndirectedGraph graph;
 graph.addEdge(0, 1);
 graph.addEdge(0, 3);
 graph.addEdge(1, 2);
 graph.addEdge(2, 3);
 graph.addEdge(2, 4);
 graph.addEdge(3, 4);
 graph.printGraph();
 return 0;
}

输出

Vertex 0 is connected to: 1 3 
Vertex 1 is connected to: 0 2 
Vertex 2 is connected to: 1 3 4 
Vertex 3 is connected to: 0 2 4 
Vertex 4 is connected to: 2 3

说明

在此示例中，代码定义了一个名为UndirectedGraph的类，它使用从顶点到其邻居的映射来表示无向图。它还使用 C++ 标准库的std::set来按排序顺序存储邻居。
UndirectedGraph类中的addEdge 方法向图中添加无向边。它接受两个顶点索引src和dest，并使用std::set将两个顶点添加到彼此的邻接列表中，以确保邻居按排序顺序存储。这样，相同的边不会多次添加。
printGraph 方法用于打印图的邻接表。它遍历邻接列表（adjacency list）中的每个顶点，并打印与每个顶点关联的邻居。
创建了UndirectedGraph 类的一个实例，名为 graph。
使用addEdge 方法向图中添加了几条无向边。
调用printGraph 方法显示图的邻接表表示。
该代码着重于使用映射和排序集来维护无向图的清晰邻接表表示。

复杂度分析

时间复杂度

将元素插入到std::set中需要O(log N)时间，其中N是顶点的邻居数。由于每个边都涉及将两个顶点添加到各自的集合中，因此添加所有边的总时间复杂度将是O(E * log V)，其中E是边数，V 是顶点数。
此函数遍历邻接列表中的每个顶点及其关联的邻居，这需要O(V + E) 时间，其中V是顶点数，E是边数。
添加边需要O(E * log V)时间。

空间复杂度

邻接列表和集合的存储决定了空间复杂度：

邻接列表所需的空间为O(V + E)，其中V是顶点数，E是边数。
每个邻居集合使用O(N) 空间，其中N是每个顶点的平均邻居数。
总体空间复杂度为O(V + E + V * N)，如果平均邻居数不显著大于顶点数，则简化为O(V + E)。

加权图

加权图是一种图，其中每条边都带有一个数值，称为“权重”。此权重表示与边连接的两个顶点之间的连接相关联的某些属性、成本、距离或值的定量度量。换句话说，分配给边的权重提供了有关它连接的顶点之间关系的附加信息。

在加权图中

每个边都有一个关联的权重，表示各种量，如距离、成本、时间、容量或任何其他相关度量。
权重可以是正数、负数或零，具体取决于上下文和权重的含义。
加权图用于建模节点之间关系具有不同程度的重要性、成本或影响的场景。

例如，考虑一个场景，其中顶点表示城市，边表示它们之间的道路。在这种情况下，边上的权重可以表示城市之间的距离。同样，在金融网络中，权重表示账户之间的交易金额。加权图用途广泛，在交通、社交网络、网络路由和资源分配等各个领域都有应用。

方法 1：使用列表数组（或向量）

这是一个如何使用向量数组在 C++ 中表示加权图以存储邻接表的示例

#include <iostream>
#include <vector>
class WeightedGraph {
private:
 int numVertices;
 std::vector<std::vector<std::pair<int, int>>> adjacencyList;
public:
 WeightedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList.resize(vertices);
 }
 void addEdge(int src, int dest, int weight) {
 // Adding weighted edge from src to dest with a given weight
 adjacencyList[src].emplace_back(dest, weight);
 // Uncomment the line below for an undirected graph
 // adjacencyList[dest].emplace_back(src, weight);
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " is connected to: ";
 for (const auto& neighbor : adjacencyList[i]) {
 std::cout << neighbor.first << " (Weight: " << neighbor.second << ") ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 WeightedGraph graph(5);
 graph.addEdge(0, 1, 2);
 graph.addEdge(0, 3, 5);
 graph.addEdge(1, 2, 3);
 graph.addEdge(2, 3, 1);
 graph.addEdge(2, 4, 4);
 graph.addEdge(3, 4, 6);
 graph.printGraph();
 return 0;
}

输出

Vertex 0 is connected to: 1 (Weight: 2) 3 (Weight: 5) 
Vertex 1 is connected to: 2 (Weight: 3) 
Vertex 2 is connected to: 3 (Weight: 1) 4 (Weight: 4) 
Vertex 3 is connected to: 4 (Weight: 6) 
Vertex 4 is connected to:

说明

在此示例中，代码定义了一个名为WeightedGraph的类，它使用向量数组来表示加权图以存储邻接表。邻接表的每个元素都是一个包含表示目标顶点和边权重的对的向量。
构造函数初始化顶点数并相应地调整邻接表向量的大小。
addEdge 方法允许向图中添加加权边。它将源顶点、目标顶点和权重作为输入。该方法将包含目标顶点和权重的对追加到邻接列表中源顶点位置的向量中。此外，我们可以取消注释相应的行以添加无向图的反向边。
printGraph 方法用于显示图的邻接表表示。它遍历邻接列表中的每个顶点及其关联的邻居（对），并打印目标顶点以及边的权重。
在main 函数中创建了一个WeightedGraph类的实例，名为 graph。使用 addEdge 方法向图中添加了几条加权边。之后，调用printGraph 方法显示图的邻接表表示，显示顶点之间的连接以及关联的边权重。
此代码演示了如何使用向量数组表示加权图并将边权重合并到图结构中。

复杂度分析

时间复杂度

添加边涉及向源顶点的邻接表追加，这需要O(1) 时间。
此函数遍历邻接列表中的每个顶点及其关联的邻居（对），导致时间复杂度为O(V + E)，其中V是顶点数，E是边数。
使用addEdge 方法添加边需要O(E) 时间。

空间复杂度

空间复杂度由邻接表和表示边的对的存储决定

邻接列表所需的空间为O(V + E)，其中V是顶点数，E是边数。
表示边的每个对使用O(1) 空间。
由于邻接表和对，总体空间复杂度为O(V + E)。

其中

V是顶点数。

E是图中的边数。

方法 2：使用从顶点到邻居的映射

这是一个如何使用从顶点到其邻居的映射（其中每个邻居都与权重相关联）来表示加权图的示例

#include <iostream>
#include <map>
class WeightedGraph {
private:
 std::map<int, std::map<int, int>> adjacencyList;
public:
 void addEdge(int src, int dest, int weight) {
 // Adding weighted edge from src to dest with a given weight
 adjacencyList[src][dest] = weight;
 // Uncomment the line below for an undirected graph
 // adjacencyList[dest][src] = weight;
 }
 void printGraph() {
 for (const auto& vertex : adjacencyList) {
 std::cout << "Vertex " << vertex.first << " is connected to: ";
 for (const auto& neighbor : vertex.second) {
 std::cout << neighbor.first << " (Weight: " << neighbor.second << ") ";
 }
 std::cout << "\n";
 }
 }
};
int main() {
 WeightedGraph graph;
 graph.addEdge(0, 1, 2);
 graph.addEdge(0, 3, 5);
 graph.addEdge(1, 2, 3);
 graph.addEdge(2, 3, 1);
 graph.addEdge(2, 4, 4);
 graph.addEdge(3, 4, 6);
 graph.printGraph();
 return 0;
}

输出

Vertex 0 is connected to: 1 (Weight: 2) 3 (Weight: 5) 
Vertex 1 is connected to: 2 (Weight: 3) 
Vertex 2 is connected to: 3 (Weight: 1) 4 (Weight: 4) 
Vertex 3 is connected to: 4 (Weight: 6)

说明

在此示例中，代码定义了一个名为WeightedGraph的类，它使用从顶点到邻居的映射来表示加权图，其中每个邻居都与权重相关联。
addEdge 方法允许向图中添加加权边。它将源顶点、目标顶点和权重作为输入。该方法更新与源顶点关联的内部映射，以将目标顶点作为邻居以及边的权重包含在内。您可以取消注释相应的行以添加无向图的反向边。
printGraph 方法用于显示图的邻接表表示。它遍历外部映射中的每个顶点及其关联的邻居（内部映射）以打印目标顶点和边的权重。

在主函数中

创建了WeightedGraph类的一个实例。
使用addEdge 方法向图中添加了几条加权边。
之后，调用printGraph 方法显示图的邻接表表示，显示顶点之间的连接以及关联的边权重。

复杂度分析

时间复杂度

添加边涉及更新与源顶点关联的内部映射，这需要O(log N) 时间，其中N是顶点的平均邻居数。
此函数遍历邻接列表中的每个顶点及其关联的邻居（内部映射），导致时间复杂度为O(V + E)，其中V是顶点数，E是边数。
使用addEdge方法添加边需要O(E * log N) 时间。

空间复杂度

空间复杂度由邻接表和表示边的映射的存储决定

邻接列表所需的空间为O(V + E)，其中V是顶点数，E是边数。
与顶点关联的每个内部映射使用O(N) 空间，其中N是顶点的平均邻居数。
总体空间复杂度为O(V + E + V * N)，如果N不显著大于顶点数，则简化为O(V + E + E * log N)或简单地O(V + E)。

方法 3：使用双端队列数组

我们使用包含整数对的双端队列数组（双端队列）来表示加权图。每对中的整数表示邻居顶点以及连接当前顶点与其邻居的边的权重。

#include <iostream>
#include <deque>
class WeightedGraph {
private:
 int numVertices;
 std::deque<std::pair<int, int>>* adjacencyList;
public:
 WeightedGraph(int vertices) {
 numVertices = vertices;
 adjacencyList = new std::deque<std::pair<int, int>>[vertices];
 }
 void addEdge(int src, int dest, int weight) {
 adjacencyList[src].push_back(std::make_pair(dest, weight));
 adjacencyList[dest].push_back(std::make_pair(src, weight)); // For undirected graphs
 }
 void printGraph() {
 for (int i = 0; i < numVertices; ++i) {
 std::cout << "Vertex " << i << " is connected to: ";
 for (const auto& neighbor : adjacencyList[i]) {
 std::cout << neighbor.first << " (Weight: " << neighbor.second << ") ";
 }
 std::cout << "\n";
 }
 }
 ~WeightedGraph() {
 delete[] adjacencyList;
 }
};
int main() {
 WeightedGraph graph(5);
 graph.addEdge(0, 1, 2);
 graph.addEdge(0, 3, 5);
 graph.addEdge(1, 2, 3);
 graph.addEdge(2, 3, 1);
 graph.addEdge(2, 4, 4);
 graph.addEdge(3, 4, 6);
 graph.printGraph();
 return 0;
}

输出

Vertex 0 is connected to: 1 (Weight: 2) 3 (Weight: 5) 
Vertex 1 is connected to: 0 (Weight: 2) 2 (Weight: 3) 
Vertex 2 is connected to: 1 (Weight: 3) 3 (Weight: 1) 4 (Weight: 4) 
Vertex 3 is connected to: 0 (Weight: 5) 2 (Weight: 1) 4 (Weight: 6) 
Vertex 4 is connected to: 2 (Weight: 4) 3 (Weight: 6)

说明

在此示例中，代码定义了一个名为加权图的类来表示加权图。
它包含一个私有成员变量 numVertices，用于存储图中的顶点数。
类构造函数将顶点数作为参数并初始化numVertices 变量。
它为双端队列数组动态分配内存，其中每个双端队列对应于图中的一个顶点。
邻接表实现为包含整数对的双端队列数组。每对由邻居顶点和连接当前顶点与该邻居的边的权重组成。
addEdge 方法允许在两个顶点（src和dest）之间添加具有指定权重的加权边。
它将一对推入与源顶点和目标顶点关联的双端队列中。此对包括邻居顶点 (dest)和连接当前顶点 (src)与该邻居的边权重。
对于无向图，它还添加反向边以确保顶点之间的对称关系。
printGraph 方法用于显示图的邻接表表示。
它遍历图中的每个顶点（从0到numVertices - 1）并打印邻居及其关联的边权重。
该类包含一个析构函数，用于在对象销毁时释放双端队列数组的动态分配内存。
在主函数中，创建了WeightedGraph类的一个实例，并使用addEdge 方法向图中添加了几条加权边。最后，调用printGraph 方法显示图的邻接表表示，包括顶点、它们的邻居和边权重。
此代码使用双端队列数组提供了加权图的清晰高效表示。它适用于加权边和高效邻居遍历至关重要的各种应用程序。

复杂度分析

时间复杂度

创建双端队列数组的时间复杂度为O(V)，其中 V 是顶点数。
将一对推入双端队列需要常数时间，O(1)。
在两个顶点之间添加边会导致无向图的两次常数时间操作。
如果有E 条边，添加边的总时间复杂度为O(E)。
该方法遍历每个顶点及其邻居，导致时间复杂度为O(V + E)，其中V是顶点数，E 是边数。
删除双端队列数组需要O(V)。
因此，时间复杂度主要由添加边和打印图支配，使其为O(V + E)。

空间复杂度

双端队列数组的空间复杂度为O(V)，其中 V 是顶点数。
对于每个边，对于无向图，一对（邻居顶点，边权重）存储两次。
如果有E 条边，存储对的空间复杂度为O(2E)，简化为O(E)。
总空间复杂度是双端队列数组和双端队列中对所用空间的总和，即O(V + E)。

邻接表应用

邻接表由于其在各种应用中的效率，是一种常用的图表示方法。以下是邻接表的一些常见应用

社交网络：在Facebook、Twitter和LinkedIn等社交网络中，每个用户都可以表示为一个顶点，他们的连接（友谊、关注者等）可以使用邻接表表示。

推荐系统：许多推荐算法使用图结构推荐项目、产品或朋友。邻接表表示有助于建模用户或项目之间的关系和连接，从而实现更准确的推荐。

路由和网络：在计算机网络中，邻接表表示网络的拓扑。它们有助于找到最短路径、优化数据路由并有效管理网络资源。

游戏开发：在视频游戏开发中，邻接表可用于建模游戏世界，其中顶点表示位置或场景，边表示场景之间可能的转换。

数据挖掘和聚类：在聚类算法中，邻接表可以表示数据点之间的相似关系。每个顶点表示一个数据点，边表示相似性度量。

图算法：许多图算法，如深度优先搜索 (DFS)、广度优先搜索 (BFS)、Dijkstra 算法和Prim 算法，与邻接表表示一起工作效率很高。这种表示允许快速访问邻居及其相关信息。

好处

内存效率：邻接表对于稀疏图来说内存效率高，因为它们只存储有关现有边的信息。这使得它们适用于边数少于最大可能边数的图。

遍历便捷性：使用邻接表遍历顶点的邻居非常简单。遍历顶点的邻接表所需时间仅等于邻居数，这使得某些图算法效率更高。

动态图：邻接表非常适合图结构不断演变的情况。添加或删除边或顶点可以高效完成，而不会影响整个数据结构。

具有可变连通性的应用程序：当顶点之间的连通性程度差异很大时，邻接表在内存使用方面比邻接矩阵更有效。

局限性

空间复杂度（稠密图）：对于稠密图（边很多），邻接表的空间复杂度可能高于邻接矩阵。在这种情况下，它们的内存效率会降低。

邻居查找时间：虽然邻接表对于遍历邻居来说效率很高，但查找两个顶点是否直接连接（边存在）需要O(度) 时间，其中度是平均邻居数。

边权重检索：在加权图中，邻接表需要额外的空间来存储边权重。由于需要搜索特定邻居，检索边权重可能需要额外时间。

边删除：从邻接表中删除边需要搜索并可能调整列表大小。此操作可能不如邻接矩阵中的边删除效率高。

图表示权衡：邻接表和矩阵之间的选择取决于特定的图特性和执行的操作类型。由于常数时间边存在检查，某些算法可能对矩阵更有效。

下一主题C++ 中的 Make_pair

C++ 邻接表

图的表示

邻接表

有向图

方法 1：使用列表数组（或向量）

方法 2：使用从顶点到邻居的映射

无向图

方法 1：使用列表数组（或向量）

方法 2：使用双端队列数组

方法 3：使用从顶点到邻居的映射

加权图

在加权图中

方法 1：使用列表数组（或向量）

方法 2：使用从顶点到邻居的映射

方法 3：使用双端队列数组

邻接表应用

好处

局限性

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 邻接表

图的表示

邻接表

有向图

方法 1：使用列表数组（或向量）

方法 2：使用从顶点到邻居的映射

无向图

方法 1：使用列表数组（或向量）

方法 2：使用双端队列数组

方法 3：使用从顶点到邻居的映射

加权图

在加权图中

方法 1：使用列表数组（或向量）

方法 2：使用从顶点到邻居的映射

方法 3：使用双端队列数组

邻接表应用

好处

局限性

相关帖子

C++ 名称修饰和 extern C 概念

C++ feholdexcept()

C++ 二分法