數(shù)據(jù)結(jié)構(gòu)（六）

1、數(shù)據(jù)結(jié)構(gòu)（六）,常寶寶北京大學計算機科學與技術(shù)系chbb@pku.edu.cn,內(nèi)容提要,圖狀結(jié)構(gòu)-實現(xiàn)-遍歷-拓撲排序-最短路徑,鄰接矩陣,如果一個有向圖含有n個頂點，則可以用n×n的布爾型矩陣adjacency[n][n]來存儲圖狀結(jié)構(gòu)。若頂點v鄰接到頂點w，則adjacency[v][w]= true，否則adjacency[v][w]= false上述圖狀結(jié)構(gòu)的表示方法稱為鄰接矩陣表示法。對于無向圖而

2、言，采用鄰接矩陣表示法，則鄰接矩陣必為對稱矩陣，即adjacency[v][w]= adjacency[w][v]。,鄰接矩陣,鄰接矩陣的C++實現(xiàn),template class Graph { int count;//頂點數(shù) bool adjacency[max_size][max_size];//鄰接矩陣};,鄰接表,除采用鄰接矩陣表示圖狀結(jié)構(gòu)外，還可以采用鄰接表的方法實現(xiàn)圖狀結(jié)構(gòu)。在鄰接表表示法中，n

3、個頂點的圖狀結(jié)構(gòu)可以表示成一個含有n個元素的線性表（稱為頂點表）和n個線性表（稱為鄰接表）。每個頂點對應(yīng)一個鄰接表，頂點v對應(yīng)的鄰接表記錄了頂點v鄰接到的所有頂點。頂點表和鄰接表既可以采用鏈式線性表也可以采用順序線性表。,鄰接表,,鄰接表,鄰接表的C++實現(xiàn)（頂點表為順序表，鄰接表為鏈表）,typedef int Vertex;template class Graph { int count;//頂點數(shù) Lis

4、t neighbors[max_size];//鄰接表};,鄰接表,鄰接表的C++實現(xiàn)（頂點表、鄰接表均為鏈表），這種實現(xiàn)也稱為十字鏈表法。,class Edge;class Vertex { Edge* first_edge; Vertex* next_vertex;};class Edge { Vertex* end_point; Edge* next_edge;};class Grap

5、h { Vertex* first_vertex;};,圖的遍歷,和樹的遍歷類似，可以從圖的某個頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次，這個過程稱為圖的遍歷。圖的遍歷比樹的遍歷復雜。樹的遍歷始于根結(jié)點，圖中沒有根結(jié)點。圖中可能存在回路。常用的圖遍歷方法深度優(yōu)先遍歷寬度優(yōu)先遍歷,深度優(yōu)先遍歷,深度優(yōu)先遍歷類似于樹的先根遍歷，其基本思想為：從圖中某個頂點v0出發(fā)，訪問此頂點。然后依次從v0未被訪問

6、的鄰接結(jié)點出發(fā)深度優(yōu)先遍歷圖，直到圖中所有和頂點v0連通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直到圖中所有頂點都被訪問到為止。,深度優(yōu)先遍歷,圖中可能包含回路，因此在遍歷過程中，一個頂點有可能被重復訪問，為此設(shè)置一個布爾數(shù)組記錄頂點是否被訪問過。bool visited[max_size];圖有可能不連通，必須保證圖中所有頂點被訪問。,不是程序，不能編譯,深度優(yōu)先

7、遍歷算法,,template void Graph::depth_first( void (*visit)(Vertex&)) const { bool visited[max_size]; Vertex v; for (all v in G) visited[v]=false; for (all v in G) if ( !visited[v] ) traverse(v, visited

8、, visit);},template void Graph::traverse( Vertex &v, bool visted[],void (*visit)(Vertex&)) const { Vertex w; visited[v] = true; (*visit)(v); for (all w adjacent to v) if ( !visited[w] ) tra

9、verse(w, visited, visit);},寬度優(yōu)先遍歷,寬度優(yōu)先遍歷的基本思想為：從圖中某個頂點v0出發(fā)，訪問此頂點。然后依次訪問v0的各個未被訪問過的鄰接結(jié)點，然后分別從這些鄰接結(jié)點出發(fā)寬度優(yōu)先遍歷圖，直到圖中所有和頂點v0連通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直到圖中所有頂點都被訪問到為止。,不是程序，不能編譯,深度優(yōu)先遍歷算法,,temp

10、late void Graph::breadth_first( void (*visit)(Vertex&)) const { Queue q; bool visited[max_size]; Vertex v, w, x; for (all v in G) visited[v]=false; for (all v in G) if ( !visited[v] ) {

11、 q.append(v); while( !q.empty() ) { q.retrieve(w); if ( !visited[w] ) { visited[w]=true; (*visit)(w); for ( all x adjacent to

12、w ) q.append(x); } q.serve(); } }},拓撲排序,什么是拓撲排序？ 如果G＝（V, E）是一個無環(huán)的有向圖，則G上的拓撲排序指的是圖中頂點滿足下列條件的一種排序。若 ∈E，則在頂點v必須位于頂點w之前。上圖可能的拓撲排序 9 6 3 4 8 2 0 5 1 7 3 6 9 0

13、 2 4 1 5 8 7,拓撲排序不唯一！,拓撲排序算法,常用拓撲排序方法：深度優(yōu)先排序?qū)挾葍?yōu)先排序深度優(yōu)先排序（1）逆序產(chǎn)生拓撲排序，首先產(chǎn)生拓撲排序中最后一個頂點， 最后產(chǎn)生拓撲排序中的第一個頂點。（2）找一個沒有后繼的頂點并將其作為拓撲排序的最后一個頂點。（3）只有當一個頂點的所有后繼頂點已經(jīng)全部加入拓撲排序后，才可把該頂點加入到拓撲排序的最前端。,深度優(yōu)先排序,,拓撲排序的實現(xiàn),有向圖采用鄰接表實現(xiàn)，頂點表采用順序存

