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

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

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

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

4、t neighbors[max_size];//鄰接表};,鄰接表,鄰接表的C++實(shí)現(xiàn)（頂點(diǎn)表、鄰接表均為鏈表），這種實(shí)現(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;};,圖的遍歷,和樹的遍歷類似，可以從圖的某個頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個頂點(diǎn)僅被訪問一次，這個過程稱為圖的遍歷。圖的遍歷比樹的遍歷復(fù)雜。樹的遍歷始于根結(jié)點(diǎn)，圖中沒有根結(jié)點(diǎn)。圖中可能存在回路。常用的圖遍歷方法深度優(yōu)先遍歷寬度優(yōu)先遍歷,深度優(yōu)先遍歷,深度優(yōu)先遍歷類似于樹的先根遍歷，其基本思想為：從圖中某個頂點(diǎn)v0出發(fā)，訪問此頂點(diǎn)。然后依次從v0未被訪問

6、的鄰接結(jié)點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中所有和頂點(diǎn)v0連通的頂點(diǎn)都被訪問到。若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。,深度優(yōu)先遍歷,圖中可能包含回路，因此在遍歷過程中，一個頂點(diǎn)有可能被重復(fù)訪問，為此設(shè)置一個布爾數(shù)組記錄頂點(diǎn)是否被訪問過。bool visited[max_size];圖有可能不連通，必須保證圖中所有頂點(diǎn)被訪問。,不是程序，不能編譯,深度優(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)先遍歷的基本思想為：從圖中某個頂點(diǎn)v0出發(fā)，訪問此頂點(diǎn)。然后依次訪問v0的各個未被訪問過的鄰接結(jié)點(diǎn)，然后分別從這些鄰接結(jié)點(diǎn)出發(fā)寬度優(yōu)先遍歷圖，直到圖中所有和頂點(diǎn)v0連通的頂點(diǎn)都被訪問到。若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。,不是程序，不能編譯,深度優(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(); } }},拓?fù)渑判?什么是拓?fù)渑判颍?如果G＝（V, E）是一個無環(huán)的有向圖，則G上的拓?fù)渑判蛑傅氖菆D中頂點(diǎn)滿足下列條件的一種排序。若 ∈E，則在頂點(diǎn)v必須位于頂點(diǎn)w之前。上圖可能的拓?fù)渑判?9 6 3 4 8 2 0 5 1 7 3 6 9 0

13、 2 4 1 5 8 7,拓?fù)渑判虿晃ㄒ唬?拓?fù)渑判蛩惴?常用拓?fù)渑判蚍椒ǎ荷疃葍?yōu)先排序?qū)挾葍?yōu)先排序深度優(yōu)先排序（1）逆序產(chǎn)生拓?fù)渑判颍紫犬a(chǎn)生拓?fù)渑判蛑凶詈笠粋€頂點(diǎn)， 最后產(chǎn)生拓?fù)渑判蛑械牡谝粋€頂點(diǎn)。（2）找一個沒有后繼的頂點(diǎn)并將其作為拓?fù)渑判虻淖詈笠粋€頂點(diǎn)。（3）只有當(dāng)一個頂點(diǎn)的所有后繼頂點(diǎn)已經(jīng)全部加入拓?fù)渑判蚝?，才可把該頂點(diǎn)加入到拓?fù)渑判虻淖钋岸恕?深度優(yōu)先排序,,拓?fù)渑判虻膶?shí)現(xiàn),有向圖采用鄰接表實(shí)現(xiàn)，頂點(diǎn)表采用順序存

14、儲，鄰接表采用鏈?zhǔn)酱鎯Α?typedef int Vertex;template class Graph { int count;//頂點(diǎn)數(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)先排序的實(shí)現(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)先排序的實(shí)現(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)生拓?fù)渑判颍紫犬a(chǎn)生拓?fù)渑判蛑械谝粋€頂點(diǎn)， 最后產(chǎn)生拓?fù)渑判蛑凶詈笠粋€頂點(diǎn)。（2）找一個沒有前

19、趨的頂點(diǎn)并將其作為拓?fù)渑判虻牡谝粋€頂點(diǎn)。（3）只有當(dāng)一個頂點(diǎn)的所有前趨頂點(diǎn)已經(jīng)全部加入拓?fù)渑判蚝螅趴砂言擁旤c(diǎn)加入到拓?fù)渑判虻淖詈蠖?。用一個數(shù)組記錄圖中每個頂點(diǎn)的前趨的個數(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ò)，每條邊上帶有一個非負(fù)的權(quán)值，則從頂點(diǎn)v到頂點(diǎn)w的最短路徑指的是從頂點(diǎn)v到頂點(diǎn)w的所有路徑中權(quán)值之

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

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

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

27、接矩陣實(shí)現(xiàn)。,template class Graph { int count; Weight adjacency[graph_size][graph_size];public: void set_distances(Vertex source, Weight distance[]) const;};,Dijkstra算法的實(shí)現(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]; }},上機(jī)作業(yè),在機(jī)器上用C++分別實(shí)現(xiàn)和圖狀結(jié)構(gòu)有關(guān)的算法。想一想為什么用Dijkstra