概述

  • 一个由顶点和边组成的非线性数据结构，突出点与点之间的关系。广泛应用与现实场景的各种抽象建模，很灵活
  • 由图的建模使用可以衍生出各种各样的算法，这里不做详细说明，需要的时候在补上

简单图示

图

特性

相对详细内容请查看 图论

在图论介绍的各种分类以及性质，最终在数据结构层面影响到的是数据的存储、表示方式

表示方式

以图示的图为例，表示方式如下

  1. 邻接矩阵

    以一个二维矩阵表示点与点之间的关系。如图所示，矩阵下标表示点的编号，矩阵值表示点与点是否相连(通常0表示没有相连，1及以上表示连接/边的权值)(图中省略0)

邻接矩阵

  • 适用场景
    • 稠密图
    • 频繁查询边信息

  1. 邻接表

    以一个链表集合表示点与点之间关系。如图所示，集合中每个元素表示一个点，每个点有一个链表表示该点与其它点的关系

邻接表

  • 适用场景
    • 稀疏图
    • 频繁查询邻近点信息

  1. 直接存边

    使用一个数组直接存边，每个元素包含起点和终点，若有边权则额外补充

复杂度分析

假设图的点数为n，边数为m

邻接矩阵

操作 时间复杂度 空间复杂度
构建 - O(n^2)
查边 O(1) -
遍历点所有出边 O(n) -
遍历图 O(n^2) -

邻接表

操作 时间复杂度 空间复杂度
构建 - O(m)
查边 O(k)(k为点的出度/链表长度) -
遍历点所有出边 O(k) -
遍历图 O(n + m) -

边集

操作 时间复杂度 空间复杂度
构建 - O(m)
查边 O(m) -
遍历点所有出边 O(m) -
遍历图 O(nm) -

衍生部分算法

遍历

BFS (广度优先搜索)

  • 借助队列逐层访问
  • 适用于获取最短路径场景等

DFS (深度优先搜试)

  • 使用递归、栈(迭代)完成分支深度搜索
  • 适用于搜索所有路径等

最短路径

  • Dijkstra 算法
  • Floyd 算法

最小生成树

  • Kruskal 算法
  • Prim 算法

拓扑排序

二分图匹配

  • 匈牙利算法
  • KM 算法

网络流

  • 最大流
  • 最小割

着色算法

发散/随想/自身理解(?)

  • 用处太广泛了，很多问题场景都可以用图来构建，而且衍生的算法太多了，很复杂
  • 不过在我的工作场景中好像没咋涉及到图结构的构建，衍生算法应该是有用到一点，但没啥印象
  • 刷题的时候遇到一大堆，不会的也一大堆

实现(C++)

构建

1
2
3
4
5
// leetcode 上，一般会给一个边集，每个元素有三个数值组成，[起点，终点，边权]
void Build(int n, vector<vector<int>> edges) {

}

存边

1
2
3
4
5
6
7
8
9
10
11
struct Edge {
    int start;
    int end;
    int weight;
};

vector<Edge> graph;

for (auto& edge: edges) {
    graph.push_back({edge[0], edge[1], edge[2]});
}

邻接矩阵

1
2
3
4
5
6
7

vector<vector<int>> graph(n, vector<int>(n, 0));

for (auto& edge: edges) {
    graph[edge[0]][edge[1]] = edge[2];
}

邻接表

1
2
3
4
5
6
7
8
9
10
11
12

struct Info {
    int p;
    int w;
};

vector<vector<Info>> graph(n);

for (auto& edge: edges) {
    graph[edge[0]].push_back({edge[1], edge[2]});
}

遍历

  • 预设：图使用邻接表构建

DFS

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
vector<vector<int>> g;

void dfs_recursion(int v) {
    if (v >= g.size()) return;

    vector<bool> visited(g.size(), false);
    function<void(int)> dfs = [&](int x) {
        if (visited[x]) return;

        // operation
        visited[x] = true;
        for (auto y: g[x]) {
            if (visited[y]) continue;
            dfs(y);
        }
    };

    dfs(v);
}

void dfs_iteration(int x) {
    if (x >= g.size()) return;
    vector<bool> visited(g.size(), false);
    stack<int> st;

    st.push(x);

    while (!st.empty()) {
        int top = st.top();
        st.pop();
        if (visited[top]) continue;
        if (top >= g.size()) continue;

        // operation
        visited[top] = true;
        for (int i = g[top].size() - 1; i >= 0; i--) {
            int y = g[top][i];
            if (visited[y]) continue;
            st.push(y);
        }
    }

}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void bfs(int x) {
    if (x >= g.size()) return;
    vector<bool> visited(g.size(), false);
    queue<int> que;

    que.push(x);

    while (!que.empty()) {
        int front = que.front();
        que.pop();
        if (visited[front]) continue;
        if (front >= g.size()) continue;

        // operation
        visited[front] = true;
        for (auto y: g[front]) {
            if (y >= g.size() || visited[y]) continue;
            que.push(y);
        }
    }

}