Graph Breadth First Search
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Graph
{
class BFS
{
private List<int>[] graph_childnodes;
public BFS(int size)
{
this.graph_childnodes = new List<int>[size];
for(int i=1;i<=size;i++)
{
graph_childnodes[i] = new List<int>();
}
}
public BFS(List<int>[] childNode)
{
graph_childnodes = childNode;
}
public int Size
{
get { return this.graph_childnodes.Length; }
}
public void AddEdge(int u,int v)
{
graph_childnodes[u].Add(v);
}
public void RemoveEdge(int u, int v)
{
graph_childnodes[u].Remove(v);
}
public bool HasEdge(int u, int v)
{
bool hasEdge = graph_childnodes[u].Contains(v);
return hasEdge;
}
public IList<int> GetSuccessors(int u)
{
return graph_childnodes[u];
}
}
class graphComponent
{
static BFS graph = new BFS(new List<int>[]{
new List<int>{1,2,3},
new List<int>{0,4,5},
new List<int>{0,5},
new List<int>{0},
new List<int>{1},
new List<int>{1,2}
});
static bool[] visited = new bool[graph.Size+1];
static Queue<int> queue = new Queue<int>();
static void TraverseBFS(int v)
{
queue.Enqueue(v);
Console.WriteLine(v + " ");
visited[v] = true;
while (queue.Count() != 0)
{
int node=queue.Dequeue();
foreach (int child in graph.GetSuccessors(node))
{
if (!visited[child])
{
visited[child] = true;
Console.WriteLine(child + " ");
queue.Enqueue(child);
}
}
}
}
static void Main(string[] args)
{
List<char> A = new List<char>();
A.Add('B');
A.Add('C');
A.Add('D');
List<char> B = new List<char>();
B.Add('A');
B.Add('E');
B.Add('F');
List<char>[] graph1 = new List<char>[5];
graph1[0] = A;
graph1[1] = B;
Console.WriteLine("Connected graph components");
for (int v = 0; v < graph.Size; v++)
{
if (!visited[v])
{
TraverseBFS(v);
Console.WriteLine();
}
}
Console.ReadLine();
}
}
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Graph
{
class BFS
{
private List<int>[] graph_childnodes;
public BFS(int size)
{
this.graph_childnodes = new List<int>[size];
for(int i=1;i<=size;i++)
{
graph_childnodes[i] = new List<int>();
}
}
public BFS(List<int>[] childNode)
{
graph_childnodes = childNode;
}
public int Size
{
get { return this.graph_childnodes.Length; }
}
public void AddEdge(int u,int v)
{
graph_childnodes[u].Add(v);
}
public void RemoveEdge(int u, int v)
{
graph_childnodes[u].Remove(v);
}
public bool HasEdge(int u, int v)
{
bool hasEdge = graph_childnodes[u].Contains(v);
return hasEdge;
}
public IList<int> GetSuccessors(int u)
{
return graph_childnodes[u];
}
}
class graphComponent
{
static BFS graph = new BFS(new List<int>[]{
new List<int>{1,2,3},
new List<int>{0,4,5},
new List<int>{0,5},
new List<int>{0},
new List<int>{1},
new List<int>{1,2}
});
static bool[] visited = new bool[graph.Size+1];
static Queue<int> queue = new Queue<int>();
static void TraverseBFS(int v)
{
queue.Enqueue(v);
Console.WriteLine(v + " ");
visited[v] = true;
while (queue.Count() != 0)
{
int node=queue.Dequeue();
foreach (int child in graph.GetSuccessors(node))
{
if (!visited[child])
{
visited[child] = true;
Console.WriteLine(child + " ");
queue.Enqueue(child);
}
}
}
}
static void Main(string[] args)
{
List<char> A = new List<char>();
A.Add('B');
A.Add('C');
A.Add('D');
List<char> B = new List<char>();
B.Add('A');
B.Add('E');
B.Add('F');
List<char>[] graph1 = new List<char>[5];
graph1[0] = A;
graph1[1] = B;
Console.WriteLine("Connected graph components");
for (int v = 0; v < graph.Size; v++)
{
if (!visited[v])
{
TraverseBFS(v);
Console.WriteLine();
}
}
Console.ReadLine();
}
}
}
Comments
Post a Comment