【算法】图论学习笔记与代码实现
这学期两门主课 算法设计与分析（Algorithm and Analysis，ADA） 和 图论与算法（Graph Theory and Algorithms, GTA） 都涉及到很多经典图论问题以及相关代码实现，遂写下此文，以记录学习过程，随缘更新。
深度优先遍历（经典DFS）：
从图中某一个节点出发，如果有未探索的邻居节点，则选择其中应该进行深入探索（其他节点暂时不管），每到一个新的节点则递归进行上述过程。当探索无法继续时（当前节点的所有邻居都在前面的探索过程中被标记过），则沿原路径回退。回退到某个节点时，若它还有其他的邻居节点没有探索，则继续深入探索。
使用白色，黑色，灰色记录每个节点的状态：
白色：表示一个节点尚未被遍历；
灰色：表示一个节点已经被遍历到，但是对于它的遍历尚未结束；即该节点还有若干邻居节点等待遍历，而当前算法正在递归处理其中一个邻居节点；
黑色：表示一个节点的所有邻居已经完成遍历，其自身的遍历也结束。
框架代码（包括封装和实现两部分）：
具体实现（根据DFS遍历顺序简单输出一下各个节点的编号）：
// DFS
#include
#define N 10000
using namespace std;int graph[N][N];
int color[N]; // 0 white, 1 grey, 2 black
int n, m;void dfs(int v)
{color[v] = 1;for (int i = 1; i <= n; i++){if (i != v && graph[v][i] == 1){if (color[i] == 0){dfs(i);}}}cout << v << " ";color[v] = 2;
}void my_dfs()
{for (int i = 1; i <= n; i++){if (color[i] == 0)dfs(i);}cout << endl;
}int main()
{cin >> n >> m;for (int i = 0; i < m; i++){int x, y;cin >> x >> y;graph[x][y] = 1;}my_dfs();return 0;
}/*
input：
7 13
1 2
1 3
1 6
2 3
2 4
4 1
4 3
5 3
5 7
6 1
6 3
7 4
7 5output:
3 4 2 6 1 7 5
*/ 广度优先遍历（BFS）：
从图中某个节点出发，首先处理该节点指向邻居的所有边，然后将所有邻居放入一个调度器——队列（queue）中，接着处理该节点。下一个遍历的节点从当前被发现但未被处理的点中选出，即队列的首个节点，然后将其邻居节点依次放入队尾，处理该节点自身。重复以上过程，直到队列为空，所有节点均被处理完毕。
仍然以上面的图为例，输出BFS顺序遍历每个节点的值：
// BFS
#include
#include
#define N 10000
using namespace std;int graph[N][N];
int color[N]; // 0 white, 1 grey, 2 black
int parent[N];
int dis[N];
int n, m;void bfs(int v)
{queue que;color[v] = 1; // greydis[v] = 0; // 源点que.push(v);while(!que.empty()){int w = que.front();que.pop();for (int i = 1; i < n; i++){if (i != w && graph[w][i] == 1){if (color[i] == 0){color[i] = 1; //greyparent[i] = w;dis[i] = dis[w] + 1;que.push(i);}}}cout << w << " ";color[w] = 2; // black}
}void my_bfs()
{for (int i = 1; i <= n; i++){color[i] = 0;parent[i] = 0;dis[i] = 0;}for (int i = 1; i <= n; i++){if (color[i] == 0)bfs(i);}cout << endl;
}int main()
{cin >> n >> m;for (int i = 0; i < m; i++){int x, y;cin >> x >> y;graph[x][y] = 1;}my_bfs();return 0;
}/*
input：
7 13
1 2
1 3
1 6
2 3
2 4
4 1
4 3
5 3
5 7
6 1
6 3
7 4
7 5
output:
1 2 3 6 4 5 7
*/ 网络中的最大流：
题目描述：
给定n个点，m条有向边，给定每条边的容量，求从点s到点t的最大流
输入：
第一行四个整数n，m，s，t。
接下来的m行，每行三个整数u，v，c，表示u到v，流量为c的一条边，
输出：
输出点s到点t的最大流。
样例输入 ：
7 14 1 7 1 2 5 1 3 6 1 4 5 2 3 2 2 5 3 3 2 2 3 4 3 3 5 3 3 6 7 4 6 5 5 6 1 6 5 1 5 7 8 6 7 7
样例输出 ：
14
提示：
1<=n<=100，1<=m<=5000，0<=c<=2147483647
#include
#include
using namespace std;const int N = 10001, E = 200001;int n, m, s, t;
long long ans = 0;
long long cnt = 1, first[N], nxt[E], to[E], val[E];inline void addE(int u, int v, long long w)
{to[++cnt] = v;val[cnt] = w;nxt[cnt] = first[u];first[u] = cnt;
}int dep[N], q[N], l, r;bool bfs()
{ memset(dep, 0, (n + 1) * sizeof(int));q[l = r = 1] = s;dep[s] = 1;while (l <= r) {int u = q[l++];for (int p = first[u]; p; p = nxt[p]) {int v = to[p];if (val[p] and !dep[v]) { dep[v] = dep[u] + 1;q[++r] = v;}}}return dep[t];
}long long dfs(int u, long long in)
{if (u == t)return in;long long out = 0;for (int p = first[u]; p and in; p = nxt[p]){int v = to[p];if (val[p] and dep[v] == dep[u] + 1) {long long res = dfs(v, min(val[p], in));val[p] -= res;val[p ^ 1] += res;in -= res;out += res;}}if (out == 0)dep[u] = 0;return out;
}int main()
{cin >> n >> m >> s >> t;for (int i = 1; i <= m; i++) {int u, v; long long w;cin >> u >> v >> w;addE(u, v, w);addE(v, u, 0);}while (bfs())ans += dfs(s, 1e18);cout << ans << endl;return 0;
}
/**************************************************************Problem: 1006User: 201830210Language: C++Result: 正确Time:56 msMemory:0 kb
****************************************************************/ 二分图中的最大匹配问题：
题目描述：
给定一个二分图，其左部点的个数为n，右部点的个数为m，边数为e，求其最大匹配的边数。
左部点从1至n编号，右部点从1至m编号。
输入：
输入的第一行是三个整数，分别代表n,m,e。
接下来输入e行，每行两个整数u,v，表示存在一条连接左部点u和右部点v的边。
输出：
输出一个整数，代表二分图最大匹配的边数。
样例输入：
4 2 7 3 1 1 2 3 2 1 1 4 2 4 1 1 1
样例输出：
2
提示：
1<= n,m <=100
#include
#include
#include
#include
using namespace std;int n,m;
int cnt=2;
int alist[6000001];
struct data
{int v;int next;int value;
}edge[6000001];void add(int u,int v,int value)
{edge[cnt].v=v;edge[cnt].value=value;edge[cnt].next=alist[u];alist[u]=cnt++;return ;
}
int h[1000001];
int q[1000001];bool bfs()
{int x,next;memset(h,-1,sizeof(h));int head=0,tail=1;q[head]=1;h[1]=0;while(head 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！