广度优先搜索 C++ 代码

2016-08-01 11:45:20 暂无评论阳光倾城算法与数据结构 631

广度优先搜索 C++ 代码

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;

else n = size;
A = new int*[n];

A[i] = new int[n];

A[i][j] = 0;
}
Graph::~Graph() {

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;

visited[i] = false;
Q.add(x);
visited[x] = true;

while (!Q.isEmpty()) {
int k = Q.get();

if (isConnected(k, i) && !visited[i]) {
Q.add(i);
visited[i] = true;
}
}

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];

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();

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;
}

p = 0;
while (q) {
Y[p] = X[q].current;
q = X[q].prev;
++p;
}
Y[p] = X[0].current;

int temp = Y[q];
Y[q] = Y[p-q];
Y[p-q] = temp;
}

delete [] visited;
delete [] X;
delete [] Y;
}