Implement Depth First Search (DFS) | C# Online Compiler

Implement Depth First Search (DFS) by Etim Essang

using System;
using System.Collections.Generic;
					
public class Program
{
	    public static void Main(string[] args)
        {
            Graph g = new Graph(7);
            g.addEdge(1, 2);
            g.addEdge(1, 3);
            g.addEdge(2, 4);
            g.addEdge(2, 5);

            Console.WriteLine (dfsTraversal(g));
           
        }
	
	    public static void dfs_helper(Graph g, int source, bool [] visited, ref string result)
        {
            if (g.getVertices() < 1)
            {
                return;
            }

            //Create Stack(Implemented in previous chapters) for Depth First Traversal and Push source in it
            Stack<int> stack = new Stack<int> { };

            stack.Push(source);
            visited[source] = true;
            int current_node;
            LinkedList.Node temp;
            //Traverse while stack is not empty
            while (stack.Count != 0)
            {

                //Pop a vertex/node from stack and add it to the result
                current_node = stack.Pop();
                result += current_node.ToString() ;

                //Get adjacent vertices to the current_node from the array,
                //and if they are not already visited then push them in the stack
                temp = (g.getArray())[current_node].GetHead();

                while (temp != null)
                {

                    if (!visited[temp.data])
                    {
                        stack.Push(temp.data);
                        //Visit the node
                        visited[temp.data] = true;
                    }
                    temp = temp.nextElement;
                }
            } //end of while

        }
        public static string dfsTraversal(Graph g)
        {
            string result = "";

            //Bool Array to hold the history of visited nodes
            //Make a node visited whenever you push it into stack
            bool [] visited = new bool[g.getVertices()];
            for (int i = 0; i < g.getVertices(); i++)
            {
                visited[i] = false;
            }
            for (int i = 0; i < g.getVertices(); i++)
            {
                if (!visited[i])
                    dfs_helper(g, i, visited, ref result);
            }

            //delete[] visited;
            visited = null;

            return result;
        }
	
	public class Graph
    {
        int vertices;
        LinkedList [] array;

      
       public Graph(int v)
       {
            array = new LinkedList[v];
            vertices = v;
            for(int i = 0; i < v; i++)
            {
                array[i] = new LinkedList();
            }
        }

        public void addEdge(int source, int destination)
        {
            if (source < vertices && destination < vertices)
                array[source].InsertAtHead(destination);
        }

        public void printGraph()
        {
            Console.WriteLine("Adjacency List of Directed Graph");
            LinkedList.Node temp;
            for (int i = 0; i < vertices; i++)
            {
                Console.Write( "|" + i + "| => ");
                temp = (array[i]).GetHead();

                while (temp != null)
                {
                    Console.Write("[" + temp.data + "] -> ");
                    temp = temp.nextElement;
                }
                Console.WriteLine("NULL");
            }
        }

        public LinkedList [] getArray()
        {
            return array;
        }

        public int getVertices()
        {
            return vertices;
        }
    }
	
	    public class LinkedList
    {
        public class Node
        {
            internal int data; //Data to store (could be int,string,object etc)
            internal Node nextElement; //Pointer to next element

            public Node()
            {
                //Constructor to initialize nextElement of newlyCreated Node
                nextElement = null;
            }
        };
        Node head;

