Hello,
The program finds the shortest path between the user inputted nodes. The nodes are integer. Now I need to modify my code to find the path between nodes which are string.
Path between A and B instead of 1 and 2. Please help me to convert my code.
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>
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[i] = new int[n];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
A[i][j] = 0;
}
Graph::~Graph() {
for (int i = 0; i < n; ++i)
delete [] A[i];
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[i] = 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[i])
{
Q.add(i);
visited[i] = 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[i] = 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[i]) {
Q.add(i);
++q;
X[q].current = i;
X[q].prev = p;
visited[i] = true;
if (i == target) found = true;
}
++p;
}
cout << "The minimum length path from " << start;
cout << " to " << target << " is : " << endl;
p = 0;
while (q)
{
Y[p] = X[q].current;
q = X[q].prev;
++p;
}
Y[p] = 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;
}
void asgn() {
Graph f(11);
f.addEdge(1, 8); f.addEdge(1, 4); f.addEdge(1, 10);
f.addEdge(10, 4); f.addEdge(10, 11); f.addEdge(10, 5);
f.addEdge(6, 8); f.addEdge(6, 4); f.addEdge(6, 2);
f.addEdge(11, 2); f.addEdge(2, 9); f.addEdge(7, 9);
f.addEdge(7, 11); f.addEdge(3, 5); f.addEdge(11, 9);
f.addEdge(5, 11);
int start, target;
cout<<"Please enter starting point (1-11) :\n";
cin>>start;
cout<<"Please enter target point (1-11) :\n";
cin>>target;
f.minPath(start, target);
}
void main() {
cout << endl;
asgn();
}