图论算法

algorithm

早起的鸟儿有虫吃

图的遍历

* 有两种存储方式：邻接矩阵和邻接表
* 在一些顶点数目比较大（一般顶点个数在1000以上）的情况下，使用邻接表而  
不是邻接矩阵来存储图。如果是稀疏图，用邻接表，如果是稠密图，用邻接矩阵。

深度优先搜索dfs遍历图

1
2
3
4
5
6
7
8
9
10
11
12
//按深度优先的方式访问所有未被访问的结点，在结点被访问过后标记为已访问
dfs(u) {
  vis[u] = true;
  for(从u出发到能到达的所有顶点v)
    if(vis[v] == false)
      dfs(v);
}
dfsTravel(G) {
  for(G的所有顶点u)
    if(vis[u] == false)
      dfs(u); //访问u所在连通块
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//邻接矩阵版 DFS

int n, G[maxV][maxV];//n顶点数 maxV最大顶点数
bool vis[maxV] = {false};//记录顶点是否被访问过

void dfs(int u, int depth) {
    vis[u] = true;
    for(int v = 0; v < n; v++)//遍历u可以到达的顶点v
        if(G[u][v] != INF && vis[v] == false)
            dfs(v, depth + 1);//访问v 深度+1
}

void travelDFS() {
    for(int u = 0; u < n; u++)
        if(vis[u] == false)
            dfs(u, 1);//访问u和u所在的连通块
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//邻接表版 DFS

vector<int> arr[maxn];

void dfs(int u, int depth) {
  vis[u] = true;
  for(int i = 0; i < arr[u].size(); i++){
	int v = arr[u][i];
	if(vis[i] == false)
    	dfs(v, depth + 1);
  }
}

void dfsTrave() {
  for(int u = 0; u < n; u++) {
    if(vis[u] == false)
      dfs(u, 1);
  }
}

广度优先搜索bfs遍历图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//建立一个队列，把初始定点加入队列，然后每次都取出队首元素进行访问，并把该定点  
//除法可以到达的未曾加入过队列（而不是未访问）的顶点全部加入队列，直到队列为空。
bfs(u) {
  queue q;
  将u入队
  inq[u] = true;
  while(q非空) {
    for(从u出发到可到达的所有顶点v) {
      if(inq[v] == false)
        将v入队
        inq[v] = true;
    }
  }
}

bfsTrave(G) {
  for(G的所有顶点u) {
    if(inq[u] == false)
      bfs(u);
  }
}
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
//邻接矩阵版 BFS
int n, G[maxV][maxV];//n顶点数 maxV最大顶点数
bool inq[maxV] = {false};//记录顶点的是否入队

void bfs(int u) {//u顶点编号
	queue<int> q;
	q.push(u);//入队
	inq[u] = true;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int v = 0; v < n; v++)//遍历u所在连通块（未入队）并入队
			if(G[u][v] != INF && inq[v] == false){
				q.push(v);、
				inq[v] = true;
			}
	}
}

/*邻接表：
for(int i = 0; i < arr[u].size(); i++) {
  int v= arr[u][i];
  if(inq[v] == false) {
    q.push(v);
    inq[v] = true;
  }
}
*/

void travelBFS() {
	for(int v = 0; v < n; v++)
		if (inq[v] == false)
			bfs(v);//遍历v及其所在连通块
}
1
2
3
4
5
6
7
8
//带层数的 邻接表
struct node {
  int v;//顶点编号
  int layer;//顶点层号
};
next.layer = curNode.layer + 1;
//邻接表中的类型是node，而不是int
vector<node> Adj[N];

最短路径

* 单源最短路径：计算源点到其他各顶点的最短路径的长度
* 全局最短路径：图中任意两点的最短路径
* Dijkstra、Bellman-Ford、SPFA求单源最短路径
* Floyd-Warshall可以求全局最短路径，但是效率比较低
* SPFA算法是Bellman-Ford算法的队列优化
* Dijkstra算法不能求带负权边的最短路径，而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径
* Bellman-Ford算法的核心代码只有4行，Floyd-Warshall算法的核心代码只有5行
* 深度优先遍历可以求一个点到另一个点的最短路径的长度