        public LinkedList()
        {
            head = null;
        }
        public Node GetHead()
        {
            return head;
        }
        bool IsEmpty()
        {
            if (head == null) //Check whether the head points to null
                return true;
            else
                return false;
        }
        public bool PrintList()
        {
            if (IsEmpty())
            {
                Console.Write("List is Empty!");
                return false;
            }
            Node temp = head;
            Console.Write("List : ");

            while (temp != null)
            {
                Console.Write(temp.data + "->");
                temp = temp.nextElement;
            }
            Console.WriteLine("null ");
            return true;
        }
        public void InsertAtHead(int value)
        {
            Node newNode = new Node();
            newNode.data = value;
            newNode.nextElement = head; //Linking newNode to head's nextNode
            head = newNode;

        }
        public string Elements()
        { // this function will return all values of linked List
            string elementsList = "";
            Node start = head;
            Node check = head;

            elementsList += start.data.ToString();
            elementsList += "->";
            start = start.nextElement;

            while (start != null && start.data != check.data)
            {
                elementsList += start.data.ToString();
                elementsList += "->";
                start = start.nextElement;
            }

            if (start == null)
                return elementsList + "null";

            elementsList += check.data.ToString();
            return elementsList;
        }
        public void InsertAtTail(int value)
        {
            if (IsEmpty())
            { // inserting first element in list
                InsertAtHead(value); // head will point to first element of the list      
            }
            else
            {
                Node newNode = new Node(); // creating new node
                Node last = head; // last pointing at the head of the list

                while (last.nextElement != null)
                { // traversing through the list
                    last = last.nextElement;
                }

                newNode.data = value;
                Console.Write(value + " Inserted!    ");
                newNode.nextElement = null; // point last's nextElement to nullptr
                last.nextElement = newNode; // adding the newNode at the end of the list
            }
        }
  
        // function to check if element exists in the list
        public bool Search(int value)
        {
            Node temp = head; // pointing temp to the head

            while (temp != null)
            {
                if (temp.data == value)
                { // if passed value matches with temp's data
                    return true;
                }
                temp = temp.nextElement; // pointig to temp's nextElement
            }
            return false; // if not found
        }
        
        public bool Delete(int value)
        {
            bool deleted = false; //returns true if the node is deleted, false otherwise

            if (IsEmpty())
            { //check if the list is empty
                Console.WriteLine("List is Empty");
                return deleted; //deleted will be false
            }

            //if list is not empty, start traversing it from the head
            Node currentNode = head; //currentNode to traverse the list
            Node previousNode = null; //previousNode starts from null

            if (currentNode.data == value)
            { // deleting value of head
                deleted = DeleteAtHead();
                Console.WriteLine(value + " deleted!");
                deleted = true; // true because value found and deleted
                return deleted; //returns true if the node is deleted
            }
            previousNode = currentNode;
            currentNode = currentNode.nextElement; // pointing current to current's nextElement
                                                   //Traversing/Searching for Node to Delete
            while (currentNode != null)
            {

                //Node to delete is found
                if (value == currentNode.data)
                {
                    // pointing previousNode's nextElement to currentNode's nextElement
                    previousNode.nextElement = currentNode.nextElement;
                    // delete currentNode;
                    currentNode = previousNode.nextElement;
                    deleted = true;
                    break;
                }
                previousNode = currentNode;
                currentNode = currentNode.nextElement; // pointing current to current's nextElement
            }
            //deleted is true only when value is found and deleted
            if (deleted == false)
            {
                Console.WriteLine(value + " does not exist!");
            }
            else
            {
                Console.WriteLine(value + " deleted!");
            }
            return deleted;
        } //end of delete()
        bool DeleteAtHead()
        {
            if (IsEmpty())
            { // check if list is empty
                Console.WriteLine("List is Empty");
                return false;
            }
           
            head = head.nextElement; //nextNode points to head's nextElement

            
            return true;
        }
 
        public int Length()
        {
            Node current = head; // Start from the first element
            int count = 0; // in start count is 0

            while (current != null)
            { // Traverse the list and count the number of nodes
                count++; // increment everytime as element is found
                current = current.nextElement; // pointing to current's nextElement
            }
            return count;
        }
      

        public string Reverse()
        {
            Node previous = null; //To keep track of the previous element, will be used in swapping links
            Node current = head; //firstElement
            Node next = null;

            //While Traversing the list, swap links
            while (current != null)
            {
                next = current.nextElement;
                current.nextElement = previous;
                previous = current;
                current = next;
            }

            head = previous; // pointing head to start of the list
            return Elements(); // calling elements to return a string of values in list
        }
      
