The below code is an implementation of the Depth First Search (DFS) algorithm on a graph using the C# programming language. The DfsGraph class represents a graph and contains several properties and methods to perform the DFS traversal.
class DfsGraph
{
private int V;
private List<int>[] adj;
public DfsGraph(int v)
{
V = v;
adj = new List<int>[v];
for (int i = 0; i < v; i++)
{
adj[i] = new List<int>();
}
}
public void AddEdge(int v,int w)
{
adj[v].Add(w);
}
void DfsUtil(int v, bool[] visited)
{
visited[v] = true;
Console.Write(v + " ");
List<int> vList = adj[v];
foreach (var item in vList)
{
if (!visited[item])
DfsUtil(item, visited);
}
}
public void Dfs(int v)
{
bool[] visted = new bool[V];
DfsUtil(v, visted);
}
}
}
The V property is an integer that represents the number of vertices in the graph. The adj property is an array of lists, where each list represents the adjacency list of a vertex. An adjacency list is a collection of all the vertices that are adjacent to a given vertex. In other words, it contains all the vertices that can be reached from the given vertex by following a single edge.
public DfsGraph(int v)
{
V = v;
adj = new List<int>[v];
for (int i = 0; i < v; i++)
{
adj[i] = new List<int>();
}
}
The DfsGraph(int v) constructor takes an integer v as an argument, which represents the number of vertices in the graph. It initializes the V property with the value of v and creates a new array of lists with size v for the adj property. It then iterates over each element in the adj array and initializes it with a new empty list.
The AddEdge(int v, int w) method takes two integers v and w as arguments, which represent two vertices in the graph. It adds an edge between these two vertices by adding w to the adjacency list of vertex v.
void DfsUtil(int v, bool[] visited)
{
visited[v] = true;
Console.Write(v + " ");
List<int> vList = adj[v];
foreach (var item in vList)
{
if (!visited[item])
DfsUtil(item, visited);
}
}
The DfsUtil(int v, bool[] visited) method is a recursive utility method that performs the DFS traversal starting from vertex v. It takes an integer v and a boolean array visited as arguments. The visited array is used to keep track of which vertices have been visited during the traversal. The method first marks vertex v as visited by setting the corresponding element in the visited array to true. It then prints the value of v to the console using the Console.Write method. Next, it retrieves the adjacency list of vertex v and iterates over each element in the list. For each element, it checks if it has not been visited yet by checking its value in the visited array. If it has not been visited, it calls itself recursively with this element as the new starting vertex.
public void Dfs(int v)
{
bool[] visted = new bool[V];
DfsUtil(v, visted);
}
The Dfs(int v) method performs the DFS traversal starting from vertex v. It takes an integer v as an argument, which represents the starting vertex for the traversal. It first creates a new boolean array with size equal to the number of vertices in the graph to keep track of visited vertices. It then calls the DfsUtil method with vertex v and the visited array as arguments to perform the DFS traversal.
Here’s an example that demonstrates how to use this class to create a graph with 4 vertices and perform a DFS traversal starting from vertex 2:
var graph = new DfsGraph(4);
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 2);
graph.AddEdge(2, 0);
graph.AddEdge(2, 3);
graph.AddEdge(3, 3);
Console.WriteLine("Depth First Traversal starting from vertex 2:");
graph.Dfs(2);
This code creates a new instance of the DfsGraph class with 4 vertices, adds edges between them using the AddEdge method, and performs a DFS traversal starting from vertex 2 using the Dfs& method. The output of this code would be:
Depth First Traversal starting from vertex 2:
2
0
1
3