bfs to detect cycle in undirected graph
#include <iostream>
#include <list>
#include <queue>
using namespace std;
class Graph {
int V;
list<int> *adj;
public:
Graph(int V);
void addEdge(int v, int w);
bool isCyclic();
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v);
}
bool Graph::isCyclic() {
vector<bool> visited(V, false);
vector<int> parent(V, -1);
queue<int> q;
for (int i = 0; i < V; i++) {
if (!visited[i]) {
visited[i] = true;
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto it = adj[u].begin(); it != adj[u].end(); ++it) {
if (!visited[*it]) {
visited[*it] = true;
q.push(*it);
parent[*it] = u;
} else if (parent[u] != *it) {
return true;
}
}
}
}
}
return false;
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
if (g.isCyclic())
cout << "Graph contains cycle\n";
else
cout << "Graph doesn't contain cycle\n";
return 0;
}
Explanation:
- The code defines a C++ class Graph to represent an undirected graph and detect cycles in it using the breadth-first search (BFS) algorithm.
- The class has a constructor to initialize the number of vertices and an array of adjacency lists to store the connections between vertices.
- The addEdge
method is used to add edges between vertices in the graph.
- The isCyclic
method uses BFS to detect cycles in the graph. It maintains a queue to perform BFS traversal and checks for cycles by keeping track of visited vertices and their parent vertices.
- The main function creates a graph with 4 vertices and adds edges between them. It then calls the isCyclic
method to determine if the graph contains a cycle and prints the result.