        public bool DetectLoop()
        {
            Node slow = head, fast = head; //starting from head of the list

            while ((slow != null) && (fast != null) && (fast.nextElement != null)) //checking if all elements exist 
            {
                slow = slow.nextElement;
                fast = fast.nextElement.nextElement;

                /* If slow and fast meet at some point then there
                    is a loop */
                if (slow == fast)
                {
                    // Return 1 to indicate that loop is found */
                    return true;
                }
            }
            // Return 0 to indeciate that ther is no loop*/
            return false;
        }
        public void InsertLoop()
        {
            Node temp = head;
            // traversing to get to last element of the list
            while (temp.nextElement != null)
            {
                temp = temp.nextElement;
            }
            temp.nextElement = head; // pointing last element to head of the list
        }
      
        public int FindMid()
        {
            //list is empty
            if (IsEmpty())
                return 0;

            //currentNode starts at the head
            Node currentNode = head;

            if (currentNode.nextElement == null)
            {
                //Only 1 element exist in array so return its value.
                return currentNode.data;
            }

            Node midNode = currentNode; //midNode starts at head
            currentNode = currentNode.nextElement.nextElement; //currentNode moves two steps forward

            //Move midNode (Slower) one step at a time
            //Move currentNode (Faster) two steps at a time
            //When currentNode reaches at end, midNode will be at the middle of List
            while (currentNode != null)
            {       // traversing from head to end

                midNode = midNode.nextElement;

                currentNode = currentNode.nextElement;     // pointing to current's next
                if (currentNode != null)
                    currentNode = currentNode.nextElement;     // pointing to current's next

            }
            if (midNode != null)     // pointing at middle of the list
                return midNode.data;
            return 0;
        }
       
        public string RemoveDuplicates()
        {
            Node start, startNext = null;
            start = head;

            /* Pick elements one by one */
            while ((start != null) && (start.nextElement != null))
            {
                startNext = start;

                /* Compare the picked element with rest 
                   of the elements */
                while (startNext.nextElement != null)
                {
                    /* If duplicate then delete it */
                    if (start.data == startNext.nextElement.data)
                    {

                        // skipping elements from the list to be deleted
                        startNext.nextElement = startNext.nextElement.nextElement;

                    }
                    else
                        startNext = startNext.nextElement; // pointing to next of startNext
                }
                start = start.nextElement;
            }
            return Elements();

        }

      
        public string Union(LinkedList list1, LinkedList list2)
        {
            //Return other List if one of them is empty
            if (list1.IsEmpty())
                return list2.Elements();
            else if (list2.IsEmpty())
                return list1.Elements();

            Node start = list1.head; // starting from head of list 1

            //Traverse first list till the last element
            while (start.nextElement != null)
            {
                start = start.nextElement;
            }

            //Link last element of first list to the first element of second list
            start.nextElement = list2.head; // appendinf list2 with list 1
            return list1.RemoveDuplicates(); // removing duplicates from list and return list
        }

        //To Find nth node from end of list
        public int FindNth(int n)
        {

            if (IsEmpty()) // if list is empty return -1
                return -1;

            int length = 0;
            Node currentNode = head; // pointing to head of the list

            // finding the length of the list
            while (currentNode != null)
            {
                currentNode = currentNode.nextElement;
                length++;
            }

            //Find the Node which is at (len - n) position from start
            currentNode = head;
            int position = length - n;

            if (position < 0 || position > length) // check if out of the range of the list
                return -1;

            int count = 0;
            // traversing till the nth Element of the list
            while (count != position)
            { // finding the position of the element
                currentNode = currentNode.nextElement;
                count++;
            }

            if (currentNode != null) // if node exists
                return currentNode.data;

            return -1;

        }
    }
}

​x
 
using System;
using System.Collections.Generic;
                    
