图论基础
图是什么?
图的定义
- 图(graph)是一个二元组G=(V(G), E(G))。其中V(G)是非空集,称为点集(vertex set),对于V中的每个元素,我们称其为 顶点 (vertex) 或 节点 (node),简称 点;E(G) 为 V(G) 各结点之间边的集合,称为 边集 (edge set)。
- 存在一个结点(V),可能含有多个前驱结点和后继结点。
- 边长定义为边权,即顶点之间的距离
图的分类
- 有向图——边具有指向性的图
- 无向图——边没有指向性的图
- 无权图
- 带权图(网)——图中的边加上表示某种含义的数组,数值称为边的权
- 连通图——任意两点之间都有路径连接的图
- 二分图
- ...
连通:两顶点间有路可通
连通分量:无向图中的极大连通子图
无向图的术语
- 两个顶点之间如果有边连接,那么就视为两个顶点相邻。
- 相邻顶点的序列称为路径。
- 起点和终点重合的路径叫做圈。
- 任意两点 之间都有路径连接的图叫做连通图。
- 顶点连接的边数叫做这个顶点的度。
- 没有圈的连通图叫做树((tree)),没有圈的非连通图叫做森林。一棵树的边数恰好等于顶点数-1
- 如果在树上选择一个顶点作为根((root)),就可以把根提到最上面,而离根越远的顶点越往下安排其位置。这样的树叫做有根树。
有向图的术语
入度—— 以该点为终点的边的数目
出度—— 以该顶点为起点的边的数目
度—— 等于该顶点的入度与出度之和
- 没有圈的有向图叫做(DAG)((Directed) (Acyclic) (Graph)).
在DAG中我们可以给顶点标记一个先后顺序,对于每个顶点我们给它一个编号,第(i)号顶点叫做(v_i)。那么存在从顶点(v_i)到顶点(v_j)的边时就有(i<j)成立,这样的编号叫做拓扑序。
如果把图中顶点按照拓扑序从左到右排列,那么所有的边都是从左指向右的。
图的存储
邻接矩阵(二维数组)
g[i][j]; //表示i点到j点的边权。
-
无向图中
只需要知道“顶点(i)和顶点(j)之间是否有边连着”这样的信息,因此如果顶点(i)和顶点(j)之间有边相连,那么g[i][j]
和g[j][i]
就设为(1),否则设为(0). -
在有向图中
只需要知道“是否有从顶点(i)发出指向顶点(j)的边”这样的信息,因此如果顶点(i)有一条指向顶点(j)的边,那么g[i][j]
就设为(1),否则设为(0)。与无向图不同,并不需要满足g[i][j]=g[j][i]
. -
在带权图中
g[i][j]
表示的是顶点(i)到顶点(j)的边的权值。由于在边不存在的情况下,如果将g[i][j]
设为(0),就无法和权值为(0)的情况区分开来,因此选取适当的较大的常数(INF)(只要能和普通的权值区别开来就可以),然后令g[i][j]=INF
就好。当然,在无向图中还要保持g[i][j]=g[j][i]
。在一条边上有多种不同权值情况下,定义多个二维数组或者使用结构体就可以。
存图方法
//无向图:两遍都可以走,双向箭头
for(int i = 1; i <= m; i++){ //m是边的数量
int from, to, w;
cin >> from >> to >> w;
map[from][to] = w;
map[to][from] = w;
}
总结:邻接矩阵的优点: 方便度的计算(读入时就可以算)、方便判断两点是否有边及其权值、大小是n*n、占用的单元只与顶点有关。
缺点: 是寻找一个点的所有相连的边需要1-n循环,而且内存过大容易爆
邻接表
- vector
- 邻接表
- 伪邻接表(链式前向星)
//链式前向星写法
struct Edge {
int to, w, next;
} edges[N];
int head[N], cnt;//cnt为当前边的编号
void add (int from, int to, int w) {
edges[++cnt].w = w;//新增一条编号为cnt+1的边,边权为w
edges[cnt].to = to;//该边的终点为to
edges[cnt].next = head[from];//把下一条边,设置为当前起点的第一条边
head[from] = cnt;//该边成为当前七点新的第一条边
}
图的DFS遍历
算法步骤:
- 从某个节点开始,每次任选一个与它相邻的未访问节点访问下去
- 直到当前节点的所有相邻节点都已经被访问过。
- 回溯到第一个未被访问过的节点
图的BFS遍历
- 用
dis[]
数组表示各点距离起点(S)的距离。dis[i]=-1
表示(i)点还未被访问。用g[i][j]
表示(i)点和(j)点之间是否有边。 - 将
dis[s]
初始化为(0),将其他点的dis
初始化为(-1)。将(S)点入队 -
while(队列非空) 从队首出队一个元素u 对于所有根u有边相连的点v: if(dis[v]==-1) dis[v] = dis[u] +1; v入队
判断是否为欧拉图
- 如果图G中的一个路径包括每个边恰好一次,则该路径称为欧拉路径(Euler path)
- 如果一个回路是欧拉路径,则称为欧拉回路(Euler circuit)
- 具有欧拉回路的图称为欧拉图(简称E图)。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。
无向图存在欧拉回路的充要条件
- 一个无向图存在欧拉回路,当且仅当该图所有顶点度数都为偶数,且该图是连通图。
有向图存在欧拉回路的充要条件
- 一个有向图存在欧拉回路,所有顶点的入度等于出度且该图是连通图。
拓扑排序
概念
- 一个工程常被分为多个小的子工程,这些子工程被称为活动,在有向图中若以顶点表示活动,有向边表示活动之间的先后关系,这样的图简称为AOV网。在AOV网中为了更好地完成工程,必须满足活动之间先后关系,需要将各活动排一个先后次序即为拓扑排序
实现方法
- 从有向图中选取一个没有前驱的顶点,并输出它。
- 从有向图中删去此顶点以及所有以它为尾的弧。
- 重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。没有前驱——入度为零,删除顶点以及以它为尾的弧——弧头顶点的入度减1。
举例
- 根据算法思想:
- 找到的点的顺序依次为v6,v1,v5,v3,v2,v4
- 可以看到,拓扑排序可能有多解
- (注意一边输出当前点,一边更新其他点的入度)
输入:
输入n,m表示n个顶点,m条边
m行,每行表示两个顶点x,y,表示有边从x到y
6 8
1 2
1 4
1 3
2 4
3 4
5 3
5 4
6 4
输出:
1
5
6
2
3
4
链式前向星:
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long LL;
int n, m;
struct ty {
int t, next;
} edge[100010];
int head[1010];
int cnt = 0;
void addedge(int x, int y) {
edge[++cnt].t = y;
edge[cnt].next = head[x];
head[x] = cnt;
}
int inc[1010];
queue<int> q;
void tuopu() {
for (int i = 1; i <= n; i++) {
if (inc[i] == 0) {
q.push(i);
}
}
int tot = 0;
while (!q.empty()) {
int x = q.front();
cout << x << " " << endl;
q.pop();
tot++;
for (int i = head[x]; i != -1; i = edge[i].next) {
inc[edge[i].t]--;
if (inc[edge[i].t] == 0) q.push(edge[i].t);
}
}
if (tot != n) cout << -1;
}
int main() {
scanf("%d%d", &n, &m);
memset(head, -1, sizeof(head));
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
addedge(x, y);
inc[y]++;
}
tuopu();
return 0;
}
拓扑排序的使用
- 判断一个有向图中是否有环。无环的图所有点都能进行拓扑排序。
关键路径
-
AOE网(Activity On Edge network),即边表示活动的网络,与AOV网相对应,它通常表示一个工程的计划或进度。
-
AOE是一个带权的有向无环图,图中的:
- 边:表示活动(子工程)
- 边上的权:表示该活动的持续时间,即完成该活动所需要的时间
- 顶点:表示事件,每个事件是活动之间的转接点,即表示它的所有入边活动到此完成,所有出边活动从此开始。其中有两个特殊的顶点(事件),一个称作源点,它表示整个工程的开始,亦即最早活动的起点,显然它只有出边,没有入边;另一个称作汇点,它表示整个工程的结束,亦即最后活动的终点,显然它只有入边,没有出边。除了这两个顶点外,其余顶点都既有入边,也有出边,是入边活动和出边活动的转接点。
-
AOE网中有些活动可以并行进行,所以完成整个工程的最短时间是从源点到汇点的最长路径长度,路径长度为路径上各边的权值之和。把从源点到汇点的最长路径长度称为关键路径。
-
对应一个AOE网,待研究的问题是:(1)整个工程至少需要多长时间完成?****(2)哪些活动是影响工程进度的关键?
-
假设开始点是(v_1),从(v_1)到(v_i)的最长路径长度叫做事件(v_i)的最早发生时间,这个时间决定了所有(v_i)为尾的弧所表示的活动的最早开始时间。我们用(e(i))表示活动(a_i)的最早开始时间。还可以定义一个活动的最迟开始时间(l(i)),这是在不推迟整个工程的前提下,活动(a_i)最迟必须开始进行的时间。两者之差(l(i)-e(i))意味着完成活动(a_i)的时间余量。我们把(l(i)=e(i))的活动叫做关键活动。
-
关键路径上的所有活动都是关键活动,因此提前完成非关键活动并不能加快工程的进度。
原文链接: https://www.cnblogs.com/csai-H/p/17065031.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/313749
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!