Trang Chính
Box này mình sẽ post những cài đặt đối với những giải thuật cơ bản bằng C++, vì đa số các giải thuật này đều được cài đặt bằng Pascal nên cũng gây không ít khó khăn cho những bạn mới học khi muốn tìm hiểu giải thuật mà không biết Pascal T_T. Mình sẽ demo output luôn cho các bạn tiện theo dõi, nếu có bug thì các bạn cứ thoải mái report vì mình cũng không dám nói mình viết là perfect ~~!
Lưu ý về phần lý thuyết mình sẽ không nêu ra ở đây vì các bạn có thể dễ dàng tìm thấy trên wikipedia.org. Nên mình chỉ để lại 1 link lý thuyết cho những bạn nào muốn tìm hiểu lại thôi.
Mở đầu sẽ là thuật toán tìm kiếm theo chiều rộng trên đồ thị :
Breadth First Search :
Lý thuyết :
Code:
[You must be registered and logged in to see this link.]
Cài đặt bằng ngôn ngữ C++ :
C++ Code:
#include
#include
using std::[You must be registered and logged in to see this link.];
using std::endl;
using std::endl;
using std::[You must be registered and logged in to see this link.];
const int maxx = 20;
void Read_input_from_user(bool grid[][maxx], int vertices)
{
int u, v;
for(int x = 0; x < vertices; ++x)
{
[You must be registered and logged in to see this link.] << "Enter u : \t";
[You must be registered and logged in to see this link.] >> u;
u--;
[You must be registered and logged in to see this link.] << "Enter v : \t";
[You must be registered and logged in to see this link.] >> v;
v--;
grid[u][v] = true;
grid[v][u] = true;
[You must be registered and logged in to see this link.] << "---------------------\n";
}
}
void Breadth_first_search(std::queue<int> &Q, std::vector<int> &trace,
bool grid[][maxx], int start, int nodes)
{
int u;
Q.push(start);
trace[start] = -1;
do{
u = Q.front();
Q.pop();
for(int v = 0; v < nodes; ++v)
{
if((grid[u][v] == true) && trace[v] == 0)
{
Q.push(v);
trace[v] = u;
}
}
}while(!Q.empty());
}
void Trace_result(std::vector<int> &trace, int start, int end, int nodes)
{
[You must be registered and logged in to see this link.] << "From _nodes" << start + 1 << " you can visit :\n";
for(int v = 0; v < nodes; ++v)
{
if(trace[v] != 0)
{
[You must be registered and logged in to see this link.] << " _nodes : " << v + 1 << " , ";
}
}
[You must be registered and logged in to see this link.] << "\n--------------------------------------------\n";
[You must be registered and logged in to see this link.] << "The path from " << start + 1 << " to " << end + 1 << '\n';
if(trace[end] == 0){
[You must be registered and logged in to see this link.] << "Unavailable.! to go to from " << end + 1
<< " to -> " << start + 1 << '\n';
}
else{
while(end != start)
{
[You must be registered and logged in to see this link.] << end + 1 << "<-";
end = trace[end];
}
[You must be registered and logged in to see this link.] << start + 1 << endl;
}
}
int main()
{
//Initialization
std::vector<int> trace(maxx, 0);
std::queue<int> Q;
bool grid[maxx][maxx] = {false};
int nodes, vertices;
[You must be registered and logged in to see this link.] << "Please input the number of Node : \n";
[You must be registered and logged in to see this link.] >> nodes;
[You must be registered and logged in to see this link.] << "Please input the number of Vertices : \n";
[You must be registered and logged in to see this link.] >> vertices;
//Set value for all vertices.
Read_input_from_user(grid, vertices);
//Read the necessary path
int starting_position, finishing_position;
[You must be registered and logged in to see this link.] << "Please Input the Starting Node : \n";
[You must be registered and logged in to see this link.] >> starting_position;
[You must be registered and logged in to see this link.] << "Please Input the Finishing Node : \n";
[You must be registered and logged in to see this link.] >> 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);
return 0;
}
Demo :
Lưu ý về phần lý thuyết mình sẽ không nêu ra ở đây vì các bạn có thể dễ dàng tìm thấy trên wikipedia.org. Nên mình chỉ để lại 1 link lý thuyết cho những bạn nào muốn tìm hiểu lại thôi.
Mở đầu sẽ là thuật toán tìm kiếm theo chiều rộng trên đồ thị :
Breadth First Search :
Lý thuyết :
Code:
[You must be registered and logged in to see this link.]
Cài đặt bằng ngôn ngữ C++ :
C++ Code:
[You must be registered and logged in to see this link.] | [You must be registered and logged in to see this link.]
#include
#include
using std::[You must be registered and logged in to see this link.];
using std::endl;
using std::endl;
using std::[You must be registered and logged in to see this link.];
const int maxx = 20;
void Read_input_from_user(bool grid[][maxx], int vertices)
{
int u, v;
for(int x = 0; x < vertices; ++x)
{
[You must be registered and logged in to see this link.] << "Enter u : \t";
[You must be registered and logged in to see this link.] >> u;
u--;
[You must be registered and logged in to see this link.] << "Enter v : \t";
[You must be registered and logged in to see this link.] >> v;
v--;
grid[u][v] = true;
grid[v][u] = true;
[You must be registered and logged in to see this link.] << "---------------------\n";
}
}
void Breadth_first_search(std::queue<int> &Q, std::vector<int> &trace,
bool grid[][maxx], int start, int nodes)
{
int u;
Q.push(start);
trace[start] = -1;
do{
u = Q.front();
Q.pop();
for(int v = 0; v < nodes; ++v)
{
if((grid[u][v] == true) && trace[v] == 0)
{
Q.push(v);
trace[v] = u;
}
}
}while(!Q.empty());
}
void Trace_result(std::vector<int> &trace, int start, int end, int nodes)
{
[You must be registered and logged in to see this link.] << "From _nodes" << start + 1 << " you can visit :\n";
for(int v = 0; v < nodes; ++v)
{
if(trace[v] != 0)
{
[You must be registered and logged in to see this link.] << " _nodes : " << v + 1 << " , ";
}
}
[You must be registered and logged in to see this link.] << "\n--------------------------------------------\n";
[You must be registered and logged in to see this link.] << "The path from " << start + 1 << " to " << end + 1 << '\n';
if(trace[end] == 0){
[You must be registered and logged in to see this link.] << "Unavailable.! to go to from " << end + 1
<< " to -> " << start + 1 << '\n';
}
else{
while(end != start)
{
[You must be registered and logged in to see this link.] << end + 1 << "<-";
end = trace[end];
}
[You must be registered and logged in to see this link.] << start + 1 << endl;
}
}
int main()
{
//Initialization
std::vector<int> trace(maxx, 0);
std::queue<int> Q;
bool grid[maxx][maxx] = {false};
int nodes, vertices;
[You must be registered and logged in to see this link.] << "Please input the number of Node : \n";
[You must be registered and logged in to see this link.] >> nodes;
[You must be registered and logged in to see this link.] << "Please input the number of Vertices : \n";
[You must be registered and logged in to see this link.] >> vertices;
//Set value for all vertices.
Read_input_from_user(grid, vertices);
//Read the necessary path
int starting_position, finishing_position;
[You must be registered and logged in to see this link.] << "Please Input the Starting Node : \n";
[You must be registered and logged in to see this link.] >> starting_position;
[You must be registered and logged in to see this link.] << "Please Input the Finishing Node : \n";
[You must be registered and logged in to see this link.] >> 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);
return 0;
}
Demo :
