數(shù)據(jù)結(jié)構(gòu)(Java)圖

1、基本內(nèi)容1.圖的定義和基本術(shù)語圖的定義和基本術(shù)語 第第7章章 圖圖2.圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 3.圖的遍歷圖的遍歷 4.圖的最小生成樹圖的最小生成樹 5.最短路徑最短路徑NEXT Neusoft一.圖的定義和基本術(shù)語 NEXT Neusoft一.圖的定義和基本術(shù)語 NEXT Neusoft一.圖的定義和基本術(shù)語 NEXT Neusoft一.圖的定義和基本術(shù)語 NEXT Neusoft1.圖的定義圖的定義 集合集合V和集合和集合E分別為：分別為：V（G）=A,D,T,G,S,W,QE（G）=（A,D），（），（T,G），（），（D,T），（），（G,W），（），（D,S），（），（W,S），）

2、，（A,S），（），（A,Q）一.圖的定義和基本術(shù)語 AGSTQWDNEXT Neusoft一.圖的定義和基本術(shù)語 NEXT Neusoft2.圖的基本術(shù)語圖的基本術(shù)語 2)完全圖完全圖 完全圖完全圖是指圖的邊數(shù)達(dá)到最大值，即圖中每兩個點之間都有邊。是指圖的邊數(shù)達(dá)到最大值，即圖中每兩個點之間都有邊。 完全無向圖完全無向圖一.圖的定義和基本術(shù)語 ASTDNEXT Neusoft一.圖的定義和基本術(shù)語 NEXT Neusoft2.圖的基本術(shù)語圖的基本術(shù)語 3)帶權(quán)圖帶權(quán)圖 帶權(quán)圖帶權(quán)圖是指圖中的每條邊具有一個權(quán)值。是指圖中的每條邊具有一個權(quán)值。一.圖的定義和基本術(shù)語 ASTKFD51938NEXT

3、 Neusoft2.圖的基本術(shù)語圖的基本術(shù)語 4)頂點的度頂點的度 對于無向圖，對于無向圖，頂點的度是指與該頂點連接的邊的數(shù)目頂點的度是指與該頂點連接的邊的數(shù)目。頂點。頂點A的度可以表示為的度可以表示為deg（A） 。對于有向圖，對于有向圖，頂點的度分為出度與入度頂點的度分為出度與入度。在有向圖中，頂點的出度是指由該頂點。在有向圖中，頂點的出度是指由該頂點出發(fā)的邊的數(shù)目，用出發(fā)的邊的數(shù)目，用outdeg（）表示；頂點的入度是指指向該頂點邊的數(shù)目，（）表示；頂點的入度是指指向該頂點邊的數(shù)目，用用indeg（）表示。（）表示。 一.圖的定義和基本術(shù)語 NEXT Neusoft2.圖的基本術(shù)語圖的基

4、本術(shù)語 5)路徑、簡單路徑和回路路徑、簡單路徑和回路 路徑路徑是從一個頂點到另一個頂點所經(jīng)過的頂點序列。是從一個頂點到另一個頂點所經(jīng)過的頂點序列。簡單路徑簡單路徑是指一條路徑上，除起點與終點外，其余頂點均不相同的路徑。是指一條路徑上，除起點與終點外，其余頂點均不相同的路徑。若路徑的起點與終點相同，則該路徑稱為若路徑的起點與終點相同，則該路徑稱為回路回路。 一.圖的定義和基本術(shù)語 NEXT Neusoft2.圖的基本術(shù)語圖的基本術(shù)語 6)連通圖連通圖 在圖中，從任意一個頂點出發(fā)有路徑可以到達(dá)該圖中的其他任意一個頂點，則該在圖中，從任意一個頂點出發(fā)有路徑可以到達(dá)該圖中的其他任意一個頂點，則該圖為圖

