图论
发表于：2024-02-04 | 分类： 数据结构与算法

图算法专题

图的存储

  • 邻接矩阵
  • 邻接表

邻接矩阵可以采用一个二维数组G[][]来进行存取数据，而邻接表可以采用链表形式或者vector数组来实现

一般来说对于点数较少的图采用邻接矩阵方式比较方便，而对于点数较多的密集图采用邻接表形式比较方便

图的遍历

深度优先搜素（DFS）

  • 邻接矩阵版
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
49
50
51
52
53
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径
 
void dfs (const vector<vector<int>>& graph, int x, int n) {
    // 当前遍历的节点x 到达节点n 
    if (x == n) { // 找到符合条件的一条路径
        result.push_back(path);
        return;
    }
    for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
        if (graph[x][i] == 1) { // 找到 x链接的节点
            path.push_back(i); // 遍历到的节点加入到路径中来
            dfs(graph, i, n); // 进入下一层递归
            path.pop_back(); // 回溯，撤销本节点
        }
    }
}
 
int main() {
    int n, m, s, t;
    cin >> n >> m;
 
    // 节点编号从1到n，所以申请 n+1 这么大的数组
    vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
 
    while (m--) {
        cin >> s >> t;
        // 使用邻接矩阵 表示无线图，1 表示 s 与 t 是相连的
        graph[s][t] = 1;
    }
 
    path.push_back(1); // 无论什么路径已经是从1节点出发
    dfs(graph, 1, n); // 开始遍历
 
    // 输出结果
    if (result.size() == 0) cout << -1 << endl;
    // for (const vector<int> &pa : result) {
    //     for (int i = 0; i < pa.size() - 1; i++) {
    //         cout << pa[i] << " ";
    //     }
    //     cout << pa[pa.size() - 1]  << endl;
    // }
    for(int i=0;i<result.size();++i) {
        for(int j=0;j<result[i].size() - 1;++j) {
            cout<<result[i][j]<<" ";
        }
        cout<<result[i][result[i].size() - 1]<<"\n";
    }
    return 0;
}
  • 邻接表版
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
#include <iostream>
#include <vector>
#include <list>
using namespace std;

vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径

void dfs (const vector<list<int>>& graph, int x, int n) {

    if (x == n) { // 找到符合条件的一条路径
        result.push_back(path);
        return;
    }
    for (int i : graph[x]) { // 找到 x指向的节点
        path.push_back(i); // 遍历到的节点加入到路径中来
        dfs(graph, i, n); // 进入下一层递归
        path.pop_back(); // 回溯，撤销本节点
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m;

    // 节点编号从1到n，所以申请 n+1 这么大的数组
    vector<list<int>> graph(n + 1); // 邻接表
    while (m--) {
        cin >> s >> t;
        // 使用邻接表 ，表示 s -> t 是相连的
        graph[s].push_back(t);

    }

    path.push_back(1); // 无论什么路径已经是从0节点出发
    dfs(graph, 1, n); // 开始遍历

    // 输出结果
    if (result.size() == 0) cout << -1 << endl;
    for (const vector<int> &pa : result) {
        for (int i = 0; i < pa.size() - 1; i++) {
            cout << pa[i] << " ";
        }
        cout << pa[pa.size() - 1]  << endl;
    }
}

广度优先搜素（BFS）

  1. 邻接矩阵版
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
#define N 10000
#define INF 10000000
int n,G[N][N];//n为顶点数
bool vis[N]={false};
void BFS(int u)
{
	queue<int>q;
	q.push(u);
	vis[u]=true;//标记已入队
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v=0;v<n;v++)
		{
			if(vis[u]==false&&g[u][v]!=INF)
			{
				q.push(v);
				vis[v]=true;
			}
		}
	}
}
void BFSTrave()//遍历整个图
{
	for(int u=0;u<n;u++)
	{
		if(vis[u]==false)
		{
			BFS(u);
		}
	}
}
  1. 邻接表版
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
#define N 1000
#define INF 100000000
vector<int>Adj[N];//图G
bool vis[N]={false};
int n;//顶点数

