using System.Collections.Generic;
_adj = new LinkedList<int>[ V ];
for (int i = 0; i < _adj.Length; i++) {
_adj[i] = new LinkedList<int>();
public void AddEdge(int v, int w)
bool[] visited = new bool[_V];
for (int i = 0; i < _V; i++)
LinkedList<int> queue = new LinkedList<int>();
LinkedList<int> list = _adj[s];
void DFSUtil(int v, bool[] visited)
LinkedList<int> vList = _adj[v];
bool[] visited = new bool[_V];
Boolean isCyclicUtil(int v, Boolean[] visited,
foreach(int i in _adj[v])
if (isCyclicUtil(i, visited, v))
Boolean[] visited = new Boolean[_V];
for (int i = 0; i < _V; i++)
for (int u = 0; u < _V; u++)
if (isCyclicUtil(u, visited, -1))
static void Main(string[] args)
Console.Write("Following is Breadth First "
+ "Traversal(starting from "
"Following is Depth First Traversal "
+ "(starting from vertex 2)");
Console.WriteLine("Graph contains cycle");
"Graph doesn't contain cycle");
The only catch here is, that, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we divide the vertices into two categories:
A boolean visited array is used to mark the visited vertices. For simplicity, it is assumed that all vertices are reachable from the starting vertex.
BFS uses a queue data structure for traversal.
Implementation of BFS traversal on Graph:
Breadth_First_Search( Graph, X )
Process all the neighbors of Y, For all the neighbors Z of Y
If Z is not visited, Q. enqueue( Z )
Follow the below method to implement BFS traversal.
Declare a queue and insert the starting vertex.
Initialize a visited array and mark the starting vertex as visited.
Follow the below process till the queue becomes empty:
Remove the first vertex of the queue.
Mark that vertex as visited.
Insert all the unvisited neighbors of the vertex into the queue.
The implementation uses an adjacency list representation of graphs.
STL‘s list container stores lists of adjacent nodes and the queue of nodes needed for BFS traversal.