public class Program
{
        public static void Main(string[] args)
        {
            Graph g = new Graph(7);
            g.addEdge(1, 2);
            g.addEdge(1, 3);
            g.addEdge(2, 4);
            g.addEdge(2, 5);
​
            Console.WriteLine (dfsTraversal(g));
           
        }
    
        public static void dfs_helper(Graph g, int source, bool [] visited, ref string result)
        {
            if (g.getVertices() < 1)
            {
                return;
            }
​
            //Create Stack(Implemented in previous chapters) for Depth First Traversal and Push source in it
            Stack<int> stack = new Stack<int> { };
​
            stack.Push(source);
            visited[source] = true;
            int current_node;
            LinkedList.Node temp;
            //Traverse while stack is not empty
            while (stack.Count != 0)
            {
​
                //Pop a vertex/node from stack and add it to the result
                current_node = stack.Pop();
                result += current_node.ToString() ;
​
                //Get adjacent vertices to the current_node from the array,
                //and if they are not already visited then push them in the stack
                temp = (g.getArray())[current_node].GetHead();
​
                while (temp != null)
                {
​
                    if (!visited[temp.data])
                    {
                        stack.Push(temp.data);
                        //Visit the node
                        visited[temp.data] = true;
                    }
                    temp = temp.nextElement;
                }
            } //end of while
​
        }
        public static string dfsTraversal(Graph g)
        {
            string result = "";
​
            //Bool Array to hold the history of visited nodes
            //Make a node visited whenever you push it into stack
            bool [] visited = new bool[g.getVertices()];
            for (int i = 0; i < g.getVertices(); i++)
            {
                visited[i] = false;
            }
            for (int i = 0; i < g.getVertices(); i++)
            {
                if (!visited[i])
                    dfs_helper(g, i, visited, ref result);
            }
​
            //delete[] visited;
            visited = null;
​
            return result;
        }
    
    public class Graph
    {
        int vertices;
        LinkedList [] array;
​
      
       public Graph(int v)
       {
            array = new LinkedList[v];
            vertices = v;
            for(int i = 0; i < v; i++)
            {
                array[i] = new LinkedList();
            }
        }
​
        public void addEdge(int source, int destination)
        {
            if (source < vertices && destination < vertices)
                array[source].InsertAtHead(destination);
        }
​
        public void printGraph()
        {
            Console.WriteLine("Adjacency List of Directed Graph");
            LinkedList.Node temp;
            for (int i = 0; i < vertices; i++)
            {
                Console.Write( "|" + i + "| => ");
                temp = (array[i]).GetHead();
​
                while (temp != null)
                {
                    Console.Write("[" + temp.data + "] -> ");
                    temp = temp.nextElement;
                }
                Console.WriteLine("NULL");
            }
        }
​
        public LinkedList [] getArray()
        {
            return array;
        }
​
        public int getVertices()
        {
            return vertices;
        }
    }
    
