I've been trying to make this program save the vertices that make the cycle in the graph. But I'm kind of a newbie in algorithms and achieving that functionality seems a bit complex when using BFS. The code below successfully finds cycles, but the question is how to modify this code so I can print all the vertices that make the cycle?
#include <bits/stdc .h>
using namespace std;
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
bool isCyclicConntected(vector<int> adj[], int s,
int V, vector<bool>& visited)
{
// Set parent vertex for every vertex as -1.
vector<int> parent(V, -1);
// Create a queue for BFS
queue<int> q;
// Mark the current node as
// visited and enqueue it
visited[s] = true;
q.push(s);
while (!q.empty()) {
// Dequeue a vertex from queue and print it
int u = q.front();
q.pop();
// Get all adjacent vertices of the dequeued
// vertex u. If a adjacent has not been visited,
// then mark it visited and enqueue it. We also
// mark parent so that parent is not considered
// for cycle.
for (auto v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
parent[v] = u;
}
else if (parent[u] != v)
return true;
}
}
return false;
}
bool isCyclicDisconntected(vector<int> adj[], int V)
{
// Mark all the vertices as not visited
vector<bool> visited(V, false);
for (int i = 0; i < V; i )
if (!visited[i] && isCyclicConntected(adj, i,
V, visited))
return true;
return false;
}
// Driver program to test methods of graph class
int main()
{
int V = 4;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 1, 2);
addEdge(adj, 2, 0);
addEdge(adj, 2, 3);
if (isCyclicDisconntected(adj, V))
cout << "Yes";
else
cout << "No";
return 0;
}
CodePudding user response:
You could use the parent
links to reconstruct the cycle.
When two BFS paths meet, then these two paths can each be reconstructed by following the parent
link in tandem, until a common node is encountered. The lengths of these two paths can either be equal (the cycle is even), or differ by 1 (the cycle is odd). If you do the tandem walk via the mutual parent
links in the right way, you will always encounter the "top" of the cycle.
The nodes of the cycle will be listed in a natural order when you use a deque: the nodes coming from the first path can be pushed to the front, while the nodes of the other path to the back.
You don't actually need a separate visited
vector: you can also use parent
for this purpose. True, the first node you start the BFS on, will then not be marked as visited, but there is no way to visit it as the end point of a cycle, as BFS will go through all edges from that source node, and does not allow to use any of those edges to visit the source node. So using parent
for that purpose is enough.
Here is your code adapted with those ideas:
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
bool isCyclicConnectedHelper(vector<int> adj[], int s,
int V, vector<int>& parent,
deque<int> &cycle)
{
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : adj[u]) {
if (parent[v] == -1) { // Not yet visited
parent[v] = u;
q.push(v);
}
else if (parent[u] != v) { // Not the same edge
// Two paths meet: unwind both of them at both sides of a deque:
while (u != v) {
cycle.push_front(v);
v = parent[v];
if (u == v) break;
cycle.push_back(u);
u = parent[u];
}
cycle.push_front(u);
return true;
}
}
}
return false;
}
bool isCyclicConnected(vector<int> adj[], int V, deque<int> &cycle)
{
vector<int> parent(V, -1);
for (int i = 0; i < V; i ) {
if (parent[i] == -1) {
if (isCyclicConnectedHelper(adj, i, V, parent, cycle)) {
return true;
}
}
}
return false;
}
// Driver program to test methods of graph class
int main()
{
int V = 5;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 1, 2);
addEdge(adj, 2, 4);
addEdge(adj, 3, 4);
addEdge(adj, 4, 1);
deque<int> cycle;
if (isCyclicConnected(adj, V, cycle)) {
cout << "The graph has a cycle:";
for (auto v : cycle) {
cout << " " << v;
}
} else {
cout << "The graph has no cycle.";
}
cout << "\n";
return 0;
}
NB: I would suggest defining adj
as vector<vector<int>>
and adjust addEdge
so it will extend that vector as needed. That way you also get rid of V
.