void BFS(int u)
{
	queue<int>q;
	q.push(u);
	vis[u]=true;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v=0;v<Adj[u].size();v++)
		{
			int z=Adj[u][v];
			if(vis[z]==false)
			{
				q.push(z);
				vis[z]=true;
			}
		}
	}
}
void BFSTrave() //遍历整个图
{
	for(int u=0;u<n;u++)
	{
		if(vis[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
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {
    int m, n, s, t;
    cin >> n >> m;
    vector<int> inDegree(n, 0); // 记录每个文件的入度
 
    unordered_map<int, vector<int>> umap;// 记录文件依赖关系
    vector<int> result; // 记录结果
 
    while (m--) {
        // s->t，先有s才能有t
        cin >> s >> t;
        inDegree[t]++; // t的入度加一
        umap[s].push_back(t); // 记录s指向哪些文件
    }
    queue<int> que;
    for (int i = 0; i < n; i++) {
        // 入度为0的文件，可以作为开头，先加入队列
        if (inDegree[i] == 0) que.push(i);
        //cout << inDegree[i] << endl;
    }
    // int count = 0;
    while (que.size()) {
        int  cur = que.front(); // 当前选中的文件
        que.pop();
        //count++;
        result.push_back(cur);
        vector<int> files = umap[cur]; //获取该文件指向的文件
        if (files.size()) { // cur有后续文件
            for (int i = 0; i < files.size(); i++) {
                inDegree[files[i]] --; // cur的指向的文件入度-1
                if(inDegree[files[i]] == 0) que.push(files[i]);
            }
        }
    }
    if (result.size() == n) {
        for (int i = 0; i < n - 1; i++) cout << result[i] << " ";
        cout << result[n - 1];
    } else cout << -1 << endl;
}

时间复杂度O（n+m）,空间复杂度O（n） n为顶点数，m为边数

用途：

  1. 计算工序最短用时（经典拓扑+dp）
  2. 有向无环图（DAG）判环
  3. 分级（排序、分层）
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
int n, x, index, ans;
const int maxn = 10005;
vector<int> G[maxn];    //邻接链表存图
int f[maxn], t[maxn];    //记录总时长，单位时长
int indegree[maxn]; //记录入度
void Topo_sort() {
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!indegree[i]) {  //入度为0，入队
            q.push(i);
            f[i] = t[i];  //初始化时间
        }
    }
    while (!q.empty()) {
        //先计算该点的时间
        int temp = q.front(); q.pop();
        for (int i = 0; i < G[temp].size(); ++i) {
            --indegree[G[temp][i]]; //子节点的入度全部-1
            f[G[temp][i]] = max(f[G[temp][i]], f[temp] + t[G[temp][i]]); //更新子节点的工序用时
            if (!indegree[G[temp][i]]) q.push(G[temp][i]);   //分层
        }
    }
}
int main() {
    cin >> n; //顶点个数
    for (int i = 1; i <= n; ++i) {
        cin >> index; //工程序号
        cin >> t[index];
        while (cin >> x) {
            if (x == 0) break;
            G[x].push_back(index);  //建图
            ++indegree[index];  //入度+1
        }
    }
    Topo_sort();
    //找出最终答案
    for (int i = 1; i <= n; ++i) ans = max(ans, f[i]);
    cout << ans << endl;
    return 0;
}

DAG判环：只需要新建一个cnt变量来记录队列中pop出来的顶点的个数，设总顶点数为N，若cnt==N，则表明无环，若cnt!=N，则表示有环。

拓扑排序的稳定性

拓扑排序时，若每一次入队的顶点数量均为1，则代表拓扑排序的结果只有一个，排序是稳定的；若每一次入队的顶点的数量不为1，则表示同一阶段有多个入度为0的顶点，这几个顶点的顺序是不固定的，故排序是不稳定的。
题目中若对排序有较严格要求，需要特别注意拓扑排序的稳定性。

并查集

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
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

最短路径

Dijkstra算法（处理单源最短路径）

​ Dijkstra算法用来解决单源最短路径问题，即给定一个图G和起点s，通过算法求出点s到达图中其他顶点的最短路径。其基本思想是对图G（V,E)设置集合S,存放已访问的顶点，然后每次从V-S中选择与顶点s最短距离最小的一个顶点（记为u)，访问并加入集合S。之后，令顶点u为中介点，优化起点s与所有从u所能到达的顶点v之间的最短距离。这样执行n次（n为顶点个数）,知道集合S中包含图中所有起点。

  • 邻接矩阵版
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
49
50
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int G[N][N];
int n,m;
int d[N];
bool vis[N] = {false}; // 标记数组
const int INF = 1000000005;
void Dijkstra(int s) {
	fill(d,d+N,INF);
	d[s] = 0;
	for(int i=1;i<=n;++i) {
		int u = -1,MIN = INF;
		for(int j=1;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=1;v<=n;++v) {
			// 如果v未被访问并且能到达v且使得到达起点s的距离更小
			if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
				d[v] = d[u] + G[u][v];
			}
		}
	}
}
int main() {
	cin>>n>>m;
	// 初始化，慎用memset 
	for( int i=1;i<=n;++i){
		for(int j=1;j<=n;++j) {
			G[i][j] = INF;
		}
	}
	while(m--) {
		int u,v,w;
		cin>>u>>v>>w;
		G[u][v] = w; 
	} 
	Dijkstra(1);
	if(d[n] == INF)cout<<-1<<endl;
	else cout<<d[n]<<endl;
	
	
	return 0;
}
  • 邻接表版
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=100010;
#define INF 0x3f3f3f3f
int n,m;//顶点数 边数
int d[N];//记录起点s到达图中各顶点的最短距离
bool vis[N]={false};//标记数组，判断顶点是否访问
struct Node
{
  int v;//v为边的终点
  int weight;	//边的权值
};
void init()
{
	memset(d,INF,sizeof(d));
	memset(vis,false,sizeof(vis));
}
vector<Node>Adj[N]; //图G Adj[u]存放从顶点u出发可以到达的所有顶点

