图论『代码模板』

发表于 | 阅读次数:
字数统计: 1,111 字

这篇主要总结一下图论有关的代码模板；
主要由以下几个部分：

  • 图的建立和读入

  • 图的遍历

    • DFS
      • BFS

  • 图的最短路问题

    • Floyd 算法（多源最短路可带负环）（可求图的连通性）O(n*n*n)
      • Dijstra 算法（单源最短路径不可带负环）（可进行堆优化） O(n*n)
      • Bellman-ford 算法（单源最短路可判负环）O(n*m)
      • SPFA 算法 （单源最短路可判断负环）O(n*m)

  • 图的最小生成树问题(MST)

    • kruskal 算法
      • 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
struct node
{
	int y,v,next;//y为这条边的终点编号,v为权值，next表示同起点下条边的编号是多少
}e[MAXN+10]; //边表

int lin[MAXN+10];//起点表
int len=0;//表示边的总条数

inline void insert(int xx,int yy,int vv)//xx为起点，yy为终点，vv为边的权值,在x与y之间插入一条权值为v的边
{
	e[++len].next=lin[xx]; lin[xx]=len;
	e[len].y=yy; e[len].v=vv;
}

inline void init()
{
	scanf("%d%d",&n,&m);//一共n个顶点，m条边
	memset(e,0,sizeof(e));
	memset(lin,0,sizeof(lin));
	for (int i=1;i<=n;i++)
	{
		int xx,yy,vv;
		scanf("%d%d%d",&xx,&yy,&vv);
		insert(xx,yy,vv);
		//insert(yy,xx,vv)//如果为无向图的话需要插入两遍；
	}
}

以上为一个图的读入处理，注意无向图两条边都要互相连通。

还有一个比较重要的循环可以遍历
以下是bfs和dfs遍历两种方法

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void dfs(int p)
{
	bool f[MAXN];
	memset(f,false,sizeof(f));
	for (int i=lin[p];i;i=e[i].next)
	{
		if (!f[e[i].y])
		{
			f[e[i].y]=true;
			dfs(e[i].y);
		}
	}
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void bfs(int p)
{
	int head=0;tail=1;
	int queue[MAXN];
	bool f[MAXN];
	queue[1]=p;f[p]=true;
	while(h++<tail)
		for (int i=lin[queue[h]];i;i=e[i].next)
			if (!f[e[i].y])
			{
				f[e[i].y]=true;
				queue[++tail]=e[i].y;
			}
}

最短路问题的几种常用方法：

floyd

1
2
3
4
5
6
7
inline void floyd()
{
	for (int k=1;k<=n;k++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
					dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

floyd最短路路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 有关于如何使用floyd储存最短路路径的问题
inline void floyed()
{
	for (int k=1;k<=n;k++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
					if (d[i][k]+d[k][j] < d[i][j])
					{
						d[i][j]=d[i][k]+d[k][j];
						path[i][j] = pah[k][j];// 记录前驱点
					}
}

void dfs(int i,int j)// 根据path数组里存的每个点的前驱点来倒序输出。
{
	if (i == j) 
    	printf("%d ",i);
	else if (path[i][j] > 0)
    {
    	dfs(i,path[i][j]);
		printf("%d ",j)
	}
}

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
inline void Dijkstra(int x)
{
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++)	dis[i]=INF;
	dis[x]=0;
	for (int i=1;i<n;i++)
	{
		int minn=INF;
		int k=0;
		for (int j=1;j<=n;j++)
		{
			if((!vis[j]) && (dis[j]<minn))
			{
				minn=dis[j];
				k=j;
			}
		}
		if (k == 0)return;
		vis[k]=1;
		for (int j=head[k];j;j=e[j].next)//用邻接表来存图 三角形原理进行更新
			if (!vis[e[j].y] && dis[e[j].y]>(e[j].v+dis[k]))
				dis[e[j].y]=e[j].v+dis[k];
	}
}

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
void SPFA(int x)
{
	queue<int> q;
	for (int i = 1; i <= n; ++i)
	{
		dis[i] = INF;
		vis[i] = 0;
	}
	q.push(x); dis[x] = 0; vis[x] = 1;
	while (!q.empty())
	{
		int u = q.front();
		q.pop(); vis[u] = 0;
		for (int j = lin[u]; j; j = e[j].next)
		{
			int v = e[j].y;
			if (dis[v] > dis[u] + e[j].v)
			{
				dis[v] = dis[v] +e[j].v;
				if (vis[v] == 0)
				{
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}

Kruskal算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline int find(int x)	{	return f[x] == x ? x : f[x] = find(f[x]);	}
inline bool cmp(egde a,edge b)	{	return a.w < b.w;	}
void Kruskal()
{
	sort(e, e+len, cmp);  //把边按照权值从小到大排序。
	for (int i=1;i<=n;i++)
		f[i]=i;	//初始化并查集。
	for (int i=1;i<=len;i++)
	{
		int x = find(e[i].u), y = find(e[i].v);
		if (x != y) {	//如果不在一个连通分量中，那么加上这条边就不会形成环，于是加上这条边，并且合并。
			ans+=e[i].w;  f[y]=x;
		}
	}
}