5、為連通圖連通圖，否則該圖為，否則該圖為非連通圖非連通圖。 一.圖的定義和基本術(shù)語 NEXT NeusoftNEXT NeusoftNEXT Neusoft1.鄰接矩陣表存儲鄰接矩陣表存儲 鄰接矩陣存儲鄰接矩陣存儲是用一維數(shù)組存儲圖中頂點的信息，用矩陣表示圖中各頂點之間的是用一維數(shù)組存儲圖中頂點的信息，用矩陣表示圖中各頂點之間的鄰接關(guān)系。若圖鄰接關(guān)系。若圖G（V，E）有）有n個頂點，則個頂點，則Av0,v1,vn-1表示表示G中各頂點相中各頂點相鄰關(guān)系為一個鄰關(guān)系為一個nn的矩陣，矩陣中元素的值為：的矩陣，矩陣中元素的值為：二.圖的存儲結(jié)構(gòu) ，其它0E(G)v,v或)v,(v若1, jijiji

6、ANEXT Neusoft1.鄰接矩陣表存儲鄰接矩陣表存儲 二.圖的存儲結(jié)構(gòu) NEXT Neusoft1.鄰接矩陣表存儲鄰接矩陣表存儲 二.圖的存儲結(jié)構(gòu) NEXT Neusoft2.鄰接表存儲鄰接表存儲 鄰接表存儲鄰接表存儲是將順序存儲與鏈?zhǔn)酱鎯Y(jié)合的存儲方法。是將順序存儲與鏈?zhǔn)酱鎯Y(jié)合的存儲方法。鄰接表表示法類似于樹的孩子鏈表表示法。鄰接表表示法類似于樹的孩子鏈表表示法。對于圖對于圖G中的每一個頂點中的每一個頂點vi，將所有與頂點，將所有與頂點vi有連線的頂點有連線的頂點vj連成一個單鏈表，連成一個單鏈表，這個單鏈表就稱為頂點這個單鏈表就稱為頂點vi的鄰接表，再將所有頂點的鄰接表表頭放到數(shù)組

7、中，就的鄰接表，再將所有頂點的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。構(gòu)成了圖的鄰接表。 二.圖的存儲結(jié)構(gòu) NEXT Neusoft2.鄰接表存儲鄰接表存儲 二.圖的存儲結(jié)構(gòu) NEXT Neusoft2.鄰接表存儲鄰接表存儲 二.圖的存儲結(jié)構(gòu) noNEXT Neusoft1.深度優(yōu)先遍歷深度優(yōu)先遍歷 （DFS）圖的深度優(yōu)先遍歷圖的深度優(yōu)先遍歷是以圖的某一頂點是以圖的某一頂點V0作為出發(fā)點，首先訪問該點，然后依次從作為出發(fā)點，首先訪問該點，然后依次從V0的各個未被訪問的鄰接點出發(fā)，進(jìn)行深度優(yōu)先遍歷，直至圖中所有和的各個未被訪問的鄰接點出發(fā)，進(jìn)行深度優(yōu)先遍歷，直至圖中所有和V0相通相通的頂點都被

8、訪問到。若此時圖中還有頂點未被訪問，則以該頂點為起點重復(fù)上述的頂點都被訪問到。若此時圖中還有頂點未被訪問，則以該頂點為起點重復(fù)上述訪問過程，直至圖中所有頂點都被訪問到為止。訪問過程，直至圖中所有頂點都被訪問到為止。 三.圖的遍歷 NEXT Neusoft三.圖的遍歷 NEXT Neusoft三.圖的遍歷 NEXT Neusoft三.圖的遍歷 遍歷結(jié)果為：遍歷結(jié)果為：A，B，E，D，F(xiàn)，CA，E，D，F(xiàn)，C，BNEXT Neusoft1.深度優(yōu)先遍歷深度優(yōu)先遍歷 voiddsf(intindex)/未找到指定結(jié)點，退出未找到指定結(jié)點，退出if(vertexsindex=null)return;/