void Dijkstra(int s)//s为起点
{
	 fill(d,d+N,INF);//fill函数将整个d数组赋值为INF（慎用memset) 
	 d[s]=0;
	 for(int i=1;i<=n;i++)
	{
		int u=-1,MIN=INF;
		for(int j=1;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 j=0;j<Adj[u].size();j++)
		{
			int v=Adj[u][j].v;
			if(vis[v]==false&&Adj[u][j].weight+d[u]<d[v])
			{
				d[v]=d[u]+Adj[u][j].weight;//松弛
			}
		}
    }
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		Node nd;
		nd.v=y;nd.weight=1;//边的权重
		Adj[x].push_back(nd);
	}
	for(int i=1;i<=n;i++)
	{
		Dijkstra(i);
		int maxn=0;
		for(int j=1;j<=n;j++)
		{
           if(d[j]!=INF)
           {
           	maxn=max(j,maxn);//找每个顶点能够到达的最大编号顶点
		   }
		}
		cout<<maxn<<' ';
		init();
	}
	return 0;
}
  • 堆优化版
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<queue>
using namespace std;
const int N=100010;
const int INF=0x3f3f3f3f;
int n,m,s,u,v,w;//顶点数 边数  源点
int d[N];//记录起点s到达图中各顶点的最短距离
bool vis[N]= {false}; //标记数组，判断顶点是否访问
struct Node
{
	int v;//v为边的到达点
	int weight;	//边的权值
	Node(int a,int b)
	{
		v=a;
		weight=b;
	}
};
vector<Node>Adj[N]; //图G Adj[u]存放从顶点u出发可以到达的所有顶点
struct cmp
{
	//注意优先级队列的优先级定义，小根堆要用大于号
	bool operator()(Node n1,Node n2)
	{
		if(n1.weight==n2.weight)
		{
			return n1.v>n2.v;
		}
		else return n1.weight>n2.weight;
	}
};
void Dijkstra(int s)//s为起点
{
	fill(d,d+N,INF);//fill函数将整个d数组赋值为INF（慎用memset)
	d[s]=0;
	priority_queue<Node,vector<Node>,cmp>q;//优先级队列的自定义语法
	Node n1(s,0);
	q.push(n1);
	while(!q.empty())
	{
		Node M=q.top();
		q.pop();
		//特判两种情况
		if(vis[M.v]==true)continue;//已访问过的结点不需要再访问
		if(d[M.v]==INF)break;//不连通
		vis[M.v]=true;
		int v=M.v;
		//松弛
		for (int w = 0; w < Adj[v].size(); ++w)
		{
			if (d[Adj[v][w].v] > d[v] + Adj[v][w].weight)
			{
				d[Adj[v][w].v] = d[v] + Adj[v][w].weight;
				Node K(Adj[v][w].v, d[Adj[v][w].v]);
				q.push(K);
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		Node temp(y,z);
		Adj[x].push_back(temp);
	}
	Dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		cout<<d[i]<<' ';
	}
	return 0;
}

Floyd算法（解决全源最短路径）

该算法用于求任意两点之间的最短路径，也可以来求解一个点是否能到达另一个点。dis[][]数组用于存图。算法核心在于中转站的选择，意为在前v个中转站被允许参与中转的情况下，任意两点可以到达的最短路径，枚举中转站的时候也可以用来判断该点是否位于最短路径当中。注意先初始化dis[][]为INF。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 200;	// 最大定点数 
int dis[N][N];	// dis[i][j] 表示i到j的最短距离 
int n,m;	// 顶点数 	边数 
const int INF = 1000000000;	


void Floyd() {
	for(int k=0;k<n;++k) {	// 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][j] < dis[i][k] + dis[k][j]) {
					dis[i][j] = dis[i][k] + dis[k][j];
				}
			}
		}
	}
} 
int main() {
	int u,v,w;
	fill(dis[0],dis[0] + N * N, INF);	// 初始化
	cin>>n>>m;
	for(int i=0;i<n;++i)dis[i][i] = 0;	// i 到 i 的距离初始化为0 
	while(m--) {
		cin>>u>>v>>w;
		dis[u][v] = w;	// 有向图为例 
	} 
	Floyd();
	for(int i=0;i<n;++i) {
		for(int j=0;j<n;++j) {
			cout<<dis[i][j]<<" ";
		}
		cout<<endl;
	} 
	return 0;
}

