bfs_graph.c

// C# program to print BFS traversal 
// from a given source vertex. 
// BFS(int s) traverses vertices 
// reachable from s. 
using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

// This class represents a directed 
// graph using adjacency list 
// representation 
class Graph{ 
	
// No. of vertices	 
private int _V; 

//Adjacency Lists 
LinkedList<int>[] _adj; 

public Graph(int V) 
{ 
	_adj = new LinkedList<int>[V]; 
	for(int i = 0; i < _adj.Length; i++) 
	{ 
		_adj[i] = new LinkedList<int>(); 
	} 
	_V = V; 
} 

// Function to add an edge into the graph 
public void AddEdge(int v, int w) 
{		 
	_adj[v].AddLast(w); 

} 

// Prints BFS traversal from a given source s 
public void BFS(int s) 
{ 
	
	// Mark all the vertices as not 
	// visited(By default set as false) 
	bool[] visited = new bool[_V]; 
	for(int i = 0; i < _V; i++) 
		visited[i] = false; 
	
	// Create a queue for BFS 
	LinkedList<int> queue = new LinkedList<int>(); 
	
	// Mark the current node as 
	// visited and enqueue it 
	visited[s] = true; 
	queue.AddLast(s);		 

	while(queue.Any()) 
	{ 
		
		// Dequeue a vertex from queue 
		// and print it 
		s = queue.First(); 
		Console.Write(s + " " ); 
		queue.RemoveFirst(); 
		
		// Get all adjacent vertices of the 
		// dequeued vertex s. If a adjacent 
		// has not been visited, then mark it 
		// visited and enqueue it 
		LinkedList<int> list = _adj[s]; 

		foreach (var val in list)			 
		{ 
			if (!visited[val]) 
			{ 
				visited[val] = true; 
				queue.AddLast(val); 
			} 
		} 
	} 
} 

// Driver code 
static void Main(string[] args) 
{ 
	Graph g = new Graph(4); 
	
	g.AddEdge(0, 1); 
	g.AddEdge(0, 2); 
	g.AddEdge(1, 2); 
	g.AddEdge(2, 0); 
	g.AddEdge(2, 3); 
	g.AddEdge(3, 3); 
	
	Console.Write("Following is Breadth First " + 
				"Traversal(starting from " + 
				"vertex 2)\n"); 
	g.BFS(2); 
} 
} 

// This code is contibuted by anv89