图论算法详解

一、图的表示

1.1 邻接矩阵

一个一维数组存储顶点。一个二维数组存储边。
稠密图首选邻接矩阵。如果顶点太多了，比如说有100000个顶点，要开辟mpt[100000][100000]这么大的数组，空间超出限制，则考虑用邻接表。同时，如果图比较稀疏，也可考虑用邻接表。
下面演示邻接矩阵的存储过程。

#include <bits/stdc++.h>
using namespace std;

int mpt[105][105];  
int n,m;  //n个点,m条边 
# define INF  999

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
    	if(n==0&&m==0) break;
    	/*---------初始化------------*/
    	for(int i=1;i<=n;i++){  //横纵坐标都从1开始 
    		for(int j=1;j<=n;j++){
    			if(i==j) mpt[i][j]=0;
    			else mpt[i][j]=INF;  //暂且先写着INF 
			}
		}
		/*----------手动赋值-----------*/
		for(int i=1;i<=m;i++){  //输入m条边 
			int a,b,c;  //起点，重点，权重
			scanf("%d%d%d",&a,&b,&c);
			if(c<mpt[a][b]){//当有重边时，存储权值最小的那个
				mpt[a][b]=c;
				mpt[b][a]=c; //无向图 
			} 
		}
		/*---------存储完毕后进入相应函数---------*/
		//floyd();
		
	}
	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

1.2 邻接表

一个一维数组存储顶点。用vector或者单链表表示边。
以单链表为例，如果边没有权重，那么结构体有2个元素，一个是data，存储与哪个顶点相连。一个是next，指向下一条边；如果有权重，那么结构体就3个元素，多了一个权重。

二、并查集

2.1 可套用的样题

输入样例
4 3
2 3
4 3
3 3
输出样例
1

再看两个例子。思路就是把已经联通的所有点看成一个点（集合），假如一共有N个这样的点（集合），那么还需要N-1条边（左图需要1条，右图需要2条）

所有联通的点生成一颗子树，子树的根作为他们的祖宗。
也就是说，输入给出了两个点x,y（一条边），我们写一个找祖宗的函数find(x)，如果两个点的祖宗相同，那么他俩就是联通的。

如果两个点的祖宗不同，那么我们就得让他俩连到一起。形象化的方法是将左边（或右边）作为子树连接到右边（左边）的根节点上去。
总结成一句话就是：我祖宗认你祖宗当爸爸!

具体实现的代码模板如下

#include <bits/stdc++.h>
using namespace std;

int fa[1005];  //x的父亲结点结点,从fa[1]开始记录 

int find(int x){  //寻找祖宗结点 
	if(x==fa[x]) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}

