graph.cpp

来自「数据结构与程序设计教材源码 数据结构与程序设计教材源码」· C++ 代码 · 共 141 行

 
template <int graph_size>
Digraph<graph_size>::Digraph()
{
   count = 0;
}
 
template <int graph_size>
void Digraph<graph_size>::read()
{
   cout << "How many vertices in the digraph (between 1 and " << graph_size << ")? " << flush;
   cin >> count;
   cout << "For each vertex, give the vertices to which it points." << endl;
   cout << "Type the numbers (terminated by a : for each vertex), separated by blanks." << endl;
   for (Vertex v = 0; v < count; v++) {
      int degree = 0;
      char c;
      cout << "Vertex " << v << "  : " << flush;
      do {
         c = cin.get();
         if ('0' <= c && c <= '9') {
            Vertex w = c - '0';
            while ((c = cin.get()) >= '0' && c <= '9')
               w = 10 * w + c - '0';
            neighbors[v].insert(degree++, w);
         }
      } while (c != ':');
   }
}
 
template <int graph_size>
void Digraph<graph_size>::recursive_depth_sort(Vertex v, bool *visited,
                          List<Vertex> &topological_order)
/* 
 
Pre:  Vertex v of the Digraph does not belong to
     the partially completed List topological_order.
Post: All the successors of v and finally v itself are added to
      topological_order with a depth-first search.
Uses: Methods of class List and the function recursive_depth_sort.
 
*/

{
   visited[v] = true;
   int degree = neighbors[v].size();

   for (int i = 0; i < degree; i++) {
      Vertex w;                       //  A (neighboring) successor of v 
      neighbors[v].retrieve(i, w);
      if (!visited[w])                //  Order the successors of w.
         recursive_depth_sort(w, visited, topological_order);
   }
   topological_order.insert(0, v);    //  Put v into topological_order.
}
 
template <int graph_size>
void Digraph<graph_size>::depth_sort(List<Vertex> &topological_order)
/* 
 
Post: The vertices of the Digraph are placed into
      List topological_order with a depth-first traversal
      of those vertices that do not belong to a cycle.
Uses: Methods of class List, and function recursive_depth_sort
      to perform depth-first traversal.
 
*/

{
   bool visited[graph_size];
   Vertex v;
   for (v = 0; v < count; v++) visited[v] = false;
   topological_order.clear();
   for (v = 0; v < count; v++)
      if (!visited[v])  //  Add v and its successors into topological order.
         recursive_depth_sort(v, visited, topological_order);
}
 
template <int graph_size>
void Digraph<graph_size>::write()
{
   for (Vertex v = 0; v < count; v++) {
      int degree = neighbors[v].size();
      cout << "Vertex " << v << "  : ";
      if (degree == 0) cout << " has no successors" << endl;
      else cout << "has successors: ";
      for (int j = 0; j < degree; j++) {
         Vertex w;
         neighbors[v].retrieve(j, w);
         cout << w;
         if (j < degree - 1) cout << ", ";
         else cout << "\n";
      }
   }
}
 
typedef Vertex Queue_entry;
#include "../../3/QUEUE/QUEUE.H"
#include "../../3/QUEUE/QUEUE.CPP"
 
template <int graph_size>
void Digraph<graph_size>::breadth_sort(List<Vertex> &topological_order)
/* 
 
Post: The vertices of the Digraph are arranged into the List 
      topological_order which is found with a breadth-first
      traversal of those vertices that do not belong to a cycle.
Uses: Methods of classes Queue and List.
 
*/

{
   topological_order.clear();
   Vertex v, w;
   int predecessor_count[graph_size];

   for (v = 0; v < count; v++) predecessor_count[v] = 0;
   for (v = 0; v < count; v++)
      for (int i = 0; i < neighbors[v].size(); i++) { //  Loop over all edges v -- w.
         neighbors[v].retrieve(i, w);
         predecessor_count[w]++;
      }

   Queue ready_to_process;
   for (v = 0; v < count; v++)
      if (predecessor_count[v] == 0)
         ready_to_process.append(v);

   while (!ready_to_process.empty()) {
      ready_to_process.retrieve(v);
      topological_order.insert(topological_order.size(), v);
      for (int j = 0; j < neighbors[v].size(); j++) { //  Traverse successors of v.
         neighbors[v].retrieve(j, w);
         predecessor_count[w]--;
         if (predecessor_count[w] == 0)
            ready_to_process.append(w);
      }
      ready_to_process.serve();
   }
}