14、儲，鄰接表采用鏈式存儲。,typedef int Vertex;template class Graph { int count;//頂點數(shù) List neighbors[graph_size];//鄰接表 void recursive_depth_sort(Vertex v, bool visited[], List& topological_order);pub

15、lic: void depth_sort(List& topological_order); void breadth_sort(List& topological_order);};,深度優(yōu)先排序的實現(xiàn),,template void Graph::depth_sort(List& topological_order){ bool visited[graph_size]; Vertex

16、 v; for (v=0; v<count; v++) visited[v]=false; topological_order.clear(); for(v=0; v<count; v++) if (!visited[v]) recursive_depth_sort(v,visited, topological_order);},深度優(yōu)先排序的實現(xiàn),,template

17、void Graph:: recursive_depth_sort(Vertex v, bool *visited, List& topological_order) { visited[v]=true; int degree = neighbors[v].size(); for (int i=0; i<degree; i++) { Vertex w; neighbo

18、rs[v].retrieve(i,w); if (!visited[w]) recursive_depth_sort(w,visited, topological_order); } topological_order.insert(0,v); },寬度優(yōu)先排序,寬度優(yōu)先排序（1）正向產(chǎn)生拓撲排序，首先產(chǎn)生拓撲排序中第一個頂點， 最后產(chǎn)生拓撲排序中最后一個頂點。（2）找一個沒有前

19、趨的頂點并將其作為拓撲排序的第一個頂點。（3）只有當一個頂點的所有前趨頂點已經(jīng)全部加入拓撲排序后，才可把該頂點加入到拓撲排序的最后端。用一個數(shù)組記錄圖中每個頂點的前趨的個數(shù)int predecessor_count[graph_size];,寬度優(yōu)先排序,,寬度優(yōu)先排序,,template void Graph::breadth_sort(List& topological_order){ topological

20、_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++) {

21、 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()

22、) { ready_to_process.retrieve(v); topological_order.insert(topological_order.size(), v); for (int j=0; j<neighbors[v].size(); j++) { neighbors[v].retrieve(j,w); predecessor_count[w]

23、--; if (predecessor_count[w]==0) ready_to_process.append(w); } ready_to_process.serve(); } },最短路徑,最短路徑通常是針對有向網(wǎng)絡(luò)而言的。即邊上帶有權(quán)值的有向圖。假定G是一個有向網(wǎng)絡(luò)，每條邊上帶有一個非負的權(quán)值，則從頂點v到頂點w的最短路徑指的是從頂點v到頂點w的所有路徑中權(quán)值之

24、和最小的路徑。頂點v稱做源點，頂點w稱做終點。,最短路徑,頂點0和頂點1之間的最短路徑是哪條路徑?怎樣快速求出從某給定源點到其它頂點間的最短路徑?,最短路徑,Dijkstra算法依最短路徑的長度遞增的次序求得各條路徑。設(shè)置一個集合S，該集合中存放從給定源點出發(fā)最短路徑已知的所有頂點。因此算法開始時，集合S中只有源點一個頂點。隨著算法的進行，其余的頂點被逐步加入集合S。因此算法要解決的問題是確定每步應(yīng)該加入哪個頂點？設(shè)定一個數(shù)組

25、int distance[graph_size];記錄從源點到其它頂點的距離。,最短路徑,若頂點v已在S中，則distance[v]記錄了從源點到頂點v的最短距離。若頂點v還未加入S中，則distance[v]記錄了從源點到某個S中的頂點w的最短距離加上邊的權(quán)值。distance數(shù)組的初始化。 (1)若從源點鄰接到頂點v(有邊的情況)，則distance[v]即為該邊的權(quán)值。(2)否則(無邊的情況)，則distance[v]

26、為無窮大。算法進行時，從distance中找一個最小值，并將其對應(yīng)的頂點加入到S中。,最短路徑,一旦某頂點v加入S，則重新計算尚未加入S的頂點所對應(yīng)的數(shù)組distance元素值。更新規(guī)則為：若distance[w] > distance[v]+weight()，令distance[w] = distance[v]+weight()如此循環(huán)往復，直到把所有頂點加入S。,最短路徑,,Dijkstra算法的實現(xiàn),有向網(wǎng)絡(luò)用鄰

27、接矩陣實現(xiàn)。,template class Graph { int count; Weight adjacency[graph_size][graph_size];public: void set_distances(Vertex source, Weight distance[]) const;};,Dijkstra算法的實現(xiàn),,template void Graph::set_distances(Verte

28、x source, Weight distance[]) const { Vertex v,w; bool found[graph_size];//集合S for (v=0; v::max(); for (w=0; w<count; w++) if (!found[w]) if ( distance[w]<min) {v=w; min=distance[w];}

29、 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]; }},上機作業(yè),在機器上用C++分別實現(xiàn)和圖狀結(jié)構(gòu)有關(guān)的算法。想一想為什么用Dijkstra