图

2021 年 5 月 17 日 星期一(已编辑)
1
这篇文章上次修改于 2021 年 5 月 17 日 星期一，可能部分内容已经不适用，如有疑问可询问作者。

图

图

简介

相关概念

图 · Graph 是一个二元组 G = (V(G), E(G))G \ = \ (V(G), \ E(G))。其中 V(G)V(G) 是非空集，称为 点集 · Vertex set，对于 V 中的每个元素，我们称其为 顶点 · Vertex 或 节点 · Node，简称 点；E(G)E(G) 为 V(G)V(G) 各结点之间边的集合，称为 边集 · Edge set。

常用 G = (V, E)G \ = \ (V, \ E) 表示图。

当 V, E 都是有限集合时，称 G 为 有限图。

当 V 或 E 是无限集合时，称 G 为 无限图。

图有多种，包括 无向图 · Undirected graph，有向图 · Directed graph，混合图 · Mixed graph 等

  • 若 G 为无向图，则 E 中的每个元素为一个无序二元组 (u, v)(u, \ v)，称作 无向边 · Undirected edge，简称 边 · Edge，其中 u, v ∈ Vu, \ v \ \in \ V。设 e = (u, v)e \ = \ (u, \ v)，则 u 和 v 称为 e 的端点 · Endpoint。
  • 若 G 为有向图，则 E 中的每一个元素为一个有序二元组 (u, v)(u, \ v)，有时也写作 u → vu \ \rightarrow \ v，称作 有向边 · Directed edge 或 弧 · Arc，在不引起混淆的情况下也可以称作 边 · Edge。设 e = u → ve \ = \ u \ \rightarrow \ v，则此时 u 称为 e 的 起点 · Tail，v 称为 e 的 终点 · Head，起点和终点也称为 e 的 端点 · Endpoint。并称 u 是 v 的直接前驱，v 是 u 的直接后继。
  • 若 G 为混合图，则 E 中既有向边，又有无向边。
  • 若 G 的每条边 ek = (uk, vk)e_{k} \ = \ (u_{k}, \ v_{k}) 都被赋予一个数作为该边的 权，则称 G 为 赋权图。如果这些权都是正实数，就称 G 为 正权图。

图 G 的点数 ∣V(G)∣|V(G)| 也被称作图 G 的 阶 · Order。

形象地说，图是由若干点以及连接点与点的边构成的。

度数

与一个顶点 v 关联的边的条数称作该顶点的 度 · Degree，记作 d(v)d(v)。特别地，对于边 (u, v)(u, \ v)，则每条这样的边要对 d(v)d(v) 产生 2 的贡献。

对于无向简单图，有 d(v) = ∣N(v)∣d(v) \ = \ |N(v)|。

握手定理（又称图论基本定理）：对于任何无向图 G = (V, E)G \ = \ (V, \ E)，有 ∑v ∈ Vd(v) = 2∣E∣\sum_{v \ \in \ V}d(v) \ = \ 2|E|。

推论：在任意图中，度数为奇数的点必然有偶数个。

在有向图 G = (V, E)G \ = \ (V, \ E) 中，以一个顶点 v 为起点的边的条数称为该顶点的 出度 · Out-degree，记作 d+(v)d^{+}(v)。以一个顶点 v 为终点的边的条数称为该节点的 入度 · In-degree，记作 d−(v)d^{-}(v)。显然 d+(v) + d−(v) = d(v)d^{+}(v) \ + \ d^{-}(v) \ = \ d(v)。

对于任何有向图 G = (V, E)G \ = \ (V, \ E)，有：∑v ∈ Vd+(v) = ∑v ∈ Vd−(v) = ∣E∣\sum_{v \ \in \ V}d^{+}(v) \ = \ \sum_{v \ \in \ V}d^{-}(v) \ = \ |E|

路径

Chain · 链：一个点和边的交错序列 v0 - e1 - v1 - e2 - v2 - ... - ek - vk

Trail · 迹：对于一条路径 w，若e1, e2, ..., ek 两两互不相同，则 w 是一条迹

Path · 路径：对于一条迹 w，除了 v0 和 vk 允许相同外，其余点两两互不相同，则称 w 是一条路径

Circuit · 回路：对于一个迹 w，若 v0 = vk，则称 w 是一个回路

Cycle · 环：对于一条路径 w，若 v0 = vk，则称 w 是一个环

存储

存边

方法

使用一个数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。（或者使用多个数组分别存起点，终点和边权。）

模板

#include <iostream>
#include <vector>

using namespace std;

struct Edge
{
    int u, v;
};

