图论基础知识(二)

主要包括图论涉及到的常用算法模版。
可以说，图论基础知识（一）中，主要探讨了主要的图论知识点，因为ACM比赛的缘故，很多知识体系可以理解成为了比赛而收集得来的，主要的知识结构还是建议学习一下离散数学这门课，之后再涉及相关的数据结构，可能会事半功倍，本节主要将大部分图论的算法收集整合一下，基本都是比赛常用的，欢迎各位收藏。

主要涉及的有最小生成树，最短路径，二分图，连通分量等，首先我得先感谢我的学长将大部分算法收集完成了，我只是在此基础上进行相关的修改完善。

注意：以上内容仅仅只是算法，并不是问题的完整题解，详细经典题解我会在之后补充，可以收集作为模版使用

最小生成树

最小生成树（详细定义参考离散数学以及数据结构），主要涉及的算法有kruskal算法，prim算法在此基础上修正kruskal+ufs，算法如下：

kruskal+ufs

int ufs(int x) {
return f[x] == x ? x : f[x] = ufs(f[x]);
}
int Kruskal(int n,int m) {
int w = 0;
for(int i = 0; i < n; i++)
	f[i] = i;
sort(e,e + m);
for(int i = 0; i < m; i++) {
	int x = ufs(e[i].u),y = ufs(e[i].v);
	if(x != y) {
		f[x] = y;
		w += e[i].w;
	}		
}
return w;
}

prim

int Prim() {
int w = 0;
priority_queue<pair<int, int> > q;
bool l[N] = {0};
l[1] = 1;
q.push(make_pair(0, 1));
for(int k=1; k<n; k++) {
	int u = q.top().second;
	q.pop();
	for(int i=0; i<G[u].size(); i++)
		if(!l[G[u][i]])
			q.push(make_pair(-c[u][i], G[u][i]));
	while(!q.empty() && l[q.top().second])
		q.pop();
	l[q.top().second] = 1;
	w += -q.top().first;
	q.pop();
}
return w;
}

最短路径

有谈到最短路径了，这也是之前我开始准备图论知识的起源吧，话不多说主要算法如下：

Dijkstra+priority_queue

void Dijkstra(int s) {
priority_queue<pair<int, int> > q;
bool l[N] = {0};
l[s] = 1;
fill_n(f, n, INF);
f[s] = 0;
q.push(make_pair(-f[s], s));
while(!q.empty()) {
	int u = q.front().second;
	q.pop();
	for(int i=0; i<G[u].size(); i++) {
		int v = G[u][i];
		if(f[v] > f[u] + c[u][i]) {
			f[v] = f[u] + c[u][i];
			if(!l[v]) {
				l[v] = 1;
				q.push(make_pair(-f[v], v));
			}
		}
	}
}
}

Bellman-Ford(SPFA)

void BellmanFord(int s) { // SPFA
queue<int> q;
bool l[N] = {0};
l[s] = 1;
fill_n(f, n, INF);
f[s] = 0;
q.push(s);
while(!q.empty()) {
	int u = q.front();
	q.pop();
	l[u] = 0;
	for(int i=0; i<G[u].size(); i++) {
		int v = G[u][i];
		if(f[v] > f[u] + c[u][i]) {
			f[v] = f[u] + c[u][i];
			if(!l[v]) {
				l[v] = 1;
				q.push(v);
			}
		}
	}
}
}

FLoyd

void Floyd() {
for(int k=0; k<n; k++)
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}

二分图

ufs 验证 Hungary

bool DFS(int u) {
for(int i=0; i<G[u].size(); i++) {
	int v = G[u][i];
	if(!l[v]) {
		l[v] = 1;
		if(!f[v] || DFS(f[v])) {
			f[v] = u;
			return true;
		}
	}
}
return false;
}
int Hungary() {
int w = 0;
for(int i=0; i<n; i++) {
	fill_n(l, l+n, 0);
	if(DFS(i))
		w++;
}
return w;
}

