Skip to content

2021-03-17

定义

图(Graph) 由若干 顶点 组成,用大写字母 G 表示,V 为顶点集合,E 为边集合,记作 G=(V,E)

图是描述实际问题的工具。如在城市道路规划中,可将每个城市视作顶点,将道路视作边。

边的方向

  • 图的每条边都有起点和终点,则图为 有向图
  • 相反,边没有方向(可以理解为双向)的图为 无向图(双向图)

边权和点权

为解决实际问题,引入 边权点权 的概念:

  • 边权 及边的长度.解决最短路径问题时,将城市视作顶点,城市之间的道路长度视作边权;
  • 点权 即点的大小.解决最小收费问题时,将收费站视作顶点,收费站之间的道路视作边,通过收费站支付的费用视作点权。

度数

若图中有 d 条边与节点 i 相连,则节点 i度数d(即节点的 连边 个数)。如下图,节点 1 的度为 6

  • 若有向图中有 d 条边的 终点 是节点 i,则节点 i入度d(即节点的 入边 个数);
  • 若有向图中有 d 条边的 起点 是节点 i,则节点 i出度d(即节点的 出边 个数)。

子图

G 的子图 H 满足以下条件:

  • G 中包含 H 的所有节点和边;
  • GH 同时为无向图或有向图。

G=(V,E),H=(V,E),VV,EE。如下图,HG 的子图:

路径和连通

从节点 i 走到节点 j,经过的边的序列为 ij路径。路径的长度为经过边的边权和。

如下图,节点 16 的一条路径为 1456

若两个节点之间存在路径,则称它们 连通

回路(环)

若图中存在起点和终点相同的路径,则此路径称作 回路(环)

完全图和连通图

  • 若无向图 G 的任意两个节点之间都有连边,则 G 称为 完全图

    n 个节点的完全图有 12n(n1) 条边。

  • 若无向图 G 的任意两个节点都连通,则 G 称为 连通图

    n 个节点的连通图至少有 n1 条边。

强连通分量

  • 若有向图 G 的任意两个节点都连通,则 G 称为 强连通图
  • 若有向图 G 的子图 H 是强连通图,则 H 称为 G强连通分量

图的存储

直接存边

把每条边的起点、终点、长度存入数组中.

cpp
const int N = 1e6;
struct node {
    int from, to, len;
} edge[N];

邻接矩阵

用二维数组 g(邻接矩阵)存储边长,g[i,j] 表示边 ij 的权值。缺点是不能存储重边、浪费空间。

cpp
const int N = 1e6;
int g[N][N];

邻接表

把节点 i 的所有相邻节点插入以 head[i] 开头的链表中。

cpp
int top, head[];
struct Node {
    int val, len, next; // 这里只需要用到单向链表
} edge[];

// 追加一条从 u 到 v,长度为 len 的边
void insert(int u, int v, int len) {
    edge[++ top] = Node{v, len, head[u]};
    head[u] = top;
}

// 获取以 u, v 为端点的边的长度(没有边则返回 -1)
int path(int u, int v) {
    for (int p = head[u]; p; p = edge[p].next)
        if (edge[p].val == v)
            return edge[p].len;
    return -1;
}