Simple Graph implementation
The idea is to implement a graph with a adjacency list and traverse the same inDFS
using System;
using System.Collections.Generic;
public 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>[] childnodes)
{
this.childnodes=childnodes;
}
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)
{
int vari=childnodes[u].IndexOf(v);
if(vari==-1)
return false;
else
return true;
}
public IList<int> getSuccessors(int v)
{
return childnodes[v];
}
}
class GraphComponenets
{
static Graph graph=new Graph(new List<int>[]{
new List<int>() {4,5},
new List<int>() {1,2,6},
new List<int>() {1,6},
new List<int>() {6},
new List<int>() {0},
new List<int>() {0},
new List<int>() {1,2,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()
{
Console.WriteLine("Connected graph componentes");
for(int v=0;v<graph.Size;v++)
{
if(!visited[v])
{
TraverseDFS(v);
Console.WriteLine();
}
}
}
}
Comments
Post a Comment