连通分量

Tarjan stack

stack<int> s;
void Tarjan(int u) {
dfn[u] = low[u] = ++time;
l[u] = 1;
s.push(u);
for(int i=0; i<G[u].size(); i++) {
	int v = G[u][i];
	if(!dfn[v]) {
		Tarjan(v);
		low[u] = min(low[u], low[v]);
	} else if(l[v])
		low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]) {
	w++;
	do {
		int v;
		l[v = s.top()] = 0;
		f[v] = w;
		s.pop();
	} while(u != v);
}
}
void SCC() {
fill_n(dfn, n, 0);
for(int i=0; i<n; i++)
	if(!dfn(i))
		Tarjan(i);
}

网络流

网流量的相关问题，主要阐述一下即可，费用流的问题，可以利用Bellman-Ford找增广路，或者贪心算法即可，最大流问题即用Edmonds-KarpS主要介绍一下最大流问题的算法：
通过BFS的方式来进行增广路径的查找，即每次找步数最少的路径进行残留网络的修改，此方法的复杂度为O(VE^2).

int graph::Edmonds_Karp(int start, int end, int remain_g[][1000], int current_g[][1000])//按BFS找增广路径(即每次找边数最短的)实现Ford_Fulkerson方法
{
   for (int i = 0; i < Pnum; i++)
       for (int j = 0; j < Pnum; j++)
       {
           if (edge[i][j] == INF)
               remain_g[i][j] = 0;
           else
               remain_g[i][j] = edge[i][j];
       }
   int max_flow = 0;
   while (1)
   {
       int visit[1000];
       int pre[1000];//记录节点的前驱，好找路径,其实这里的visit可以不要,就用pre
       memset(visit, 0, sizeof(visit));
       memset(pre, 0, sizeof(pre));
       //bfs在残留网络中找增广路径
       queue<int> q;
       q.push(start);
       while (!q.empty())
       {
           int temp_point = q.front();
           q.pop();
           if (temp_point == end)
               break;
           for (int i = 0; i < Pnum; i++)
           {
               if (remain_g[temp_point][i] > 0 && !visit[i])
               {
                   q.push(i);
                   pre[i] = temp_point;
                   visit[i] = 1;
               }
           }
       }
       //更新残留网络
       if (pre[end] == 0)//end的前驱没有更新，证明没有增广路径了
           break;
       int min = INF;
       for (int temp_point = end; temp_point != start; temp_point = pre[temp_point])
           min = zzMin(remain_g[pre[temp_point]][temp_point], min);
       for (int temp_point = end; temp_point != start; temp_point = pre[temp_point])
       {
           remain_g[pre[temp_point]][temp_point] -= min;
           remain_g[temp_point][pre[temp_point]] = min;//此为负向边
       }
       max_flow += min;
   }
   return max_flow;
}

对应的最小割问题，在求得最大流后得到残留网络，从s开始进行bfs，并将所有经过的点标记，然后在残留网络中找到连接标记的点和非标记的点的边，经过这些边的直线即为一个最小割.(这些边事实上就已经是满流量了,即流量=容量).

//remain_g为找到最大流后得到的残留网络
bool graph::Find_Min_Cut(int start,int remain_g[][1000], vector<int> &s_set, vector<int> &t_set)
{
   int visit[1000];
   memset(visit, 0, sizeof(visit));
   queue<int> s;
   s.push(start);
   while (!s.empty())
   {
       int temp_point = s.front();
       s.pop();
       for (int i = 0; i < Pnum; i++)
           if (remain_g[temp_point][i] > 0 && !visit[i])
           {
               s.push(i);
               visit[i] = 1;
               s_set.push_back(i);
           }
   }
   for (int i = 0; i < Pnum; i++)
       if (!visit[i])
           t_set.push_back(i);
   return true;
}