9、創(chuàng)建棧，用于記錄已訪問結(jié)點創(chuàng)建棧，用于記錄已訪問結(jié)點Stacks=newStack(vertexs.length);vertexsindex.visit();s.push(index);三.圖的遍歷 NEXT Neusoft1.深度優(yōu)先遍歷深度優(yōu)先遍歷 /如果棧不為空，繼續(xù)如果棧不為空，繼續(xù)while(!s.isEmpty()index=fNeighbor(s.peek();if(index!=-1)/訪問結(jié)點訪問結(jié)點vertexsindex.visit();s.push(index);elses.pop();/清空所有訪問標(biāo)志清空所有訪問標(biāo)志clean();三.圖的遍歷 NEXT Neuso

10、ft2.廣度優(yōu)先遍歷廣度優(yōu)先遍歷 廣度優(yōu)先遍歷廣度優(yōu)先遍歷從圖的某一頂點從圖的某一頂點V0出發(fā)，依次訪問出發(fā)，依次訪問V0未被訪問過的鄰接點，然后未被訪問過的鄰接點，然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至所有鄰接點都被訪問到。若此時分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至所有鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則以該頂點作為起點，重復(fù)上述過程，直至圖中所有頂圖中尚有頂點未被訪問，則以該頂點作為起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。點都被訪問為止。三.圖的遍歷 NEXT Neusoft2.廣度優(yōu)先遍歷廣度優(yōu)先遍歷 遍歷結(jié)果為遍歷結(jié)果為A，F(xiàn)，D，S，T，W 三.圖

11、的遍歷 ASTFDWNEXT Neusoft2.廣度優(yōu)先遍歷廣度優(yōu)先遍歷 voidbsf(intindex)/找不到指定頂點，退出找不到指定頂點，退出if(vertexsindex=null)return;/創(chuàng)建隊列，用于存放訪問過的結(jié)點創(chuàng)建隊列，用于存放訪問過的結(jié)點QStoreq=newQStore(vertexs.length);/訪問指定結(jié)點訪問指定結(jié)點vertexsindex.visit();三.圖的遍歷 NEXT Neusoft2.廣度優(yōu)先遍歷廣度優(yōu)先遍歷 /將訪問過的接點入隊將訪問過的接點入隊q.push(index);/當(dāng)隊列為空時，遍歷結(jié)束當(dāng)隊列為空時，遍歷結(jié)束while(!q

12、.isEmpty()index=q.pop();inti;/找隊頭結(jié)點所有的鄰接結(jié)點，并標(biāo)記找隊頭結(jié)點所有的鄰接結(jié)點，并標(biāo)記while(i=fNeighbor(index)!=-1)vertexsi.visit();q.push(i); 三.圖的遍歷 NEXT Neusoft三.圖的遍歷 NEXT Neusoft三.圖的遍歷 NEXT Neusoft三.圖的遍歷 NEXT Neusoft三.圖的遍歷 NEXT Neusoft1.生成樹生成樹若從圖的某頂點出發(fā)，可以依次訪問到圖中所有頂點，則遍歷時經(jīng)過的邊和頂點若從圖的某頂點出發(fā)，可以依次訪問到圖中所有頂點，則遍歷時經(jīng)過的邊和頂點所構(gòu)成的子圖，稱

13、作該所構(gòu)成的子圖，稱作該圖的生成樹圖的生成樹。 圖的生產(chǎn)樹并不是唯一的圖的生產(chǎn)樹并不是唯一的。四.圖的最小生成樹 NEXT Neusoft四.圖的最小生成樹 NEXT Neusoft四.圖的最小生成樹 NEXT Neusoft四.圖的最小生成樹 NEXT Neusoft四.圖的最小生成樹 求最小生成樹的算法(1) 克魯斯卡爾算法克魯斯卡爾算法圖的存貯結(jié)構(gòu)采用邊集數(shù)組,且權(quán)值相等的邊 在數(shù)組中排列次序可以是任意的. 該方法對于邊相對比較多的不是很實用,浪費(fèi)時間.(2) 普里姆算法普里姆算法（prim）圖的存貯結(jié)構(gòu)采用鄰接矩陣.此方法是按各個頂點連通的步驟進(jìn)行,需要用一個頂點集合,開始為空集,以后

14、將以連通的頂點陸續(xù)加入到集合中,全部頂點加入集合后就得到所需的最小生成樹 .NEXT Neusoft四.圖的最小生成樹 NEXT Neusoft四.圖的最小生成樹 NEXT Neusoft四.圖的最小生成樹 v1v4v3v6v5v2v7NEXT Neusoft五.最短路徑 NEXT Neusoft五.最短路徑 NEXT Neusoft五.最短路徑 NEXT Neusoft五.最短路徑 v1v2v6v7v3v4v52421310258461v1v2v6v7v3v4v52421310258461權(quán)值和為負(fù)的回權(quán)值和為負(fù)的回路路注注:假定沒有假定沒有權(quán)值和為負(fù)的回路權(quán)值和為負(fù)的回路,頂點頂點s到頂點

15、到頂點s的路徑長度定義為的路徑長度定義為0.第6章 圖 6.6.1 單源最短路徑單源最短路徑（單源最短路徑（Single-SourceShortestPath）問題：）問題：給定帶權(quán)有向圖（或無向圖）給定帶權(quán)有向圖（或無向圖）G（V，E）和）和源點源點v0V，求從，求從v0到到G中其余各頂點的中其余各頂點的最短路徑最短路徑（路徑上的權(quán)值和達(dá)到最?。?。（路徑上的權(quán)值和達(dá)到最小）。2/24NEXT NeusoftDijkstra算法思想：算法思想：1、設(shè)G=(V,E)是一個帶權(quán)有向圖，把圖中頂點集合V分成兩組2、第一組為已求出最短路徑的頂點集合3、第二組為其余未確定最短路徑的頂點集合（用U表示），4、按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。NEXT Neusoft五.最短路徑 NEXT Neusoft五.最短路徑 NEXT Neusoft五.最短路徑 NEXT NeusoftFloyd算法思想：算法思想：1、從任意節(jié)點i到任意節(jié)