我有兴趣在连接的无向图中找到循环总数和循环长度。我可以使用 DFS 吗?还是DFS只能找到一个循环?任何代码肯定会有所帮助。
Hassaan Khaliq
问问题
1775 次
2 回答
0
于 2009-06-30T07:31:32.520 回答
0
从图论我们知道:
- 如果图的顶点数量多于边的数量,则不存在环(闭合轮廓)。
- 如果图的顶点数等于边数,则图只有一个环。
- 如果图的顶点数小于边数,则图有多个闭合轮廓。
这个问题可以解决,使用算法深度优先搜索:
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int maximumSize=40;
vector<vector<int>> visited(maximumSize, vector<int>(maximumSize, 0));
vector<int> graph[maximumSize], closedContour, temporary;
int vertices, edges;
set<vector<int>> contours;
void showContentSetVector(set<vector<int>> input)
{
for(auto iterator=input.begin(); iterator!=input.end(); ++iterator)
{
for(auto item : *iterator)
{
cout<<item<<", ";
}
cout<<endl;
}
return;
}
bool compare(int i,int j)
{
return (i<j);
}
void createGraph()
{
cin>>vertices>>edges;
int vertex0, vertex1;
for(int i=1; i<=edges; ++i)
{
cin>>vertex0>>vertex1;
graph[vertex0].push_back(vertex1);
graph[vertex1].push_back(vertex0);
}
return;
}
void depthFirstSearch(int initial, int current, int previous)
{
if(visited[initial][current]==1)
{
for(int i=0; i<temporary.size(); ++i)
{
if(temporary[i]==current)
{
for(int j=i; j<temporary.size(); ++j)
{
closedContour.push_back(temporary[j]);
}
}
}
sort(closedContour.begin(), closedContour.end(), compare);
contours.insert(closedContour);
closedContour.clear();
return;
}
visited[initial][current]=1;
temporary.push_back(current);
for(int next : graph[current])
{
if(next==previous)
{
continue;
}
depthFirstSearch(initial, next, current);
}
temporary.pop_back();
return;
}
void solve()
{
createGraph();
for(int vertex=1; vertex<=vertices; ++vertex)
{
temporary.clear();
depthFirstSearch(vertex, vertex, -1);
}
cout<<"contours <- ";
showContentSetVector(contours);
return;
}
int main()
{
solve();
return 0;
}
结果如下:
contours <-
1, 2, 3, 4,
6, 7, 8,
于 2021-12-10T12:09:30.683 回答