单源最短路径

思想来源：图的广度优先遍历bfs

Dijkstra 算法

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
//Dijkstra 算法：
//对图G(V,E)设置集合S，存放已被访问的顶点，
//然后每次从集合V-S中选择与起点s的最短距离最小的一个顶点(记为u),访问并加入集合S，
//之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v的最短距离，
//这样的操作执行n次,直到集合S已包含所有顶点。

int G[maxSize][maxSize], n;
int d[maxSize];
int pre[maxSize];
bool vis[maxSize] = {false};
//邻接矩阵
void Dijkstra(int s) { //T(n) = O(V^2)
	fill(d, d + maxSize, INF);
	d[s] = 0;
	for (int i = 0; i < n; i++){
		int u = -1, min = INF;//u 保存最短路径顶点，min保存最短距离
		for (int j = 0; j < n; j++)
			if(vis[j] == false && d[j] < min) {
				u = j;
				min = d[j];
			}
		//找不到小于INF的d[u]，说明剩下的顶点与起点s不连通
		if(u == -1) return;
		vis[u] = true;
		for (int v = 0; v < n; v++) {
			//以u为中介点使可以使d[v]更优
			if(G[u][v] != INF && vis[v] == false && d[u] + G[u][v] < d[v]) {
				d[v] = d[u] + G[u][v];
				pre[v] = u; //记录v的前驱结点u
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//邻接表
struct Node {
	int v, dis; //v为边的目标顶点，dis为边权
};

vector<Node> Adj[MAXV];

for(int j = 0; j < Adj[u].size(); j++) {
	int v = Adj[u][j].v; //通过邻接表直接获得u能到达的顶点v
	if(vis[v] == false && d[u] + Adj[u][v].dis < d[v]) {
		d[v] = d[u] + Adj[u][v].dis;
	} 
}
1
2
3
4
5
6
7
8
9
10
//无向图解决方案: 把无向边当成指向相反的有向边

void DFS(int s, int v) {//s起点编号，v是当前访问的顶点编号（从终点开始递归）
	if(v == s) { //如果当前已经打扫起点s，则输出起点并返回
		printf("%d\n", s);
		return;
	}
	DFS(s, pre[v]); //递归访问v的前驱结点pre[v]
	printf("%d\n", v);//从最深处return回来之后，输出每一层的顶点号
}
附加考法：第一标尺是距离，第二标尺常见有三种
①新增边权：给每条边再增加一个边权（比如花费），然后要求在最短路径有多条时要求路径上的花费之和最小（如果边权是其它含义，也可以是最大）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//c[] 从起点s到达顶点u的最少花费c[u]
//cost[u][v]表示u->v的花费
//初始化时只有c[s] = 0 其余均为INF
for(int v = 0; v < n; v++) {
	if(G[u][v] != INF && vis[v] == false) {
		if(d[u] + G[u][v] < d[v]) {
			d[v] = d[u] + G[u][v];
			c[v] = c[u] +cost[u][v];
		}
		else if(d[u] + G[u][v] == d[v] && c[u] +cost[u][v] < c[v]){
			c[v] = c[u] +cost[u][v];//最短距离相同时，看c[v]能否更优	
		}
	}
}
②新增点权：给每个点增加一个点权（例如每个城市能收集到的物资），然后在最短路径
有多条时要求路径上的点权之和最大（如果点权是其它含义也可以是最小）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//w[]从起点s到顶点u能收集的最大物资w[u]
//weight[u]表示城市u中的物资数目
//初始化时只有w[s]为weight[s] 其余均为0
for(int v = 0; v < n; v++) {
	if(G[u][v] != INF && vis[v] == false) {
		if(d[u] + G[u][v] < d[v]) {
			d[v] = d[u] + G[u][v];
			w[v] = w[u] + weight[v];
		}
		else if(d[u] + G[u][v] == d[v] && w[u] + weight[v] > w[v]){
			w[v] = w[u] + weight[v];
		}
	}
}
③直接问有多少条最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
//num[]从起点s到达顶点u的最短路径条数为num[u]
//初始化只有num[s] = 1 其余均为0
for(int v = 0; v < n; v++) {
	if(G[u][v] != INF && vis[v] == false) {
		if(d[u] + G[u][v] < d[v]) {
			d[v] = d[u] + G[u][v];
			num[v] = num[u];
		}
		else if(d[u] + G[u][v] == d[v]){
			num[v] += num[u];//最短距离相同时累加num
		}
	}
}

Bellman-Ford 算法

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
// 零环、正环、负环
//零环和正环不会影响最短路径求解（因为不能使最短路径更短）
//负环 从源点可以到达，会影响最短路径求解（无法从源点除法到达 不会影响）
//算法思想：
//需要对图中的边进行V - 1轮操作，每轮都遍历图中的所有边：对每条边u->v, 
//如果以u为中介点可以使d[v]更小，即d[u] + length[u->v] < d[v]成立时，
//就用d[u] + length[u->v] 更新d[v]。
//T(n) = O(VE)
//第k轮得到从0号顶点"最多通过k条边到达其余各顶点的最短路径长度"
struct Node {
	int v, dis; //v为邻接边的目标顶点, dis为邻接边的边权
};
vector<Node> Adj[MAXV]; //邻接表
int n, d[MAXV]; //n顶点数，d[]用来存放从源点s到达各个顶点的最短距离

bool Bellman(int s) {
	fill(s, d + MAXV, INF);
	d[s] = 0;
	for(int i = 0; i < n - 1; i++) {
		for(u = 0; u < n; u++){//遍历所有边
			for(int j = 0; j < Adj[u].size(); j++) {
				int v = Adj[u][j].v;
				int dis = Adj[u][j].dis;
				if(d[u] + dis < d[v]) {
					d[v] = d[u] + dis; //松弛操作
				}
			}
		}
	}
	//判断负环代码
	for(int u = 0; u < n; u++) {
		for(int j = 0; j < Adj[u].size(); j++) {
			int v = Adj[u][j].v;
			int dis = Adj[u][j].dis;
			if(d[u] + dis < d[v]) {
				return false; //说明图中有从源点可达的负环
			}
		}
	}
	return true; //数组d的所有值都已经达到最优
}

SPFA 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Shortest Path Faster Algorithm
//T(n) = O(kE) , k <= 2
//理解SPFA的关键是理解它是如何从Bellman-Ford算法优化得来的
queue<int> q;
源点s入队
while(队列非空) {
	取出队首元素
	for(u的所有邻接边u->v) {
		if(d[u] + dis < d[v]) {
			d[v] = d[u] + dis;
			if(v当前不在队列) {
				v入队;
				if(v入队次数大于n - 1) {
					说明有可达负环，return;
				}
			}
		}
	}
}

全源最短路径

Floyd 算法

1
2
3
4
5
//Floyd算法
枚举顶点 k ∈ [1,n]
	以顶点 k 作为中介点，枚举所有顶点对i和j （i，j∈ [1,n]）
		如果dis[i][k] + dis[k][j] < dis[i][j]成立
			赋值dis[i][j] = dis[i][k] + dis[k][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
int n, m; //n顶点数， m为边数
int dis[MAXV][MAXV]; //dis[i][j]表示顶点i和j的最短距离

void Floyd(){
	for(int k = 0; k < n; k++) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j])
					dis[i][j] = dis[i][k] + dis[k][j];
			}
		}
	}
}

