// 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;

// This class represents a directed graph using adjacency list representation

public 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);

                }

            }

        }

    }

    // A function used by DFS

         void DFSUtil(int v, bool[] visited)

        {

            // Mark the current node as visited

            // and print it

            visited[v] = true;

            Console.Write(v + " ");

​

            // Recur for all the vertices

            // adjacent to this vertex

            LinkedList<int> vList = _adj[v];

            foreach(var n in vList)

            {

                if (!visited[n])

                    DFSUtil(n, visited);

            }

        }

​

        // The function to do DFS traversal.

        // It uses recursive DFSUtil()

        public void DFS(int v)

        {

            // Mark all the vertices as not visited

            // (set as false by default in c#)

            bool[] visited = new bool[_V];

​

            // Call the recursive helper function

            // to print DFS traversal

            DFSUtil(v, visited);

        }

         // A recursive function that uses visited[]

    // and parent to detect cycle in subgraph

    // reachable from vertex v.

    Boolean isCyclicUtil(int v, Boolean[] visited,

                         int parent)

    {

        // Mark the current node as visited

        visited[v] = true;

        // Recur for all the vertices

        // adjacent to this vertex

        foreach(int i in _adj[v])

        {

            // If an adjacent is not visited,

            // then recur for that adjacent

            if (!visited[i]) {

                if (isCyclicUtil(i, visited, v))

                    return true;

            }

            // If an adjacent is visited and

            // not parent of current vertex,

            // then there is a cycle.

            else if (i != parent)

                return true;

        }

        return false;

    }

    // Returns true if the graph contains

    // a cycle, else false.

    Boolean isCyclic()

    {

        // Mark all the vertices as not visited

        // and not part of recursion stack

        Boolean[] visited = new Boolean[_V];

        for (int i = 0; i < _V; i++)

            visited[i] = false;

        // Call the recursive helper function

        // to detect cycle in different DFS trees

        for (int u = 0; u < _V; u++)

            // Don't recur for u if already visited

            if (!visited[u])

                if (isCyclicUtil(u, visited, -1))

                    return true;

        return false;

    }

    // 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);

        Console.WriteLine();

        Console.WriteLine(

            "Following is Depth First Traversal "

            + "(starting from vertex 2)");

        // Function call

        g.DFS(2);

         Graph g2 = new Graph(3);

        g2.AddEdge(0, 1);

        g2.AddEdge(1, 2);

        if (g2.isCyclic())

            Console.WriteLine("Graph contains cycle");

        else

            Console.WriteLine(

                "Graph doesn't contain cycle");

    }

}

​

/**

The breadth-first search (BFS) algorithm is used to search a tree or graph data structure for a node that meets a set of criteria. 

It starts at the tree’s root or graph and searches/visits all nodes at the current depth level before moving on to the nodes at the next depth level. 

Breadth-first search can be used to solve many problems in graph theory.

​

Breadth-First Traversal (or Search) for a graph is similar to the Breadth-First Traversal of a tree (See method 2 of this post). 

​

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:

​

Visited and

Not visited.

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:

Pseudocode:

Breadth_First_Search( Graph, X ) // Here, Graph is the graph that we already have and X is the source node

​

Let Q be the queue

Q.enqueue( X ) // Inserting source node X into the queue

Mark X node as visited.

​

While ( Q is not empty )

Y = Q.dequeue( ) // Removing the front node from the queue

​

Process all the neighbors of Y, For all the neighbors Z of Y

If Z is not visited, Q. enqueue( Z ) // Stores Z in Q

Mark Z as visited

​

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.

**/

​

/**

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. 

The only catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice). 

To avoid processing a node more than once, use a boolean visited array. A graph can have more than one DFS traversal.

​

Depth-first search is an algorithm for traversing or searching tree or graph data structures. 

The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) 

and explores as far as possible along each branch before backtracking. 

So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent 

unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. 

Finally, print the nodes in the path.

​

Follow the below steps to solve the problem:

​

Create a recursive function that takes the index of the node and a visited array.

Mark the current node as visited and print the node.

Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.

**/