int n, m;
vector<Edge> e;
vector<bool> vis;

bool find_edge(int u, int v)
{
    for (int i = 1; i <= m; ++i)
    {
        if (e[i].u == u && e[i].v == v)
        {
            return true;
        }
    }
    return false;
}

void dfs(int u)
{
    if (vis[u]) return;
    vis[u] = true;
    for (int i = 1; i <= m; ++i)
    {
        if (e[i].u == u)
        {
            dfs(e[i].v);
        }
    }
}

int main()
{
    cin >> n >> m;

    vis.resize(n + 1, false);
    e.resize(m + 1);

    for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v;

    return 0;
}

复杂度

查询是否存在某条边：O(m)O(m)。

遍历一个点的所有出边：O(m)O(m)。

遍历整张图：O(nm)O(nm)。

空间复杂度：O(m)O(m)。

应用

由于直接存边的遍历效率低下，一般不用于遍历图。

在 Kruskal 算法中，由于需要将边按边权排序，需要直接存边。

在有的题目中，需要多次建图（如建一遍原图，建一遍反图），此时既可以使用多个其它数据结构来同时存储多张图，也可以将边直接存下来，需要重新建图时利用直接存下的边来建图。

邻接矩阵

方法

使用一个二维数组 adj 来存边，其中 adj[u][v] 为 1 表示存在 到 的边，为 0 表示不存在。如果是带边权的图，可以在 adj[u][v] 中存储 u 到 v 的边的边权。

模板

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<bool> > adj;

bool find_edge(int u, int v) { return adj[u][v]; }

void dfs(int u)
{
    if (vis[u]) return;
    vis[u] = true;
    for (int v = 1; v <= n; ++v)
    {
        if (adj[u][v])
        {
            dfs(v);
        }
    }
}

int main()
{
    cin >> n >> m;

    vis.resize(n + 1, false);
    adj.resize(n + 1, vector<bool>(n + 1, false));

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u][v] = true;
    }

    return 0;
}

复杂度

查询是否存在某条边：O(1)O(1)。

遍历一个点的所有出边：O(n)O(n)。

遍历整张图：O(n2)O(n^{2})。

空间复杂度：O(n2)O(n^{2})。

应用

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以 O(1)O(1) 查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

邻接表

方法

使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> adj[n + 1] 来存边，其中 adj[u] 存储的是点 的所有出边的相关信息（终点、边权等）。

模板

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<int> > adj;

bool find_edge(int u, int v)
{
    for (int i = 0; i < adj[u].size(); ++i)
    {
        if (adj[u][i] == v)
        {
            return true;
        }
    }
    return false;
}

void dfs(int u)
{
    if (vis[u]) return;
    vis[u] = true;
    for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i]);
}

int main()
{
    cin >> n >> m;

    vis.resize(n + 1, false);
    adj.resize(n + 1);

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    return 0;
}

复杂度

查询是否存在 u 到 v 的边：O(d+(u))O(d^{+}(u))（如果事先进行了排序就可以使用二分查找做到 ）。

遍历点 u 的所有出边：O(d+(u))O(d^{+}(u))。

遍历整张图：O(n + m)O(n \ + \ m)。

空间复杂度：O(m)O(m)。

应用

存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。

尤其适用于需要对一个点的所有出边进行排序的场合。

链式前向星

模板

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define INF 0x3f3f3f3f

int n, m;    //n 个点，m 条单向边
int cnt;
int front[10001];

struct EDGE
{
    int to, next, w;
};

EDGE edge[10001];

void Init()
{
    memset(front, 0, sizeof(front));
    cnt = 0;
}

void add_edge(int u, int v, int w)
{
    ++cnt;
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = front[u];
    front[u] = cnt;
}

int main()
{
    freopen("in.txt", "r", stdin);
    Init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);    //双向边
    }

    //遍历与每个点相连的所有边
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", i);
        for (int j = front[i]; j; j = edge[j].next)
        {
            printf("%d %d %d\n", i, edge[j].to, edge[j].w);
        }
        printf("\n");
    }

    return 0;

}

复杂度

查询是否存在 u 到 v 的边：O(d+(u))O(d^{+}(u))。

遍历点 的所有出边：O(d+(u))O(d^{+}(u))。

遍历整张图：O(n + m)O(n \ + \ m)。

空间复杂度：O(m)O(m)。

应用

存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。

优点是边是带编号的，有时会非常有用，而且如果 cnt 的初始值为奇数，存双向边时 i ^ 1 即是 i 的反边（常用于网络流）。

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...