【CS.DS】数据结构 —— 图：深入了解三种表示方法之邻接表(Adjacency List)

数据结构

1 概念

• 优点：空间效率高，适合稀疏图。动态性强，可以方便地添加或删除边。

  • 邻接表表示法是一种高效表示稀疏图的方式。//

• 缺点：查找某条边是否存在的时间复杂度较高。

• 示例：

A: B -> D
B: A -> C -> D
C: B
D: A -> B
1
2
3
4

• 示例解释：顶点 A 连接到 B 和 D，顶点 B 连接到 A、C 和 D，以此类推。

2 无向图的邻接表

2.1 示例

假设有以下无向图，其中节点 A、B、C、D、E 表示城市，边表示城市之间的道路，权重表示道路的距离。

在邻接表（链式）表示法中，图的边权重是预先给定的，而不是通过某种计算得到的。它们通常是图的定义的一部分，表示从一个顶点到另一个顶点的距离、时间或其他成本。例如，在地图中的路径权重可以表示两个地点之间的距离。

    A----3----B
    |         |
    4         2
    |         |
    C----1----D
    |     
    5     
    |
    E 
1
2
3
4
5
6
7
8
9

对应的邻接表为：

A -> B(3) -> C(4)
B -> A(3) -> D(2)
C -> A(4) -> D(1) -> E(5)
D -> B(2) -> C(1)
E -> C(5)
1
2
3
4
5

2.2 Mermaid 图示例

e.g. 顶点 A 的邻接表：

• 顶点 A 连接到顶点 B，边的权重是 3。
• 顶点 A 再连接到顶点 C，边的权重是 4。
• 最后一个节点指向 ^ 表示链表结束。

2.3 C++实现

2.3.1 简单实现

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 表示图的结构: `Edge` 结构体表示图的边，包括目的顶点 `dest`、边的权重 `weight` 和指向下一条边的指针 `next`。
struct Edge {
    int dest;   // 目的顶点
    int weight; // 边的权重
    Edge* next; // 指向下一条边的指针
};

// `Vertex` 结构体表示图的顶点，包括顶点数据 `data` 和指向第一个相邻顶点的指针 `first`。
struct Vertex {
    char data;    // 顶点数据
    Edge* first; // 指向第一个相邻顶点的指针
};

// 初始化图: `addEdge` 函数用于向图中添加边，每次添加新边时，会将其插入到链表的头部。
void addEdge(Vertex vertices[], int src, int dest, int weight) {
    Edge* newEdge = new Edge{dest, weight, vertices[src].first};
    vertices[src].first = newEdge;
}

void printGraph(Vertex vertices[], int V) {
    for (int i = 0; i < V; ++i) {
        cout << "顶点 " << vertices[i].data << " 的邻接表: ";
        Edge* edge = vertices[i].first;
        while (edge) {
            cout << " -> " << vertices[edge->dest].data << " (权重 " << edge->weight << ")";
            edge = edge->next;
        }
        cout << endl;
    }
}

