DepthFirst Traversal of a graph in C#
DepthFirst Traversal of a graph in C#
For understanding graphs in c# Please go through the below tutorial
http://www.introprogramming.info/tag/graph-implementation/#_Toc362296541
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Graph
{
class Graph
{
private List<int>[] childnodes;
public Graph(int size)
{
this.childnodes = new List<int>[size];
for (int i = 0; i < size; i++)
{
this.childnodes[i] = new List<int>();
}
}
public Graph(List<int>[] childnode)
{
this.childnodes = childnode;
}
public int Size
{
get { return this.childnodes.Length;}
}
public void AddEdge(int u, int v)
{
childnodes[u].Add(v);
}
public void RemoveEdge(int u, int v)
{
childnodes[u].Remove(v);
}
public bool HasEdge(int u, int v)
{
bool hasEdge = childnodes[u].Contains(v);
return hasEdge;
}
public IList<int> GetSuccessors(int v)
{
return childnodes[v];
}
}
class Program
{
static Graph graph = new Graph(new List<int>[] {
new List<int>(){2,3},
new List<int>(){4},
new List<int>(){0,3},
new List<int>(){0,2,4},
new List<int>(){1,3}
});
static bool[] visited = new bool[graph.Size];
static void TraverseDFS(int v)
{
if (!visited[v])
{
Console.Write(v + " ");
visited[v] = true;
foreach (int child in graph.GetSuccessors(v))
{
TraverseDFS(child);
}
}
}
static void Main(string[] args)
{
Console.WriteLine("Connected graph components");
for (int v = 0; v < graph.Size; v++)
{
if (!visited[v])
{
TraverseDFS(v);
Console.WriteLine();
}
}
Console.ReadLine();
}
}
}
Comments
Post a Comment