求路径

Floyd算法可以多开一个path的二位数组来存放中转站标号，只需要在dp的时候在下面多加一句path[u][w]=v;即可。
在求路径的时候需要用到递归。限制条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        cin >> dis[i][j];
        path[i][j] = -1;
    }
}
//Floyd算法求任意两点最短路径长度
for (int v = 1; v <= n; ++v) {
    for (int u = 1; u <= n; ++u) {
        for (int w = 1; w <= n; ++w) {
            if (dis[u][w] > dis[u][v] + dis[v][w]) {
                dis[u][w] = min(dis[u][w], dis[u][v] + dis[v][w]);
                //  path[u][w]=v;   //记录路径
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
void printPath(int u, int v) {
    if (paht[u][v] == -1) {    //u与v之间已经没有任何中转站，二者已经直接相连了
        cout << "<" << u << "," << v << ">" << endl;
    }
    else {
        int mid = path[u][v]; //中转站
        printPath(u, mid);   //左递归打印u到中转站的路径
        printPath(mid, v);   //有递归打印中转站到v的路径
    }
}

Bellman-Ford算法

Bellman-Ford算法使用于求解单源最短路，该算法可以允许负权值边的存在。Bellman-Ford算法算法思想为进行n - 1次松弛操作，每一次松弛操作都枚举每一条边，对该边的两端顶点路径长度进行修改。以此求出最短路径，但是无法解决存在负权回路的情况，因此还可以检测是否包含负权回路。 时间复杂度为O（nm），其中n为顶点数，m为边数。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;	// 顶点
const int M = 1e4+10;	// 边 
int dis[N], u[M], v[M], w[M];	// 最短距离 M边的起点 M边的终点 M边的权重 
int n,m;	// 顶点数 边数 
int cnt = 1;  // 无向图需要记录边数
void Bellman_Ford(int s) {
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0;
	for(int i=1;i<=n-1;++i) {
		int check = 0;	// 标记 
		// 枚举每一条边 
		for(int j=1;j<=cnt;++j) {
			if(dis[u[j]] + w[j] < dis[v[j]]) {
				dis[v[j]] = dis[u[j]] + w[j];
				check = 1;	// 1说明修改了边 
			}
		}
		if(check == 0)break;	// 0说明不需要继续松弛 
	}
	// 在下面再进行一次循环，如果还存在dis[u[j]] + w[j] < dis[[v]j]则说明存在负权回路 
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=m;++i) {
		int x,y,z; // 输入边
		// 无向图 
		cin>>x>>y>>z; 
		u[cnt] = x, v[cnt] = y, w[cnt] = z;
		cnt++;
		// 有向图则不需要cnt以及下面的两条语句 
		u[cnt] = y, v[cnt] = x, w[cnt] = z;
		cnt++; 
	} 
	Bellman_Ford(1);
	for(int i=1;i<=n;++i) {
		cout<<dis[i]<<" ";
	}
	return 0;
}

SPFA算法

SPFA（Shortest Path Faster Algorithm）算法，是Bellman-Ford算法的队列优化版，时间复杂度较为玄学，O（km），k为常数，平均值为2。理论上讲SPFA可以对Bellman-Ford进行常数级别的优化，但是在算法竞赛当中可能出现卡SPFA时间复杂度使其时间复杂度退化为O（nm）的情况，对于不存在负权值边的图来讲，Dijkstra算法在优先队列优化过后效果稳定且时间复杂度优秀，优先选用Dijkstra。但是对于存在负权值边的图来讲，Dijkstra算法会失效，所以还得使用SPFA。

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
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, s, a, b, w;
struct node {
	node(int v, int w) {
		vertex = v, weight = w;
	}
	int vertex, weight;
};
vector<node> G[maxn];   //邻接链表存图
int dis[maxn];  //记录最终的距离数组
bool mark[maxn];	//记录顶点是否存在于队列之中
void SPFA(int start) {
	//初始化距离为无穷大，原点为0
	for (int i = 1; i <= n; ++i) dis[i] = INF;
	dis[start] = 0;
	queue<int> q;
	q.push(start);
	mark[start] = 1;	//该顶点已经入队
	while (!q.empty()) {
		int v = q.front(); q.pop();
		mark[v] = 0;		//该顶点出队
		for (int w = 0; w < G[v].size(); ++w) {  //松弛
			if (dis[G[v][w].vertex] > dis[v] + G[v][w].weight) {
				dis[G[v][w].vertex] = dis[v] + G[v][w].weight;
				if (!mark[G[v][w].vertex]) {	//可以松弛并且该顶点没有在队列里面
					mark[G[v][w].vertex] = 1;		//顶点入队并且进行mark的记录
					q.push(G[v][w].vertex);
				}
			}
		}
	}
}

SPFA算法判断是否存在负环

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
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理
一定有两个点相同，所以存在环。
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}

最小生成树

Prim算法

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
const int maxn = 5005;
const int INF = 0x3f3f3f3f;
struct node {
    node(int v, int w) {
        vertex = v, weight = w;
    }
    int vertex, weight;
};
struct cmp {
    bool operator()(node n1, node n2) {
        return n1.weight > n2.weight;
    }
};
int n, m, a, b, w, ans;
bool mark[maxn];//标记数组
int dis[maxn];  //存与顶点相连的边的长度
vector<node> G[maxn];
void Prim(int start) {
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    dis[start] = 0;
    priority_queue<node, vector<node>, cmp> q;
    node N(start, 0);
    q.push(N);
    while (!q.empty()) {
        node M = q.top(); q.pop();
        //特判
        if (mark[M.vertex]) continue;    //已访问过的节点不需要再访问
        if (dis[M.vertex] == INF) break;   //图不连通
        mark[M.vertex] = 1;   //标记已访问
        int v = M.vertex;
        //松弛
        for (int i = 0; i < G[v].size(); ++i) {
            //需要特判是否重复选择
            if (dis[G[v][i].vertex] > G[v][i].weight && !mark[G[v][i].vertex]) {
                dis[G[v][i].vertex] = G[v][i].weight;
                node P(G[v][i].vertex, G[v][i].weight);
                q.push(P);
            }
        }
    }
}

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
26
27
28
29
30
31
32
33
34
35
36
const int maxn = 5005;
const int INF = 0x3f3f3f3f;
struct edge {    //创建边结构体
    edge(int _u, int _v, int _w) {
        u = _u, v = _v, w = _w;
    }
    int u, v, w;
};
bool cmp(edge e1, edge e2) {
    return e1.w < e2.w;
}
int n, m, a, b, w, cnt, ans;
vector<edge> E; //存储图的所有边
int father[maxn];   //并查集
int _find(int s) { //查
    while (father[s] != s) s = father[s];
    return s;
}
void merge(int s1, int s2) {    //并
    int f1 = _find(s1), f2 = _find(s2);
    father[max(f1, f2)] = father[min(f1, f2)];
}
void Kruskal() {
    for (int i = 1; i <= n; ++i) father[i] = i;    //初始化每一条边为自己的父亲
    //按照每一条边的权重排序
    sort(E.begin(), E.end(), cmp);
    for (int i = 0; i < E.size(); ++i) { //枚举每一条边
        int _u = E[i].u, _v = E[i].v, _w = E[i].w;
        if (_find(_u) != _find(_v)) {
            cnt++;    //计数器，如果最终cnt!=n-1则图不连通
            ans += _w;
            merge(_u, _v);
        }
        if (cnt == n - 1) break; //全部的边找到了就截断函数
    }
}

Tarjan算法

强连通分量（Strongly Connected Components）

  • 若有向图中有两个点 i 与 j 可以相互到达，则称这两个点强连通，如果图中任意两个点都强连通，则该图称为强连通图。任意一个点自己和自己是强连通的。

  • 非强连通有向图的极大强连通子图称为该图的强连通分量。

  • 根据定义，两个点一定是强连通的，当且仅当它们在同一个环内。环上所有的点都互相强连通。

算法思路

该算法有两个数组比较重要，第一个是时间戳数组dfn[]，该数组是用来记录对应节点第一次被访问的顺序。另一个是追溯值数组low[]，该数组表示了从对应节点出发，所能够访问到的最早时间戳，以便方便我们进行强连通分量的判断。

算法分三步：

  1. 入：指从 x 节点发起Tarjan算法时，记录 x 对应的时间戳，并将 x 入栈。
  2. 回：我们对 x 发起Tarjan算法，对 x 的子节点 y 进行遍历，分以下三种情况：
    • 如果 y 还未被访问，则继续对 y 进行深搜。回溯到 x 的时候，我们需要利用 y 的low值来更新 x 的low值。
    • 如果 y 已经被访问并且 y 在栈中，说明了 y 是 x 的祖先节点或者左子树节点，这个时候我们直接利用 y 的dfn值来更新 x 的low值。
    • 如果 y 已经访问并且不在栈中，表示 y 已经是属于另一个强连通分量，不需要对其进行其他处理了。
  3. 离：在处理完 x 之后，判断 x 是否为一个强连通分量的入口，如果是，则出栈，并且记录相对应的强连通分量。
  4. 根据算法过程容易注意到，因为回溯，所以越往后搜索到的点强连通分量编号越靠前。
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
49
50
51
52
53
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1e4 + 5;
int n, m, a, b, ans;
vector<int> G[maxn];	//邻接表存图
bool instk[maxn];		//判断元素是否在栈中
int stk[maxn], top;	//stk为手写栈，top为栈顶指针
int dfn[maxn], low[maxn], tot;	//时间戳，low值，对应的标记
int scc[maxn], siz[maxn], cnt;	//对应的节点属于哪一个强连通分量，对应的强连通分量的大小，强连通分量的编号
void Tarjan(int x) {
	//入
	dfn[x] = low[x] = ++tot;	//初始化时间戳和追溯值
	stk[++top] = x, instk[x] = 1;	//元素入栈
	//回
	for (int i = 0; i < G[x].size(); ++i) {
		int y = G[x][i];
		if (!dfn[y]) {	//子节点没被访问，访问子节点
			Tarjan(y);	
			low[x] = min(low[x], low[y]);	//利用子节点的追溯值来更新自己的追溯值
		}
		else if (instk[y]) {	//子节点已经在栈中
			low[x] = min(low[x], dfn[y]);	//子节点的时间戳来更新自己的追溯值
		}
	}
	//离
	if (dfn[x] == low[x]) {	//如果该节点是某一个SCC的入口，则对这个SCC进行处理
		int tmp; ++cnt;
		do {
			tmp = stk[top--]; instk[tmp] = 0;	//取栈顶元素，出栈
			scc[tmp] = cnt;	//该顶点属于第cnt个SCC
			++siz[cnt];	//第cnt个SCC的大小加1
		} while (tmp != x);
	}
}



int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> a >> b;
		G[a].push_back(b);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) Tarjan(i);	//如果这个顶点没被访问过，就从它开始发起Tarjan算法
	}
	for (int i = 1; i <= cnt; ++i) {
		if (siz[i] > 1) ++ans;
	}
	cout << ans;
	return 0;
}

