Breadth First Search in C#
I have a code BFS in C++, and i write again by C#, that code:
C++:
Code:
#include <iostream>#include <queue>
using namespace std;
const int maxx = 20;
void Read_input_from_user(bool grid[][maxx], int vertices)
{
int u, v;
for(int x = 0; x < vertices; ++x)
{
cout << "Enter u : \t";
cin >> u;
u--;
cout << "Enter v : \t";
cin >> v;
v--;
grid[u][v] = true;
grid[v][u] = true;
cout << "---------------------\n";
}
}
void Breadth_first_search(queue<int> &Q, vector<int> &trace,
bool grid[][maxx], int start, int nodes)
{
int u;
vector<int> visited(maxx,0);
Q.push(start);
trace[start] = -1;
visited[start] = 1;
do{
u = Q.front();
Q.pop();
for(int v = 0; v < nodes; ++v)
{
if((grid[u][v] == true) && visited[v] == 0)
{
Q.push(v);
trace[v] = u;
visited[v] = 1;
}
}
}while(!Q.empty());
}
void Trace_result(vector<int> &trace, int start, int end, int nodes)
{
cout << "From _nodes" << start + 1 << " you can visit :\n";
for(int v = 0; v < nodes; ++v)
{
if(trace[v] != 0)
{
cout << " _nodes : " << v + 1 << " , ";
}
}
cout << "\n--------------------------------------------\n";
cout << "The path from " << start + 1 << " to " << end + 1 << '\n';
if(trace[end] == 0){
cout << "Unavailable.! to go to from " << end + 1
<< " to -> " << start + 1 << '\n';
}
else{
while(end != start)
{
cout << end + 1 << "<-";
end = trace[end];
}
cout << start + 1 << endl;
}
}
int main()
{
//Initialization
vector<int> trace(maxx, 0);
queue<int> Q;
bool grid[maxx][maxx] = {false};
int nodes, vertices;
cout << "Please input the number of Node : \n";
cin >> nodes;
cout << "Please input the number of Vertices : \n";
cin >> vertices;
//Set value for all vertices.
Read_input_from_user(grid, vertices);
//Read the necessary path
int starting_position, finishing_position;
cout << "Please Input the Starting Node : \n";
cin >> starting_position;
cout << "Please Input the Finishing Node : \n";
cin >> finishing_position;
//Decrease to fit with index of C++ start from 0->size-1
starting_position--;
finishing_position--;
//Algorithm starts
Breadth_first_search(Q, trace, grid, starting_position, nodes);
Trace_result(trace, starting_position, finishing_position, nodes);
system("pause");
return 0;
}
Anh my C# code:
Code:
using System;using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
private const int maxx = 20;
static void Read_input_from_user(bool[,] grid, int vertices)
{
int u;
int v;
for (int x = 0; x < vertices; ++x)
{
Console.Write("Enter u : \t");
u = Convert.ToInt32(Console.ReadLine());
u--;
Console.Write("Enter v : \t");
v = Convert.ToInt32(Console.ReadLine());
v--;
grid[u, v] = true;
grid[v, u] = true;
Console.Write("---------------------\n");
}
}
static void Breadth_first_search( Queue<int> Q, List<int> trace, bool[,] grid, int start, int nodes)
{
int u;
List<int> visited = new List<int>(maxx);
Q.Enqueue(start);
trace[start] = -1;
visited[start] = 1;
do
{
u = Q.Peek();
Q.Dequeue();
for (int v = 0; v < nodes; ++v)
{
if ((grid[u, v] == true) && visited[v] == 0)
{
Q.Enqueue(v);
trace[v] = u;
visited[v] = 1;
}
}
} while (Q.Count != 0);
}
static void Trace_result( List<int> trace, int start, int end, int nodes)
{
Console.Write("From _nodes");
Console.Write(start + 1);
Console.Write(" you can visit :\n");
for (int v = 0; v < nodes; ++v)
{
if (trace[v] != 0)
{
Console.Write(" _nodes : ");
Console.Write(v + 1);
Console.Write(" , ");
}
}
Console.Write("\n--------------------------------------------\n");
Console.Write("The path from ");
Console.Write(start + 1);
Console.Write(" to ");
Console.Write(end + 1);
Console.Write('\n');
if (trace[end] == 0)
{
Console.Write("Unavailable.! to go to from ");
Console.Write(end + 1);
Console.Write(" to -> ");
Console.Write(start + 1);
Console.Write('\n');
}
else
{
while (end != start)
{
Console.Write(end + 1);
Console.Write("<-");
end = trace[end];
}
Console.Write(start + 1);
Console.Write("\n");
}
}
static int Main()
{
//Initialization
List<int> trace = new List<int>(maxx);
Queue<int> Q = new Queue<int>();
bool[,] grid = new bool[maxx, maxx];
int nodes;
int vertices;
Console.Write("Please input the number of Node : \n");
//cin >> nodes;
nodes = Convert.ToInt32(Console.ReadLine());
Console.Write("Please input the number of Vertices : \n");
//cin >> vertices;
vertices = Convert.ToInt32(Console.ReadLine());
//Set value for all vertices.
Read_input_from_user(grid, vertices);
//Read the necessary path
int starting_position;
int finishing_position;
Console.Write("Please Input the Starting Node : \n");
//cin >> starting_position;
starting_position = Convert.ToInt32(Console.ReadLine());
Console.Write("Please Input the Finishing Node : \n");
//cin >> finishing_position;
finishing_position = Convert.ToInt32(Console.ReadLine());
//Decrease to fit with index of C++ start from 0->size-1
starting_position--;
finishing_position--;
//Algorithm starts
Breadth_first_search( Q, trace, grid, starting_position, nodes);
Trace_result( trace, starting_position, finishing_position, nodes);
Console.ReadLine();
return 0;
}
}
}
So, I'm F5 to build. When i put the node start and node finish, it not work, someone test it in your VS and tell me, what i wrong?
