السلام عليكم
كيف الأحوال يارفاق
بحاجة لمن يشرح خطوات هذا البرنامج بالتفصيل الممل
وله مني جزيل الشكر
To implement the BFS method in C++ we will use a queue to store the current position of each group of people and search for their available directions to go. Also we will use an additional boolean array to store information about each vertex (whether it is occupied or not) :
visited [ k ] = true if position k is occupied, otherwise visited [ k ] = false
The Breadth First Search pseudocode looks like this (assuming x is the first node to start the traversal) :
for (all vertices 1<= i <= n) do
visited [ i ] = false
ADD x to Queue
visited [ x ] = true
while (Queue is not empty) do
extract information from the Queue to variable k
display k
for (all vertices 1<= i <= n) do
if (visited[ i ] == false AND there is an edge between k and i) then
ADD i to Queue
visited [ i ] = true
end if
end while
The minimum length path algorithm is very similar to this. The only difference is that we need to store the position from which every person came in the traversal process in order to reconstruct the path. We will achieve this using an array and displaying it in reverse order at the end of the traversal. Below you will find the listing that implements both BFS and the minimum path algorithm by encapsulating them inside the Graph class. We have also implemented a Queue class since both use this type of container.
#include <iostream>
using namespace std;
struct node {
int info;
node *next;
};
class Queue {
public:
Queue();
~Queue();
bool isEmpty();
void add(int);
int get();
private:
node *first, *last;
};
class Graph {
public:
Graph(int size = 2);
~Graph();
bool isConnected(int, int);
// adds the (x, y) pair to the edge set
void addEdge(int x, int y);
// performs a Breadth First Search starting with node x
void BFS(int x);
// searches for the minimum length path
// between the start and target vertices
void minPath(int start, int target);
private :
int n;
int **A;
};
Queue::Queue() {
first = new node;
first->next = NULL;
last = first;
}
Queue::~Queue() {
delete first;
}
bool Queue::isEmpty() {
return (first->next == NULL);
}
void Queue::add(int x) {
node *aux = new node;
aux->info = x;
aux->next = NULL;
last->next = aux;
last = aux;
}
int Queue::get() {
node *aux = first->next;
int value = aux->info;
first->next = aux->next;
if (last == aux) last = first;
delete aux;
return value;
}
Graph::Graph(int size) {
int i, j;
if (size < 2) n = 2;
else n = size;
A = new int*[n];
for (i = 0; i < n; ++i)
A = new int[n];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
A[j] = 0;
}
Graph::~Graph() {
for (int i = 0; i < n; ++i)
delete [] A;
delete [] A;
}
bool Graph::isConnected(int x, int y) {
return (A[x-1][y-1] == 1);
}
void Graph::addEdge(int x, int y) {
A[x-1][y-1] = A[y-1][x-1] = 1;
}
void Graph::BFS(int x) {
Queue Q;
bool *visited = new bool[n+1];
int i;
for (i = 1; i <= n; ++i)
visited = false;
Q.add(x);
visited[x] = true;
cout << "Breadth First Search starting from vertex ";
cout << x << " : " << endl;
while (!Q.isEmpty()) {
int k = Q.get();
cout << k << " ";
for (i = 1; i <= n; ++i)
if (isConnected(k, i) && !visited) {
Q.add(i);
visited = true;
}
}
cout << endl;
delete [] visited;
}
void Graph::minPath(int start, int target) {
Queue Q;
int i, p, q;
bool found;
struct aux { int current, prev; };
aux *X = new aux[n+1];
int *Y = new int[n+1];
bool *visited = new bool[n+1];
for (i = 1; i <= n; ++i)
visited = false;
Q.add(start);
visited[start] = true;
found = false;
p = q = 0;
X[0].current = start;
X[0].prev = 0;
while (!Q.isEmpty() && !found) {
int k = Q.get();
for (i = 1; i <= n && !found; ++i)
if (isConnected(k, i) && !visited) {
Q.add(i);
++q;
X[q].current = i;
X[q].prev = p;
visited = true;
if (i == target) found = true;
}
++p;
}
cout << "The minimum length path from " << start;
cout << " to " << target << " is : " << endl;
p = 0;
while (q) {
Yبسم الله الرحمن الرحيم = X[q].current;
q = X[q].prev;
++p;
}
Yبسم الله الرحمن الرحيم = X[0].current;
for (q = 0; q <= p/2; ++q) {
int temp = Y[q];
Y[q] = Y[p-q];
Y[p-q] = temp;
}
for (q = 0; q <= p; ++q)
cout << Y[q] << " ";
cout << endl;
cout << "Length = " << q-1 << endl;
delete [] visited;
delete [] X;
delete [] Y;
}
Let us now write two separate functions, one that traverses the previously presented graph starting from vertex 3 (the same as in the example) and one that finds the minimum length path in the maze described at the beginning of this article. Their names are Traversal() and Maze() respectively. Running the program will generate identical results with the ones we have already calculated.
void Traversal() {
Graph g(5);
g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 4);
g.addEdge(3, 5); g.addEdge(4, 5);
g.BFS(3);
}
void Maze() {
Graph f(15);
f.addEdge(1, 2); f.addEdge(1, 3); f.addEdge(2, 4);
f.addEdge(3, 14); f.addEdge(4, 5); f.addEdge(4, 6);
f.addEdge(5, 7); f.addEdge(6, 13); f.addEdge(7, 8);
f.addEdge(7, 9); f.addEdge(8, 11); f.addEdge(9, 10);
f.addEdge(10, 12); f.addEdge(10, 15); f.addEdge(11, 12);
f.addEdge(13, 14); f.addEdge(14, 15);
f.minPath(1, 10);
}
void main() {
Traversal();
cout << endl;
Maze();
}