Tarjan算法缩点

Tarjan算法的缩点一般是在利用Tarjan算法求出SCC之后进行的操作，通常是对一个节点 i 访问它的子节点 j ，而后判断两个节点是否属于同一个SCC，如果不属于同一个SCC，则记录相应的入度出度，或者直接建新图。

1
2
3
4
5
6
7
8
9
//缩点处理出度入度
for (int i = 1; i <= n; ++i) {
	for (int j = 0; j < G[i].size(); ++j) {
		if (scc[i] != scc[G[i][j]]) {
			din[scc[G[i][j]]]++;	//入度++
			dout[scc[i]]++;		//出度++
		}
	}
}
1
2
3
4
5
6
7
//缩点建新图
for (int i = 1; i <= n; ++i) {
	for (int j = 0; j < G[i].size(); ++j) {
		if (scc[i] != scc[G[i][j]])
			new_G[scc[i]].push_back(scc[G[i][j]]);	//建新图
	}
}

Hierholzer算法

又称插入回路法，用于求解欧拉路和欧拉路径。

时间复杂度O（n+m），空间复杂度O（n），n为顶点数，m为边数。

求解欧拉路的时候需要提前判明该图是否存在欧拉路。判定条件如下：

有向图：

  • 欧拉回路：所有顶点出度入度一致。
  • 欧拉路径：恰好有一个点的出度比入度多1（起点），恰好有一个点的入度比出度多1（终点）。

