数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学C++ 程序查找最大边不相交路径数
这是一个 C++ 程序，用于查找最大边不相交路径数，即最短子集路径或两个顶点之间的最大流。
算法
Begin function bfs() returns true if there is path from source s to sink t in the residual graph which indicates additional possible flow in the graph. End Begin function findDisPath() is used to return maximum flow in given graph: A) Initiate flow as 0. B) If there is an augmenting path from source to sink, add the path to flow. C) Return flow. End
示例代码
#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#define n 7
using namespace std;
bool bfs(int g[n][n], int s, int t, int par[])
{
bool visit[n];
memset(visit, 0, sizeof(visit));
queue <int> q;
q.push(s);
visit[s] = true;
par[s] = -1;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v=0; v<n; v++)
{
if (visit[v]==false && g[u][v] > 0)
{
q.push(v);
par[v] = u;
visit[v] = true;
}
}
}
return (visit[t] == true);
}
int findDisPath(int G[n][n], int s, int t)
{
int u, v;
int g[n][n];
for (u = 0; u < n; u++)
{
for (v = 0; v < n; v++)
g[u][v] = G[u][v];
}
int par[n];
int max_flow = 0;
while (bfs(g, s, t,par))
{
int path_flow = INT_MAX;
for (v=t; v!=s; v=par[v])
{
u = par[v];
path_flow = min(path_flow, g[u][v]);
}
for (v = t; v != s; v = par[v])
{
u = par[v];
g[u][v] -= path_flow;
g[v][u] += path_flow;
}
max_flow += path_flow;
}
return max_flow;
}
int main()
{
int g[n][n] = {{0, 6, 7, 1},
{0, 0, 4, 2},
{0, 5, 0, 0},
{0, 0, 19, 12},
{0, 0, 0, 17},
{0, 0, 0, 0,}};
int s=0,d=3;
cout << " There exist maximum" <<" "<< findDisPath(g, s, d)<< " edgedisjoint paths from " << s <<" to "<<d;
return 0;
}输出
There exist maximum 3 edge-disjoint paths from 0 to 3
更新于： 2019-07-30
122 次浏览
广告