graph.cpp

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

 
template <class Weight, int graph_size>
Network<Weight, graph_size>::Network()
{
}
 
template <class Weight, int graph_size>
void Network<Weight, graph_size>::minimal_spanning(Vertex source,
                     Network<Weight, graph_size> &tree) const
/* 
 
Post: The Network tree contains a minimal spanning tree for the
      connected component of the original Network 
      that contains vertex source.
 
*/

{
 
   tree.make_empty(count);
   bool component[graph_size];   //  Vertices in set X 
   Weight distance[graph_size];  //  Distances of vertices adjacent to X 
   Vertex neighbor[graph_size];  //  Nearest neighbor in set X 
   Vertex w;

   for (w = 0; w < count; w++) {
      component[w] = false;
      distance[w] = adjacency[source][w];
      neighbor[w] = source;
   }

   component[source] = true;     //  source alone is in the set X.
   for (int i = 1; i < count; i++) {
      Vertex v;                  //  Add one vertex v to X on each pass.
      Weight min = infinity;
      for (w = 0; w < count; w++) if (!component[w])
         if (distance[w] < min) {
            v = w;
            min = distance[w];
         }

      if (min < infinity) {
         component[v] = true;
         tree.add_edge(v, neighbor[v], distance[v]);
         for (w = 0; w < count; w++) if (!component[w])
            if (adjacency[v][w] < distance[w]) {
               distance[w] = adjacency[v][w];
               neighbor[w] = v;
            }
      }
      else break;            //  finished a component in disconnected graph
   }
}
 
template <class Weight, int graph_size>
void Network<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 later neighboring vertices." << endl;
   cout << " and the corresponding 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 = v; 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] = adjacency[w][v] = wt;
         }
      } while (c != ':');
   }
}
 
template <class Weight, int graph_size>
void Network<Weight, graph_size>::make_empty(int size = 0)
{
   count = size;
   for (int i = 0; i < size; i++)
      for (int j = 0; j < size; j++)
         adjacency[i][j] = infinity;
}
 
template <class Weight, int graph_size>
void Network<Weight, graph_size>::add_edge(Vertex v, Vertex w, Weight x)
{
   adjacency[v][w] = adjacency[w][v] = x;
}