Question

1.Link_Graph.h

#include <iostream>
#include <queue>
using namespace std;

#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

queue<int> Q;
struct Vertex;
struct Edge
{
  int start;
  int end;
  int value;
  Edge *next;
  Edge(int s, int e, int v):start(s),end(e),value(v),next(NULL){}
};
struct Vertex
{
  int color;
  int d;
  int Pie;
  Edge *head;
  Vertex():head(NULL),color(WHITE),d(0x7fffffff),Pie(0){};
};
class Link_Graph
{
public:
  int n;
  Vertex *V;
  Link_Graph(int num):n(num)
  {
    V = new Vertex[n+1];
  }
  ~Link_Graph(){delete []V;}
  void AddSingleEdge(int start, int end, int value = 1)
  {
    Edge *NewEdge = new Edge(start, end, value);
    if(V[start].head == NULL || V[start].head->end > end)
    {
      NewEdge->next = V[start].head;
      V[start].head = NewEdge;
    }
    else
    {
      Edge *e = V[start].head, *pre = e;
      while(e != NULL && e->end < end)
      {
        pre = e;
        e = e->next;
      }
      if(e && e->end == end)
      {
        delete NewEdge;
        return;
      }
      NewEdge->next = e;
      pre->next = NewEdge;
    }
  }
  void AddDoubleEdge(int a, int b, int value = 1)
  {
    AddSingleEdge(a, b, value);
    AddSingleEdge(b, a, value);
  }
  void DeleteSingleEdge(int start, int end)
  {
    Edge *e = V[start].head, *pre = e;
    while(e && e->end < end)
    {
      pre = e;
      e = e->next;
    }
    if(e == NULL || e->end > end) return;
    if(e == V[start].head)
      V[start].head = e->next;
    else
      pre->next = e->next;
    delete e;
  }
  void DeleteDoubleEdge(int a, int b)
  {
    DeleteSingleEdge(a, b);
    DeleteSingleEdge(b, a);
  }
  //22.2
  //广度优先搜索
  void BFS(int s);
  //广度优先树
  void Print_Path(int s, int v);
};

void Link_Graph::BFS(int s)
{
  int i;
  for(i = 1; i <= n; i++)
  {
    V[i].color = WHITE;
    V[i].d = 0x7fffffff;
    V[i].Pie = 0;
  }
  V[s].color = GRAY;
  V[s].d = 0;
  V[s].Pie = 0;
  while(!Q.empty())Q.pop();
  Q.push(s);
  while(!Q.empty())
  {
    int u, v;
    u = Q.front();Q.pop();
    Edge *e = V[u].head;
    while(e)
    {
      v = e->end;
      if(V[v].color == WHITE)
      {
        V[v].color = GRAY;
        V[v].d = V[u].d + 1;
        V[v].Pie = u;
        Q.push(v);
      }
      e = e->next;
    }
    V[u].color = BLACK;
  }
}

void Link_Graph::Print_Path(int s, int v)
{
  BFS(s);
  if(v == s)
    cout<<s<<' ';
  else
  {
    if(V[v].Pie == 0)
      cout<<"no path from "<<s<<" to "<<v<<" exists.";
    else
    {
      Print_Path(s, V[v].Pie);
      cout<<v<<' ';
    }
  }
}

2.main.cpp

#include <iostream>
#include "Link_Graph.h"
using namespace std;
/*
1 2
1 5
2 6
6 7
6 3
3 7
3 4
7 8
7 4
4 8
*/
int main()
{
  Link_Graph *G = new Link_Graph(8);
  int i = 0, a, b;
  for(i = 1; i <= 10; i++)
  {
    cin>>a>>b;
    G->AddDoubleEdge(a,b);
  }
  G->BFS(2);
  for(i = 1; i <= 8; i++)
    cout<<G->V[i].d<<' ';
  cout<<endl;
  int s, v;
  while(cin>>s>>v)
  {
    G->Print_Path(s, v);
    cout<<endl;
  }
  return 0;
}