        public class LinkedList
    {
        public class Node
        {
            internal int data; //Data to store (could be int,string,object etc)
            internal Node nextElement; //Pointer to next element
​
            public Node()
            {
                //Constructor to initialize nextElement of newlyCreated Node
                nextElement = null;
            }
        };
        Node head;
​
        public LinkedList()
        {
            head = null;
        }
        public Node GetHead()
        {
            return head;
        }
        bool IsEmpty()
        {
            if (head == null) //Check whether the head points to null
                return true;
            else
                return false;
        }
        public bool PrintList()
        {
            if (IsEmpty())
            {
                Console.Write("List is Empty!");
                return false;
            }
            Node temp = head;
            Console.Write("List : ");
​
            while (temp != null)
            {
                Console.Write(temp.data + "->");
                temp = temp.nextElement;
            }
            Console.WriteLine("null ");
            return true;
        }
        public void InsertAtHead(int value)
        {
            Node newNode = new Node();
            newNode.data = value;
            newNode.nextElement = head; //Linking newNode to head's nextNode
            head = newNode;
​
        }
        public string Elements()
        { // this function will return all values of linked List
            string elementsList = "";
            Node start = head;
            Node check = head;
​
            elementsList += start.data.ToString();
            elementsList += "->";
            start = start.nextElement;
​
            while (start != null && start.data != check.data)
            {
                elementsList += start.data.ToString();
                elementsList += "->";
                start = start.nextElement;
            }
​
            if (start == null)
                return elementsList + "null";
​
            elementsList += check.data.ToString();
            return elementsList;
        }
        public void InsertAtTail(int value)
        {
            if (IsEmpty())
            { // inserting first element in list
                InsertAtHead(value); // head will point to first element of the list      
            }
            else
            {
                Node newNode = new Node(); // creating new node
                Node last = head; // last pointing at the head of the list
​
                while (last.nextElement != null)
                { // traversing through the list
                    last = last.nextElement;
                }
​
                newNode.data = value;
                Console.Write(value + " Inserted!    ");
                newNode.nextElement = null; // point last's nextElement to nullptr
                last.nextElement = newNode; // adding the newNode at the end of the list
            }
        }
  
        // function to check if element exists in the list
        public bool Search(int value)
        {
            Node temp = head; // pointing temp to the head
​
            while (temp != null)
            {
                if (temp.data == value)
                { // if passed value matches with temp's data
                    return true;
                }
                temp = temp.nextElement; // pointig to temp's nextElement
            }
            return false; // if not found
        }
        
        public bool Delete(int value)
        {
            bool deleted = false; //returns true if the node is deleted, false otherwise
​
            if (IsEmpty())
            { //check if the list is empty
                Console.WriteLine("List is Empty");
                return deleted; //deleted will be false
            }
​
            //if list is not empty, start traversing it from the head
            Node currentNode = head; //currentNode to traverse the list
            Node previousNode = null; //previousNode starts from null
​
            if (currentNode.data == value)
            { // deleting value of head
                deleted = DeleteAtHead();
                Console.WriteLine(value + " deleted!");
                deleted = true; // true because value found and deleted
                return deleted; //returns true if the node is deleted
            }
            previousNode = currentNode;
            currentNode = currentNode.nextElement; // pointing current to current's nextElement
                                                   //Traversing/Searching for Node to Delete
            while (currentNode != null)
            {
​
                //Node to delete is found
                if (value == currentNode.data)
                {
                    // pointing previousNode's nextElement to currentNode's nextElement
                    previousNode.nextElement = currentNode.nextElement;
                    // delete currentNode;
                    currentNode = previousNode.nextElement;
                    deleted = true;
                    break;
                }
                previousNode = currentNode;
                currentNode = currentNode.nextElement; // pointing current to current's nextElement
            }
            //deleted is true only when value is found and deleted
            if (deleted == false)
            {
                Console.WriteLine(value + " does not exist!");
            }
            else
            {
                Console.WriteLine(value + " deleted!");
            }
            return deleted;
        } //end of delete()
        bool DeleteAtHead()
        {
            if (IsEmpty())
            { // check if list is empty
                Console.WriteLine("List is Empty");
                return false;
            }
           
            head = head.nextElement; //nextNode points to head's nextElement
​
            
            return true;
        }
 
        public int Length()
        {
            Node current = head; // Start from the first element
            int count = 0; // in start count is 0
​
            while (current != null)
            { // Traverse the list and count the number of nodes
                count++; // increment everytime as element is found
                current = current.nextElement; // pointing to current's nextElement
            }
            return count;
        }
      
​
        public string Reverse()
        {
            Node previous = null; //To keep track of the previous element, will be used in swapping links
            Node current = head; //firstElement
            Node next = null;
​
            //While Traversing the list, swap links
            while (current != null)
            {
                next = current.nextElement;
                current.nextElement = previous;
                previous = current;
                current = next;
            }
​
            head = previous; // pointing head to start of the list
            return Elements(); // calling elements to return a string of values in list
        }
      
