Appearance
定义
图(Graph) 由若干 顶点 和 边 组成,用大写字母
图是描述实际问题的工具。如在城市道路规划中,可将每个城市视作顶点,将道路视作边。
边的方向
- 图的每条边都有起点和终点,则图为 有向图;
- 相反,边没有方向(可以理解为双向)的图为 无向图(双向图)。
边权和点权
为解决实际问题,引入 边权 和 点权 的概念:
- 边权 及边的长度.解决最短路径问题时,将城市视作顶点,城市之间的道路长度视作边权;
- 点权 即点的大小.解决最小收费问题时,将收费站视作顶点,收费站之间的道路视作边,通过收费站支付的费用视作点权。
度数
若图中有
- 若有向图中有
条边的 终点 是节点 ,则节点 的 入度 为 (即节点的 入边 个数); - 若有向图中有
条边的 起点 是节点 ,则节点 的 出度 为 (即节点的 出边 个数)。
子图
图
中包含 的所有节点和边; 和 同时为无向图或有向图。
即
路径和连通
从节点
如下图,节点
若两个节点之间存在路径,则称它们 连通。
回路(环)
若图中存在起点和终点相同的路径,则此路径称作 回路(环)。
完全图和连通图
若无向图
的任意两个节点之间都有连边,则 称为 完全图; 个节点的完全图有 条边。 若无向图
的任意两个节点都连通,则 称为 连通图。 个节点的连通图至少有 条边。
强连通分量
- 若有向图
的任意两个节点都连通,则 称为 强连通图; - 若有向图
的子图 是强连通图,则 称为 的 强连通分量。
图的存储
直接存边
把每条边的起点、终点、长度存入数组中.
cpp
const int N = 1e6;
struct node {
int from, to, len;
} edge[N];
邻接矩阵
用二维数组
cpp
const int N = 1e6;
int g[N][N];
邻接表
把节点
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;
}