Search⌘ K

Solution Review: Implement Depth First Search

Explore how to implement depth first search in C# using a stack to traverse graphs effectively. Understand the traversal process, from marking nodes as visited to pushing adjacent nodes onto the stack, and learn about its time complexity. This lesson helps you grasp the practical application of DFS algorithms essential for coding interviews.

We'll cover the following...

Solution: Using Stacks #

C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Remoting.Messaging;
using System.Text;
using System.Threading.Tasks;
namespace chapter_5
{
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;
}
}
}

The approach is very similar to that of the BFS solution. ...