无向图：

  • 欧拉回路：所有顶点的度数为偶数。
  • 欧拉路径：恰好有两个顶点的度数为奇数。

有向图欧拉路

接下来以邻接链表有向图的欧拉路求解算法进行演示（字典序最小的欧拉路）：

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
49
50
51
52
53
54
55
56
57
const int maxn = 1000005;
int n, m, u, v, start = 1;
bool flag = true; //判定图是否满足要求，默认满足欧拉图要求
int indegree[maxn], outdegree[maxn]; //入度出度
vector<int> G[maxn];    //邻接链表存图
stack<int> ans; //存路径
void judge_path() {
    int cnt1 = 0, cnt2 = 0;  //出度比入度多的顶点个数，入度比出度多的顶点个数
    for (int i = 1; i <= n; ++i) {
        if (indegree[i] == outdegree[i]) continue; //出度入度相等
        if (indegree[i] + 1 == outdegree[i]) {   //起点
            cnt1++;
            start = i;    //记录起点
        }
        else if (indegree[i] == outdegree[i] + 1) cnt2++;    //终点
        else {  //其他条件不满足欧拉图要求
            flag = false;
            break;
        }
    }
    if (!((cnt1 == 1 && cnt2 == 1) || (cnt1 == 0 && cnt2 == 0))) flag = false;   //欧拉路径和欧拉回路情况判定
}
void dfs(int s) {
    for (vector<int>::iterator it = G[s].begin(); it != G[s].end();) {
        int next = *it;   //取点
        it = G[s].erase(it);  //删边
        dfs(next);  //深搜继续
    }
    ans.push(s);    //无法再搜索了，此时记录节点，回溯
}
int main() {
    cin >> n >> m;  //点数和边数
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v;
        G[u].push_back(v);  //建图
        ++outdegree[u]; //记录出度
        ++indegree[v];  //记录入度
    }
    juede_path();   //判定该图是否为欧拉图
    if (!flag) {
        cout << "No" << endl;
    }
    else {
        //排序
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
        }
        dfs(start);
    }
    //输出
    while (!ans.empty()) {
        int temp = ans.top();
        cout << temp << ' ';
        ans.pop();
    }
    return 0;
}

