【数据结构英文课件】GRAPHS.pptVIP

? When we add v to S, we think of v as now colored and also color the shortest path from source to v. Next, we update the entries of distance by checking, for each vertex w not in S, whether a path through v and then directly to w is shorter than the previously recorded distance to w. 3. Example of Shortest Path pg.585 fig.12.10 4. Implementation pg.586 template class Weight, int graph_size class Digraph { public: Digraph(); PrintPath(); void set_distances(Vertex source, Weight distance[ ]) ; protected: int count; Weight adjacency[graph_size][graph_size]; }; template class Weight, int graph_size void DigraphWeight, graph_size :: set distances(Vertex source,Weight distance[ ]) const { Vertex v, w; bool found[graph_size]; for (v = 0; v count; v++) { found[v] = false; distance[v] = adjacency[source][v]; } found[source] = true; distance[source] = 0; for ( int i = 0; i count; i++) { Weight min = infinity; for (w = 0; w count; w++) if (!found[w]) if (distance[w] min) { v = w; min = distance[w]; } found[v] = true; Vertices found in S Initialize with vertex source alone in the set S. Add one vertex v to S on each pass. for (w = 0; w count; w++) if (!found[w]) if (min + adjacency[v][w] distance[w]) distance[w] = min + adjacency[v][w]; } } 12.6 Minimal Spanning Trees pg.587 1. The problem : pg. 587 ? Shortest paths from source 0 to all vertices in a network. ? If the original network is based on a connected graph G, then the shortest paths from a particular source vertex to all other vertices in G form a tree that links up all the vertices of G. ? A (connected) tree that is build up out of all the vertices and some of the edges of G is called a spanning tree of G. DEFINITION A minimal spanning tree of a connected ne