int main() {
    const int V = 5;
    Vertex vertices[V] = {{'A', nullptr}, {'B', nullptr}, {'C', nullptr}, {'D', nullptr}, {'E', nullptr}};

    // 根据图添加边
    addEdge(vertices, 0, 1, 3); // A -> B
    addEdge(vertices, 0, 2, 4); // A -> C
    
    addEdge(vertices, 1, 0, 3); // B -> A
    addEdge(vertices, 1, 3, 2); // B -> D

    addEdge(vertices, 2, 0, 4); // C -> A
    addEdge(vertices, 2, 3, 1); // C -> D
    addEdge(vertices, 2, 4, 5); // C -> E

    addEdge(vertices, 3, 1, 2); // D -> B
    addEdge(vertices, 3, 2, 1); // D -> C

    addEdge(vertices, 4, 2, 5); // E -> C

    printGraph(vertices, V);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

封装实现:
优点：

• 直接性：直接使用链表来表示邻接表，比较直观。
• 高效性：链表的插入操作比较高效。
  缺点：
• 复杂性：需要手动管理内存，容易出现内存泄漏问题。
• 灵活性：不如 STL 容器灵活，操作起来相对繁琐。

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

struct Edge {
    int dest;
    int weight;
    Edge* next;
};

struct Vertex {
    char data;
    Edge* first;
};

class Graph {
public:
	// 构造函数，初始化顶点数量和顶点数组
    Graph(int vertices) : V(vertices) {
        vertex_list = new Vertex[V];
        for (int i = 0; i < V; ++i) {
            vertex_list[i].data = 'A' + i;
            vertex_list[i].first = nullptr;
        }
    }
	// 析构函数，释放所有动态分配的内存
    ~Graph() {
        for (int i = 0; i < V; ++i) {
            Edge* current = vertex_list[i].first;
            while (current) {
                Edge* temp = current;
                current = current->next;
                delete temp;
            }
        }
        delete[] vertex_list;
    }

    void AddEdge(int src, int dest, int weight) {
        Edge* newEdge = new Edge{dest, weight, vertex_list[src].first};
        vertex_list[src].first = newEdge;
    }

    void PrintGraph() const {
        for (int i = 0; i < V; ++i) {
            cout << "顶点 " << vertex_list[i].data << " 的邻接表: ";
            Edge* edge = vertex_list[i].first;
            while (edge) {
                cout << " -> " << vertex_list[edge->dest].data << " (权重 " << edge->weight << ")";
                edge = edge->next;
            }
            cout << endl;
        }
    }

private:
    int V;
    Vertex* vertex_list;
};

int main() {
    Graph g(5);

    // 根据图添加边  
    g.AddEdge(0, 1, 3); // A -> B  
    g.AddEdge(0, 2, 4); // A -> C  
  
    g.AddEdge(1, 0, 3); // B -> A  
    g.AddEdge(1, 3, 2); // B -> D  
  
    g.AddEdge(2, 0, 4); // C -> A  
    g.AddEdge(2, 3, 1); // C -> D  
    g.AddEdge(2, 4, 5); // C -> E  
  
    g.AddEdge(3, 1, 2); // D -> B  
    g.AddEdge(3, 2, 1); // D -> C  
  
    g.AddEdge(4, 2, 5); // E -> C  

    g.PrintGraph();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

执行后, 输出如下:

顶点 A 的邻接表:  -> C (权重 4) -> B (权重 3) # 对于顶点 `A` 的邻接表：A -> C(4) -> B(3) 或者 A -> B(3) -> C(4) 都是正确的，它们表示的图结构是一样的。关键在于每个顶点的邻接节点及其对应的边权重是否正确记录。
顶点 B 的邻接表:  -> D (权重 2) -> A (权重 3)
顶点 C 的邻接表:  -> E (权重 5) -> D (权重 1) -> A (权重 4)
顶点 D 的邻接表:  -> C (权重 1) -> B (权重 2)
顶点 E 的邻接表:  -> C (权重 5)
1
2
3
4
5

2.3.2 优化封装

优点：

• 简洁性：代码更简洁，易于阅读和维护。
• 内存管理：使用 STL 容器，不需要手动管理内存，减少内存泄漏风险。
• 灵活性：STL 容器操作更灵活，提供了更多的功能。
  缺点：
• 抽象程度：链表的表示方式被隐藏在 STL 容器中，可能不够直观。

#include <iostream>
#include <vector>

class Graph {
public:
    Graph(int vertices)
        : vertices_(vertices) {
        adj_list_.resize(vertices_);
    }

    void AddEdge(int u, int v, int weight) {
        adj_list_[u].emplace_back(v, weight);
        adj_list_[v].emplace_back(u, weight); // 对于无向图，需要双向添加边
    }

    void PrintAdjList() const {
        for (int v = 0; v < vertices_; ++v) {
            std::cout << static_cast<char>('A' + v) << ": ";
            for (const auto& edge : adj_list_[v]) {
                std::cout << static_cast<char>('A' + edge.first) << " (权重 " << edge.second << ") ";
            }
            std::cout << std::endl;
        }
    }

private:
    int vertices_;
    std::vector<std::vector<std::pair<int, int>>> adj_list_;
};

int main() {
    Graph g(5);

    // 根据图添加边
    g.AddEdge(0, 1, 3); // A -> B
    g.AddEdge(0, 2, 4); // A -> C
    g.AddEdge(1, 3, 2); // B -> D
    g.AddEdge(1, 4, 2); // B -> E
    g.AddEdge(2, 3, 1); // C -> D
    g.AddEdge(3, 4, 5); // D -> E

    g.PrintAdjList();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

2.4 总结

在邻接表表示法中，链表中顶点的顺序实际上是不重要的。邻接表的主要目的是表示每个顶点的邻接关系以及对应的边权重，因此，顶点的顺序并不会影响图的表示和算法的正确性。

总体来看，第二种封装方式更符合现代 C++ 编程规范，更加推荐。主要原因如下：

1. 简洁性和可维护性：使用 STL 容器使代码更简洁，易于维护和扩展。
2. 内存管理：STL 容器自动管理内存，减少内存泄漏的风险。
3. 灵活性：STL 容器提供了丰富的操作接口，使用更加灵活。

当然, 如果你需要对图进行非常细粒度的控制，或者在非常严格的性能要求下，第一种封装方式可能更适合。

3 有向图的邻接表

假设有以下有向图，其中节点 A、B、C、D、E 表示城市，边表示城市之间的道路，权重表示道路的距离。

3.1 示例

    A----3---->B
    |         |
    4         2
    |         |
    v         v
    C<----1----D
    |     
    5     
    |
    v 
    E 
1
2
3
4
5
6
7
8
9
10
11

对应的邻接表为：

A -> B(3) -> C(4)
B -> D(2)
C -> E(5)
D -> C(1)
E -> 
1
2
3
4
5

3.2 C++实现

#include <iostream>
#include <vector>

class Graph {
public:
    Graph(int vertices)
        : vertices_(vertices) {
        adj_list_.resize(vertices_);
    }

    void AddEdge(int u, int v, int weight) {
        adj_list_[u].emplace_back(v, weight);
    }

	/*
	// 对比无向图的, 向图中添加边:
	void AddEdge(int u, int v, int weight) {
        adj_list_[u].emplace_back(v, weight);
        adj_list_[v].emplace_back(u, weight); // 对于无向图，需要双向添加边
    }
	*/

    void PrintAdjList() const {
        for (int v = 0; v < vertices_; ++v) {
            std::cout << static_cast<char>('A' + v) << ": ";
            for (const auto& edge : adj_list_[v]) {
                std::cout << static_cast<char>('A' + edge.first) << " (权重 " << edge.second << ") ";
            }
            std::cout << std::endl;
        }
    }

private:
    int vertices_;
    std::vector<std::vector<std::pair<int, int>>> adj_list_;
};

int main() {
    Graph g(5);

    g.AddEdge(0, 1, 3); // A -> B
    g.AddEdge(0, 2, 4); // A -> C
    g.AddEdge(1, 3, 2); // B -> D
    g.AddEdge(3, 2, 1); // D -> C
    g.AddEdge(2, 4, 5); // C -> E

    g.PrintAdjList();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

3.3 总结

有向图表示的邻接表结构和无向图类似，只是边的方向性需要注意。

4 邻接图的遍历

// **图的遍历（DFS 和 BFS）**
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

class Graph {
public:
    Graph(int vertices)
        : vertices_(vertices) {
        adj_list_.resize(vertices_);
    }

    void AddEdge(int u, int v, int weight) {
        adj_list_[u].emplace_back(v, weight);
    }

    void DFS(int start) {
        std::vector<bool> visited(vertices_, false);
        std::stack<int> stack;
        stack.push(start);

        while (!stack.empty()) {
            int v = stack.top();
            stack.pop();

            if (!visited[v]) {
                std::cout << static_cast<char>('A' + v) << " ";
                visited[v] = true;
            }

            for (const auto& edge : adj_list_[v]) {
                if (!visited[edge.first]) {
                    stack.push(edge.first);
                }
            }
        }
        std::cout << std::endl;
    }

    void BFS(int start) {
        std::vector<bool> visited(vertices_, false);
        std::queue<int> queue;
        queue.push(start);
        visited[start] = true;

        while (!queue.empty()) {
            int v = queue.front();
            queue.pop();
            std::cout << static_cast<char>('A' + v) << " ";

            for (const auto& edge : adj_list_[v]) {
                if (!visited[edge.first]) {
                    queue.push(edge.first);
                    visited[edge.first] = true;
                }
            }
        }
        std::cout << std::endl;
    }

    void PrintAdjList() const {
        for (int v = 0; v < vertices_; ++v) {
            std::cout << static_cast<char>('A' + v) << ": ";
            for (const auto& edge : adj_list_[v]) {
                std::cout << static_cast<char>('A' + edge.first) << " (权重 " << edge.second << ") ";
            }
            std::cout << std::endl;
        }
    }

private:
    int vertices_;
    std::vector<std::vector<std::pair<int, int>>> adj_list_;
};

int main() {
    Graph g(5);

    g.AddEdge(0, 1, 3); // A -> B
    g.AddEdge(0, 2, 4); // A -> C
    g.AddEdge(1, 3, 2); // B -> D
    g.AddEdge(3, 2, 1); // D -> C
    g.AddEdge(2, 4, 5); // C -> E

    std::cout << "邻接表:" << std::endl;
    g.PrintAdjList();

    std::cout << "DFS 从 A 开始:" << std::endl;
    g.DFS(0);

    std::cout << "BFS 从 A 开始:" << std::endl;
    g.BFS(0);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

5 拓展补充

• 时间复杂度分析：
  • 添加边：O(1) - 在邻接表中添加一条边的时间复杂度为常数时间，因为只需将新边添加到链表头部。
  • 删除边：O(E) - 删除一条边可能需要遍历整个链表，时间复杂度为 O(E)，其中 E 是链表的长度。
  • 查找邻接点：O(V) - 查找某个顶点的所有邻接点的时间复杂度为 O(V)，其中 V 是顶点的数量。
  • 查找某条边：O(E) - 查找某条边是否存在的时间复杂度为 O(E)，其中 E 是链表的长度。
• 图的遍历：
  • **深度优先搜索（DFS）和广度优先搜索（BFS）**都可以在邻接表上高效实现。时间复杂度均为 O(V + E)，其中 V 是顶点的数量，E 是边的数量。
• 存储结构：
  • 邻接表可以使用数组、链表、向量（std::vector）、哈希表（std::unordered_map）等数据结构来实现，具体选择取决于需求和编程语言。
• 内存消耗：
  • 相比邻接矩阵（Adjacency Matrix），邻接表在稀疏图（Sparse Graph）上更加节省内存。对于具有 V 个顶点和 E 条边的图，邻接矩阵需要 O(V^2) 的空间，而邻接表只需要 O(V + E) 的空间。
• 变种：
  • 加权图：每条边都有权重（已在示例中展示）。
  • 有向图和无向图：有向图的每条边有方向，反映在邻接表中只在一个方向上添加边；无向图在两个顶点之间添加双向边。
  • 多重图（Multigraph）：允许在两个顶点之间存在多条边。邻接表可以通过链表或向量来支持多重图。
• 图的表示法转换：
  • 邻接表可以轻松转换为邻接矩阵，反之亦然，但在稀疏图上邻接表更有效。
• 动态图：
  • 对于动态变化的图（例如频繁添加或删除边），邻接表比邻接矩阵更具优势，因为添加和删除操作更高效。

References