最小生成树

* 如果是稠密图(边多) prim算法
* 如果是稀疏图(边少) kruskal算法

prim 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//prim算法：
//对图G(V,E)设置集合S，存放已被访问的顶点，
//然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点（记为u）访问并加入集合S。
//之后，令顶点u为中介点，优化所有从u能到达的顶点v与集合S之间的最短距离。
//这样执行操作n次（n为顶点个数），直到集合S已包含所有顶点。
//prim算法和Dijkstra算法只有优化d[v]部分不同
//prim算法和Dijkstra算法思路完全相同，只不过是数组d[]含义不同
Prim(G, d[]){
	初始化
	for(循环n次){
		u = 使d[u]最小的还未被访问的顶点的标号
		for(从u除法能到达的所有顶点){
			if(v未被访问&& 以u为中介点使得v与集合S的最短距离d[v]更优){
				将G[u][v]赋值给v与集合S的最短距离d[v]
			}
		}
	}
}
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
//邻接矩阵
int n, G[MAXV][MAXV]; //n为顶点数
int d[MAXV]; //顶点与集合S的最短距离
bool vis[MAXV] = {false}; //标记数组，vis[i] == true表示已访问。初值均为false

int prim(){//默认0号为初始点
	fill(d, d + MAXV, INF);
	d[0] = 0;
	int ans = 0; //存放最小生成树的边权之和
	for(int i = 0; i < n; i++) {
		int u = -1, min = INF; //u使d[u]最小，min存放该最小的d[u]
		for(int j = 0; j < n; j++) {
			if(vis[j] == false && d[j] < min) {
				u = j;
				min = d[j];
			}
		}
		//找不到小于INF的d[u]，则剩下的顶点和集合S不连通
		if(u == -1) return -1;
		vis[u] = true;
		ans += d[u];
		for(int v = 0; v < n; v++) {
			if(G[u][v] != INF && vis[v] ==false && G[u][v] < d[v]){
				d[v] = G[u][v];
			}
		}
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//邻接表
struct Node {
	int v, dis; //v为边的目标顶点，dis为边权
};

vector<Node> Adj[MAXV]

for(int j = 0; j < Adj[u].size(); j++) {
	int v = Adj[u][j].v; //通过邻接表直接获得u能到达的顶点v
	if(vis[v] == false && Adj[u][j].dis < d[v]) {
		d[v] = Adj[u][v].dis;
	} 
}

kruskal 算法

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
//kruskal算法采用"边贪心"策略，步骤：
//①对所有边按边权从小到大进行排序。
//②按边权从小到大测试所有边，如果当前测试所连接的两个顶点不在同一//个连通块中，
//则把这条测试边加入当前最小生成树中；否则，将边舍弃
//③执行步骤②，直到最小生成树中的边数等于总顶点数-1或是测试完所有边//时结束。
//而当结束时如果最小生成树的边数小于总顶点数-1，说明该图不连通

struct edge {
	int u, v;//边的两个端点编号
	int cost;//边权
}E[MAXE];

int kruskal(){
	令最小生成树的边权之和为ans，最小生成树的当前边数为Num_Edge;
	将所有边按边权从小到大排序;
	for(从小到大枚举所有边){
		if(当前测试边的两个端点在不同的连通块中) {
			将该测试边加入最小生成树中;
			ans += 测试边边权;
			最小生成树的当前边数Num_Edge 加 1;
			当边数Num_Edge等于顶点数减1时结束循环;
		}
	}
	return ans;
}
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
int father[N];//并查集数组
int findFather(int x){
	while(x != father[x]) x = father[x];
	return x;
}

bool cmp(edge a, edge b) {
	return a.cost < b.cost;
}

int kruskal(int n, int m){ //n顶点数 m边数
	int ans = 0，Num_Edge = 0;
	for(int i = 1; i <= n; i++) {
		father[i] = i;
	}
	sort(E, E + m, cmp); //所有边按边权从小到大排序
	for(int i = 0; i < m; i++) { //枚举所有边
		int faU = findFather(E[i].u);
		int faV = findFather(E[i].v);
		if(faU != faV) { //如果不在一个集合中
			father[faU] = faV;
			ans += E[i].cost;
			Num_Edge++;
			if(Num_Edge == n - 1) break;//边数等于顶点数减1时结束算法
		}
	}
	if(Num_Edge != n - 1) return -1; //无法连通时返回-1
	else return ans;
}

拓扑排序

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
//算法思想：
//①定义一个队列Q,并把所有入度为0的结点加入队列
//②当队列不空时，取队首结点，输出然后删去所有从它出发的边，并令这些边到达的顶点的入度减1，
//如果某个顶点的入度减为0，则将其加入队列
//③反复进行②操作，直到队列为空。
//如果队列为空时入过队的结点数目恰好为N，说明拓扑排序成功，图G为有向无环图；否则，拓扑排序失败，图G中有环

//拓扑排序可以判断一个给定的图是否是"有向无环图"
//如果有多个入度为0的顶点，选择编号最小的顶点，那么把queue改成priority_queue，
//并保持堆顶元素是优先队列中的最小元素即可。(set也行)

vector<int> G[MAXV]; //邻接表
int n, inDegree[MAXV];
bool topologicalSort() {
	queue<int> q;
	int num = 0; //记录加入拓扑排序的顶点数
	for(int i = 0; i < n; i++) {
		if(inDegree[i] == 0) {
			q.push(i);
		}
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		//printf("%d ", u); //此处可输出顶点u，作为拓扑序列中的顶点
		for(int i = 0; i < G[u].size(); i++) {
			int v = G[u][i]; //u的后继v
			inDegree[v]--;
			if(inDegree[v] == 0) {
				q.push(v);
			}
		}
		G[u].clear(); //清空顶点u的所有出边（可写可不写）
		num++; //加入拓扑排序的顶点数加1
	}
	if(num == n) return true;
	else return false;
}

关键路径

AOV网 和 AOE网

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//AOV: Activity On Vertex
//AOE: Activity On Edge
//AOV, AOE不应当有环
/*
 *AOV网只有一个源点(入度为0)和一个汇点(出度为0)，若有多个源点和多*个汇点，也可转化为一个源点和一个汇点的情况
 *即添加一个"超级源点"和一个"超级汇点"，
 *方法：从超级源点出发，连接所有入度为0的点；从所有出度为0的点出**发，连接超级汇点；添加的有向边的边权均为0
 */
/*
 *如果给定AOV网中各顶点所需要的时间，那么可以将AOV网转化成AOE网
 *方法：将AOV网中每个顶点都拆成两个顶点。分别表示活动的起点和终点，
 *而两个顶点之间用有向边连接，该有向边表示原顶点的活动，边权给定；
 *原AOV网中的边全部视为空活动，边权为0
 */
/*
 *AOE网需要着重解决两个问题：
 *a. 工程起始到终止至少需要多少时间；
 *b. 那条(些)路径上的活动是影响整个工程进度的关键
 */
//AOE网中的"最长路径"称为"关键路径"，关键路径上的活动称为关键活动

最长路径算法

1
2
3
4
5
6
7
//算法思想：
//把所有边的边权乘以-1，然后使用 Bellman-Ford算法 或 SPFA算法 求最长路径长度，将所得结果取反。
//注意：此处不能用Dijkstra算法，原因是Dijkstra算法不能处理负权边的情况。

//最长路径问题，即 Longest Path Problem，寻求的是图中的"最长简单路径"
//如果图中有正环，则最长路径不存在。但最长简单路径存在，但你用Bellman-Ford算法求不出来(你说气不气)
//但我后面有简单方法鸭(*^▽^*)  (〃'▽'〃)哪呢

关键路径算法

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
45
46
47
48
struct node {
	int v, w;
};
vector<node> G[MAXV]; //邻接表

//先求点，再夹边
//ve[] 事件最早发生时间 //取最大
stack<int> topOrder; //留着求vl[], 不然我吃饱了撑的没事干急的啊
bool topologicalSort() {
	queue<int> q;
	for(int i= 0; i < n; i++) {
		if(inDegree[i] == 0) {
			q.push(i);
		}
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		topOrder.push(u);
		for(int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].v; //u的i号后继结点编号为v
			inDegree[v]--;
			if(inDegree[v] == 0) {
				q.push(v);
			}
			if(ve[u] + G[u][v].w > ve[v]) {
				//用ve[u]来更新u的所有后继结点v
				ve[v] = ve[u] + G[u][v].w;
			}
		}
	}
	if(topOrder.size() == n) return true;
	else return false;
}

//vl[] 事件最晚发生时间 //取最小
fill(vl,vl + n, ve[n - 1]); //vl数组初始化，初始值为终点的ve值
while(!topOrder.empty()) {
	int u = topOrder.top();
	topOrder.pop();
	for(int i = 0; i < G[u].size(); i++) {
		int v = G[u][i].v;
		if(vl[v] - G[u][i].w < vl[u]) {
			//用u的所有后继结点v的vl值来更新vl[u]
			vl[u] = vl[v] - G[u][i].w;
		}
	}
}
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
45
46
47
//下面代码中未保存活动的最早开始时间e和最迟开始时间l
//原因是e 和 l只用来判断当前活动是否为关键路径
//如果需要保存则在结构体node中添加域e 和 l
int criticalPath() {
	menset(ve, 0, sizeof(ve)); //ve[]初始化
	if(topologicalSort() == false) {
		return -1; //不是有向无环图 返回-1
	}

	/*
	如果事先不知道汇点编号，可以取ve[]的最大值来得到关键路径长度
	int maxLength = 0;
	for(int i = 0; i < n; i++) {
		if(maxLength < ve[i]) {
			maxLength = ve[i];
		}
	}
	fill(vl, vl + n, maxLength);
	别忘了替换函数返回值
	*/

	fill(vl,vl + n, ve[n - 1]);
	while(!topOrder.empty()) {
		int u = topOrder.top();
		topOrder.pop();
		for(int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].v;
			if(vl[v] - G[u][i].w < vl[u]) {
				//用u的所有后继结点v的vl值来更新vl[u]
				vl[u] = vl[v] - G[u][i].w;
			}
		}
	}
	//遍历邻接表的所有边，计算活动的最早开始时间e和最迟开始时间l
	for(int u = 0; u < n; u++) {
		for(int i = 0; i < G[u][i].size(); i++) {
			int v = G[u][i].v, w = G[u][i].w;
			//活动的最早开始时间e和最迟开始时间l
			int e = ve[u], l = vl[v] - w;
			//如果e == l，说明活动u->v是关键活动
			if(e == l) {
				printf("%d->%d\n", u, v); //输出关键活动
			}
		}
	}
	return ve[n - 1]; //返回关键路径长度
}

本文标题:图论算法

文章作者:Kino

发布时间:2019年11月01日 - 11时00分

最后更新:2020年03月17日 - 22时59分

原始链接:https://cybaol.github.io/2019/11/01/Graph/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 图的遍历
    1. 1.1. 深度优先搜索dfs遍历图
    2. 1.2. 广度优先搜索bfs遍历图
  2. 2. 最短路径
    1. 2.1. 单源最短路径
      1. 2.1.1. Dijkstra 算法
      2. 2.1.2. Bellman-Ford 算法
      3. 2.1.3. SPFA 算法
    2. 2.2. 全源最短路径
      1. 2.2.1. Floyd 算法
  3. 3. 最小生成树
    1. 3.1. prim 算法
    2. 3.2. kruskal 算法
  4. 4. 拓扑排序
  5. 5. 关键路径
    1. 5.1. AOV网 和 AOE网
    2. 5.2. 最长路径算法
    3. 5.3. 关键路径算法
,