int main()
{
    int N,M;  //N个城市,M条边 
    while(scanf("%d%d",&N,&M)!=EOF){
    	if(N==0) break;
    	/*------初始化-------*/
    	for(int i=1;i<=N;i++){
    		fa[i]=i;  //先把自己的父亲设为自己 
		}
		/*------*/
		int sum=0;  //有用的边的个数
		for(int i=0;i<M;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			int fx=find(x);  //x的祖宗 
			int fy=find(y);  //y的祖宗，如果y和x连在一起，那么他俩的祖宗应该是同一个 
			/*
			  如果他俩没连在一起，就把他俩连起来 （共用同一个祖宗）
			  也可以这样理解：把x所在的部分作为子树 ，连接到 y所在部分的根上 
			*/
			if(fx!=fy){  // 
				fa[fx]=fy;  //或者fa[fy]=fx 
				sum++;  //本来有N个集合，加一条新的联通边就少一个集合，一共少了sum个集合 
			}
		}	
		printf("%d\n",N-sum-1);  //需要多少条路		 
	}
    
	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

三、最小生成树（ 一般是无向图 ）

• 最小生成树问题就是用一条最短的路径把给你的图中所有的顶点连接起来，这不就是一颗树嘛，因为所用路径最短，所以又叫最小生成树。
• 99%的最小生成树问题都可以用Kruskal方法(贪心+并查集)解决，所以就不学prim了吧。

测试用例输入
3 3
1 2 1
1 3 2
2 3 4
输出
3

思路：

（1）首先是贪心的思想，先把最低成本的边连起来，这就需要对所有边的成本进行一个排序。
（2）从小边开始挑选能连在一起并且不构成环的。这就需要用到并查集的方法，判断这条边的两个点是否已经在一个集合里了（拥有共同的祖宗），如果在一个集合里，那么这条边不能要，否则成环了。

#include <bits/stdc++.h>
using namespace std;

const int maxn=105;
//边结构体数组 
struct node{
	int u,v,w;  //点，点，权重 
}edge[maxn*maxn];

int fa[1005];  //x的父亲结点结点,从fa[1]开始记录
int find(int x){  //寻找祖宗结点 
	if(x==fa[x]) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}

bool cmp(node a,node b){
	return a.w<b.w;  //自定义从小到大进行排序 
}

int main()
{
    int N,M;  //M条边,N个城市 
    while(scanf("%d%d",&M,&N)!=EOF){
    	if(M==0) break;
    	/*------初始化-------*/
    	for(int i=1;i<=N;i++){
    		fa[i]=i;  //先把自己的父亲设为自己 
		}
		for(int i=0;i<M;i++){
			scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
		}
		/*------排序-------*/
		sort(edge,edge+M,cmp);  //sort(first,last,自定义比较函数)[first,last)是左闭右开区间 
		/*-----生成最小生成树------*/
		int sum=0;  //统计总路径 
		int count=0; //有必要的话，可以统计边的数量
		for(int i=0;i<M;i++){
			int fu=find(edge[i].u);
			int fv=find(edge[i].v);
			if(fu!=fv){  //给他俩连上
				fa[fu]=fv;
				sum=sum+edge[i].w; 
				count++;
			}
		}
		if(count<N-1)  //N个点相连需要N-1条边	 
			printf("不能生成");
		else //count==N-1
			printf("总路径为：%d",sum);
		
	}
    
	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

补充一下sort函数的基本用法。如果我要用sort函数给数组排序，不给sort第三个参数就默认是从小到大排序的：

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int a[10]={1,6,3,7,8,2};
	sort(a,a+6);  //左闭右开区间 
	for(int i=0;i<6;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

如果我不用sort排序，而是采用优先队列的方式，代码如下。

#include <bits/stdc++.h>
using namespace std;

const int maxn=105;
//边结构体数组 
struct node{
	int u,v,w;  //点，点，权重 
	bool operator< (const node&a) const{
		return w>a.w;
	}
};

int fa[1005];  //x的父亲结点结点,从fa[1]开始记录
int find(int x){  //寻找祖宗结点 
	if(x==fa[x]) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}

int main()
{
	priority_queue<node> q;
    int N,M;  //M条边,N个城市 
    while(scanf("%d%d",&M,&N)!=EOF){
    	if(M==0) break;
    	/*------初始化-------*/
    	for(int i=1;i<=N;i++){
    		fa[i]=i;  //先把自己的父亲设为自己 
		}
		node temp;
		for(int i=0;i<M;i++){
			scanf("%d%d%d",&temp.u,&temp.v,&temp.w);
			q.push(temp);
		}
	
		/*-----生成最小生成树------*/
		int sum=0;  //统计总路径 
		int count=0; //有必要的话，可以统计边的数量
		for(int i=0;i<M;i++){
			node temp=q.top();
			q.pop();
			int fu=find(temp.u);
			int fv=find(temp.v);
			if(fu!=fv){  //我祖宗认你祖宗当爸爸 
				fa[fu]=fv;
				sum=sum+temp.w; 
				count++;
			}
		}
		if(count<N-1)  //N个点相连需要N-1条边	 
			printf("不能生成");
		else //count==N-1
			printf("总路径为：%d",sum);
		
	}
    
	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

四、最短路径（ 一般是有向图，模板背有向图的！）

4.1 Floyd算法

Floyd算法的应用范围：
（1）出现负权值的边（Dijskla就不行）
（2）

下面给出一个模板题（无向图）：