graph.cpp

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

 
template <class Weight, int graph_size>
int Digraph<Weight, graph_size>::get_count()
{
   return count;
}
 
template <class Weight, int graph_size>
Digraph<Weight, graph_size>::Digraph()
{
   count = 0;
}
 
template <class Weight, int graph_size>
void Digraph<Weight, 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 << " and the corresponding directed edge weight." << endl;
   cout << "Type the pairs of numbers (terminated by a : for each vertex), separated by blanks." << endl;
   for (Vertex v = 0; v < count; v++) {
      for (Vertex w = 0; w < count; w++) adjacency[v][w] = infinity;
      char c;
      cout << "Vertex " << v << "  : " << flush;
      do {
         Vertex w;
         c = cin.get();
         if ('0' <= c && c <= '9') {
            w = c - '0';
            while ((c = cin.get()) >= '0' && c <= '9')
               w = 10 * w + c - '0';
            while (c < '0' || c > '9') c = cin.get();
            Weight wt = c - '0';
            while ((c = cin.get()) >= '0' && c <= '9')
               wt = 10 * wt + c - '0';
            adjacency[v][w] = wt;
         }
      } while (c != ':');
   }
}
 
template <class Weight, int graph_size>
void Digraph<Weight, graph_size>::write()
{
   for (Vertex v = 0; v < count; v++) {
      cout << "Vertex " << v << "  : ";
      for (Vertex w = 0; w < count; w++)
         if (adjacency[v][w] != 0)
            cout << "(" << w << "@" << adjacency[v][w] << ") ";
      cout << "\n";
   }
}
 
template <class Weight, int graph_size>
void Digraph<Weight, graph_size>::set_distances(Vertex source,
                                  Weight distance[]) const
/* 
 
Post: The array distance gives the minimal path weight from vertex source
      to each vertex of the Digraph.
 
*/

{
   Vertex v, w;
   bool found[graph_size];   //  Vertices found in S 
   for (v = 0; v < count; v++) {
      found[v] = false;
      distance[v] = adjacency[source][v];
   }

   found[source] = true; //  Initialize with vertex source alone in the set S.
   distance[source] = 0;

   for (int i = 0; i < count; i++) { //  Add one vertex v to S on each pass.
      Weight min = infinity;
      for (w = 0; w < count; w++) if (!found[w])
         if (distance[w] < min) {
            v = w;
            min = distance[w];
         }

      found[v] = true;
      for (w = 0; w < count; w++) if (!found[w])
         if (min + adjacency[v][w] < distance[w])
             distance[w] = min + adjacency[v][w];
   }
}