graphbfs.h

来自「图论：最短路径算法实现 Graph.gph GraphBFS.h Grap」· C头文件 代码 · 共 62 行

#ifndef GRAPHBFS_H
#define GRAPHBFS_H

#include "queue.h"

int const UNREACHABLE = -2;
int const SOURCE = -1;

void printPath(Graph* G, int path[], int source, int destination, int& length);

void shortestPath(Graph* G, int source, int destination, Queue<int>* Q, int path[])
{
  int v, w;

  for (int i = 0; i < G->n(); i++)
	path[i] = UNREACHABLE;

  G->cleanAllMark();

  Q->enqueue(source);  // Initialize Q

  path[source] = SOURCE;

  G->setMark(source, VISITED);

  while (Q->length() != 0)
  { // Process all vertices on Q
    Q->dequeue(v);
    for (w=G->first(v); w<G->n(); w = G->next(v,w))
      if (G->getMark(w) == UNVISITED)
	  {
        G->setMark(w, VISITED);
        Q->enqueue(w);
		path[w] = v;
      }
  }

  if (path[destination] == UNREACHABLE)
	cout << source << " and " << destination << " is Unreachable." << endl;
  else
  {
	int length = 0;
	cout << "Shortest Path between " << source << " and ";
	cout << destination << " : " << endl;
	printPath(G, path, source, destination, length);
	cout << endl;
	cout << "Length : " << length << endl;
  }
}


void printPath(Graph* G, int path[], int source, int destination,int& length)
{
  if (path[destination] != SOURCE)
  {
	printPath(G, path, source, path[destination], length);
	length++;
  }
  cout << destination << " ";
}

#endif