        public bool DetectLoop()
        {
            Node slow = head, fast = head; //starting from head of the list
​
            while ((slow != null) && (fast != null) && (fast.nextElement != null)) //checking if all elements exist 
            {
                slow = slow.nextElement;
                fast = fast.nextElement.nextElement;
​
                /* If slow and fast meet at some point then there
                    is a loop */
                if (slow == fast)
                {
                    // Return 1 to indicate that loop is found */
                    return true;
                }
            }
            // Return 0 to indeciate that ther is no loop*/
            return false;
        }
        public void InsertLoop()
        {
            Node temp = head;
            // traversing to get to last element of the list
            while (temp.nextElement != null)
            {
                temp = temp.nextElement;
            }
            temp.nextElement = head; // pointing last element to head of the list
        }
      
        public int FindMid()
        {
            //list is empty
            if (IsEmpty())
                return 0;
​
            //currentNode starts at the head
            Node currentNode = head;
​
            if (currentNode.nextElement == null)
            {
                //Only 1 element exist in array so return its value.
                return currentNode.data;
            }
​
            Node midNode = currentNode; //midNode starts at head
            currentNode = currentNode.nextElement.nextElement; //currentNode moves two steps forward
​
            //Move midNode (Slower) one step at a time
            //Move currentNode (Faster) two steps at a time
            //When currentNode reaches at end, midNode will be at the middle of List
            while (currentNode != null)
            {       // traversing from head to end
​
                midNode = midNode.nextElement;
​
                currentNode = currentNode.nextElement;     // pointing to current's next
                if (currentNode != null)
                    currentNode = currentNode.nextElement;     // pointing to current's next
​
            }
            if (midNode != null)     // pointing at middle of the list
                return midNode.data;
            return 0;
        }
       
        public string RemoveDuplicates()
        {
            Node start, startNext = null;
            start = head;
​
            /* Pick elements one by one */
            while ((start != null) && (start.nextElement != null))
            {
                startNext = start;
​
                /* Compare the picked element with rest 
                   of the elements */
                while (startNext.nextElement != null)
                {
                    /* If duplicate then delete it */
                    if (start.data == startNext.nextElement.data)
                    {
​
                        // skipping elements from the list to be deleted
                        startNext.nextElement = startNext.nextElement.nextElement;
​
                    }
                    else
                        startNext = startNext.nextElement; // pointing to next of startNext
                }
                start = start.nextElement;
            }
            return Elements();
​
        }
​
      
        public string Union(LinkedList list1, LinkedList list2)
        {
            //Return other List if one of them is empty
            if (list1.IsEmpty())
                return list2.Elements();
            else if (list2.IsEmpty())
                return list1.Elements();
​
            Node start = list1.head; // starting from head of list 1
​
            //Traverse first list till the last element
            while (start.nextElement != null)
            {
                start = start.nextElement;
            }
​
            //Link last element of first list to the first element of second list
            start.nextElement = list2.head; // appendinf list2 with list 1
            return list1.RemoveDuplicates(); // removing duplicates from list and return list
        }
​
        //To Find nth node from end of list
        public int FindNth(int n)
        {
​
            if (IsEmpty()) // if list is empty return -1
                return -1;
​
            int length = 0;
            Node currentNode = head; // pointing to head of the list
​
            // finding the length of the list
            while (currentNode != null)
            {
                currentNode = currentNode.nextElement;
                length++;
            }
​
            //Find the Node which is at (len - n) position from start
            currentNode = head;
            int position = length - n;
​
            if (position < 0 || position > length) // check if out of the range of the list
                return -1;
​
            int count = 0;
            // traversing till the nth Element of the list
            while (count != position)
            { // finding the position of the element
                currentNode = currentNode.nextElement;
                count++;
            }
​
            if (currentNode != null) // if node exists
                return currentNode.data;
​
            return -1;
​
        }
    }
}

View IL Code