无向图欧拉路

无向图欧拉路，使用了并查集特判图是否连通。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
const int maxn = 10005;
int n, m, a, b, start = 1;
bool flag = true; //默认满足欧拉图要求
int degree[maxn], father[maxn];    //顶点的度，father为并查集，用于判断图是否连通
vector<int> G[maxn];
stack<int> ans;
struct edge {    //边结构体，用于记录无向边的信息
    edge(int _u, int _v) { u = _u, v = _v; }
    bool operator<(edge e1)const {
        if (u == e1.u) return v < e1.v;
        return u < e1.u;
    }
    int u, v;
};
set<edge> E;    //储存边的信息
int _find(int s) {    //查
    while (father[s] != s) s = father[s];
    return s;
}
void _merge(int s1, int s2) {        //并
    int f1 = _find(s1), f2 = _find(s2);
    father[max(f1, f2)] = father[min(f1, f2)];
}
void judge_path() {
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        father[i] = i;    //初始化并查集数组
        if (degree[i] & 1) {
            cnt++;  //度数为奇数的点
            start = i;
        }
    }
    for (set<edge>::iterator it = E.begin(); it != E.end(); it++) {    //并
        edge tmp = *it;
        _merge(tmp.u, tmp.v);
    }
    for (int i = 1; i <= n; ++i) {
        int f = _find(i);
        if (f != 1) {    //判断图不连通
            flag = false;
            break;
        }
    }
    if (!(cnt == 0 || cnt == 2)) flag = false;    //度数有除了0和2以外的，不是欧拉图
//    if (cnt == 2 && !(degree[1] & 1)) flag = false;
}
void dfs(int start) {
    for (int i = 0; i < G[start].size(); ++i) {
        edge _find(min(start, G[start][i]), max(start, G[start][i]));
        set<edge>::iterator it = E.find(_find);
        if (it != E.end()) {   //边存在
            E.erase(it);
            dfs(G[start][i]);
        }
    }
    ans.push(start);    //回溯
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
        E.insert(edge(min(a, b), max(a, b)));    //储存边
        degree[a]++;
        degree[b]++;
    }
    judge_path();
    if (!flag) {    //无法画出欧拉路
        cout << "-1" << '\n';
    }
    else {
        //排序，保证路径的字典序最小
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
        }
        dfs(start);
        while (!ans.empty()) {
            int temp = ans.top();
            cout << temp << ' ';
            ans.pop();
        }
    }
    return 0;
}
图论
上一篇:
java笔记
下一篇:
数学问题

    • Copyright © 2022 hnuyl16 | Powered by Hexo | Theme Bamboo