數(shù)據(jù)結(jié)構(gòu)圖總結(jié)PPT課件

1、圖 圖的基本概念 圖的存儲表示 圖的遍歷與連通性 最小生成樹 最短路徑 活動網(wǎng)絡(luò) 第1頁/共116頁(vertex)： 第2頁/共116頁00001111222265433 第3頁/共116頁。0123子圖子圖0130123023第4頁/共116頁第5頁/共116頁012301230123第6頁/共116頁圖，在圖，在n個頂點(diǎn)的情形下，有個頂點(diǎn)的情形下，有n-1條邊。條邊。第7頁/共116頁class Graph public: Graph ( ); void InsertVertex ( Type & vertex ); void InsertEdge ( int v1, int v

2、2, int weight ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 ); int IsEmpty ( ); Type GetWeight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); 第8頁/共116頁, , ( , ) . , 1A0i jEi jEEdge i jiforiforotherwiseotherwise第9頁/共116頁第10頁/共116頁10( ).

3、njOD iAEdge ij10( ). nkID jAEdge kj第11頁/共116頁( , ),() ,(), WEEA.edgeEE0i jiji, ji, jijiji, ji, jij若若且且或或若若且且或或若若63129542031014092A.edge3508608第12頁/共116頁ABCDdata adjABCD0123dest linkdest link 130210 第13頁/共116頁ABCdata adjABC012dest linkdest link data adjABC012dest link102 011 第14頁/共116頁BACD9528data ad

4、jABCD0123dest cost link 1 53 62 83 21 96第15頁/共116頁第16頁/共116頁 mark vertex1 vertex2 path1 path2 第17頁/共116頁 第18頁/共116頁 第19頁/共116頁 mark vertex1 vertex2 path1 path2第20頁/共116頁 data Firstin Firstout第21頁/共116頁mark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE第2

5、2頁/共116頁 在有向圖的十字鏈表中，從頂點(diǎn)結(jié)點(diǎn)的firstout指針域出發(fā)，沿邊結(jié)點(diǎn)中的path1域的鏈一直走到底正好是原來的鄰接表結(jié)構(gòu)。統(tǒng)計鏈中邊結(jié)點(diǎn)的個數(shù)可求得該頂點(diǎn)的出度。 從頂點(diǎn)結(jié)點(diǎn)的firstin指針域出發(fā)，沿邊結(jié)點(diǎn)中的path2域的鏈一直走到底正好是原來的逆鄰接表結(jié)構(gòu)。統(tǒng)計鏈中邊結(jié)點(diǎn)的個數(shù)可求得該頂點(diǎn)的入度。第23頁/共116頁第24頁/共116頁第25頁/共116頁第26頁/共116頁ACDEGBFIHACDEGBFIH123456789123456789前進(jìn)回退深度優(yōu)先搜索過程深度優(yōu)先搜索過程 深度優(yōu)先生成樹深度優(yōu)先生成樹第27頁/共116頁template void Gr

6、aph :DFS ( ) int * visited = new int NumVertices; for ( int i = 0; i NumVertices; i+ ) visited i = 0; /訪問數(shù)組 visited 初始化 DFS (0, visited ); /從頂點(diǎn)0出發(fā)開始搜索 delete visited; /釋放 visited 第28頁/共116頁template void Graph :DFS ( const int v, int visited ) cout GetValue (v) ; /訪問頂點(diǎn) v visitedv = 1; /頂點(diǎn) v 作訪問標(biāo)記 int

7、 w = GetFirstNeighbor (v); /取 v 的第一個鄰接頂點(diǎn) w while ( w != -1 ) /若鄰接頂點(diǎn) w 存在 if ( !visitedw ) DFS ( w, visited ); /若頂點(diǎn) w 未訪問過, 遞歸訪問頂點(diǎn) w w = GetNextNeighbor ( v, w ); /取頂點(diǎn) v 排在 w 后的下一個鄰接頂點(diǎn) 第29頁/共116頁Avisited0=1w=1DFS(1,visited)w=3DFS(3,visited)w=-1Bvisited1=1w=0w=2DFS(2,visited)w=-1Cvisited2=1w=1w=-1Dvis

8、ited3=1w=0w=-1DFS（0，visited）ABCD0123第30頁/共116頁ACDEGBFIHACDEGBFH123456789123456789廣度優(yōu)先搜索過程廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先生成樹I第31頁/共116頁第32頁/共116頁第33頁/共116頁template void Graph :BFS ( int v ) int * visited = new intNumVertices; for ( int i = 0; i NumVertices; i+ ) visitedi = 0; /visited初始化 cout GetValue (v) ; vis

9、itedv = 1; Queue q; q.EnQueue (v); /進(jìn)隊列 while ( !q.IsEmpty ( ) ) /隊空搜索結(jié)束 v = q.DeQueue ( ); int w = GetFirstNeighbor (v); while ( w != -1 ) /若鄰接頂點(diǎn) w 存在 if ( !visitedw ) /未訪問過 cout GetValue (w) ; visitedw = 1; q.EnQueue (w); w = GetNextNeighbor (v, w); /內(nèi)層內(nèi)層whilewhile循環(huán)循環(huán)重復(fù)檢測 v v 的所有鄰接頂點(diǎn) /外層while循環(huán)，判

10、隊列空否 delete visited; 第34頁/共116頁例子 給出下圖從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先搜索得到的深度優(yōu)先生成樹 給出下圖從頂點(diǎn)2出發(fā)進(jìn)行廣度優(yōu)先搜索得到的廣度優(yōu)先生成樹第35頁/共116頁第36頁/共116頁第37頁/共116頁ACDEIBFOGHJNMLK非連通無向圖AHKCDEIBFOGJNML非連通圖的連通分量第38頁/共116頁ABCDEFGHIJKLMNO01234567891011121314432150065064154989787131211141014101012110ACDEBFGIHJONMLK非連通無向圖的鄰接表表示第39頁/共116頁template v

11、oid Graph :Components ( ) int *visited = new intNumVertices; for ( int i = 0; i NumVertices; i+ ) visitedi = 0; /visited 初始化 for ( i = 0; i NumVertices; i+ ) if ( !visitedi ) /檢測頂點(diǎn)是否訪問過 DFS ( i, visited ); /未訪問, 出發(fā)訪問 OutputNewComponent ( ); /連通分量 delete visited; 第40頁/共116頁第41頁/共116頁第42頁/共116頁1050461

12、3228102514242216181250461325046132原圖 (a) (b)第43頁/共116頁1012504613228102514242216181250461325046132101412原圖 (c) (d)504613210141612(e) (f) (g)504613210142216125046121025142216123第44頁/共116頁 tail head cost 邊的兩個頂點(diǎn)位置 邊的權(quán)值第45頁/共116頁第46頁/共116頁const int MAXNUM = 機(jī)器可表示的機(jī)器可表示的, 問題問題中中 不可能出現(xiàn)的大數(shù)不可能出現(xiàn)的大數(shù)class MinS

13、panTree;/最小生成樹的前視類最小生成樹的前視類聲明聲明class MSTEdgeNode /生成樹邊結(jié)點(diǎn)類friend class MinSpanTree;private: int tail, head; /生成樹各邊的兩頂點(diǎn) float cost; /生成樹各邊的權(quán)值public: MSTEdgeNode ( ) /構(gòu)造函數(shù) : tail ( -1 ), head ( -1 ), cost ( 0 ) ；第47頁/共116頁class MinSpanTree protected: MSTEdgeNode * edgevalue;/邊值數(shù)組 int MaxSize, n;public:

14、 MinSpanTree ( int sz = NumVertices-1 ) : MaxSize(sz), n (0) /數(shù)組最大元素個數(shù)和當(dāng)前個數(shù) edgevalue = new MSTEdgeNodeMaxSize; int Insert ( MSTEdgeNode& item );第48頁/共116頁void Graph :Kruskal ( MinSpanTree& T ) MSTEdgeNode e; /邊結(jié)點(diǎn)輔助單元 MinHeap H( NumEdges ); int NumVertices = VerticesList.last; /頂點(diǎn)數(shù) UFSets F

15、( NumVertices ); /并查集 for ( int u = 0; u NumVertices; u+ ) for ( int v = u +1; v NumVertices; v+ ) if ( Edgeuv != MAXNUM ) e.tail = u; e.head = v; /插入堆 e.cost = Edgeuv; H.Insert (e); 第49頁/共116頁int count = 1; /最小生成樹加入邊數(shù)計數(shù) while ( count NumVertices ) H.RemoveMin ( e ); /從堆中退出一條邊 u = F.Find ( e.tail );

16、 /檢測兩端點(diǎn)的根 v = F.Find ( e.head ); if ( u != v ) /根不在同一連通分量 F.Union ( u, v ); /合并 T.Insert ( e ); /該邊存入最小生成樹 count+; 第50頁/共116頁并查集鄰接矩陣表示-2-2-2-2-1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1-102-1-1-10-2200000 1 2 3 4 5 6-21-11-2-1-421-2 -51211-711211F 0 1 2 3 4 5 6 0 28 10 028 0 16 14 1 16 0 12 2 12 0 22 18 3 22 0

17、25 24 410 25 0 5 14 18 24 0 65046132281025142422161812第51頁/共116頁Kruskal的算法復(fù)雜度 建立最小堆檢測鄰接矩陣O(n2) e次堆插入操作O(elog2e) e次出堆操作O(elog2e) 2e次并查集find操作O(elog2n) n-1次union操作O(n) 復(fù)雜度為O(elog2e+elog2n+n2+n)第52頁/共116頁例子 采用kruskal算法求下圖的最小生成樹，并給出求解過程中堆，并查集和最小生成樹的變化1234567111095786第53頁/共116頁1234567111095786建最小堆建最小堆第54

18、頁/共116頁1234567111095786建最小堆建最小堆第55頁/共116頁并查集并查集第56頁/共116頁并查集并查集第57頁/共116頁31-6335123456并查集并查集第58頁/共116頁1234567957631-63350123456第59頁/共116頁第60頁/共116頁252510504613228102514242216185046132504613210原圖 (a) (b)504613210(c) (d) (e) (f)50461321022125046121025142216123252212第61頁/共116頁50461322810251424221618120

19、281028016141601212022182202524102501418240第62頁/共116頁0 28 10 - -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 602810280161416012120221822025241025014182405046132281025142422161812第63頁/共116頁第64頁/共116頁0 28 10 - -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 6選選 v=5選邊選邊 (0,5)0281028016141601212022182202524102501418

20、240第65頁/共116頁頂點(diǎn)頂點(diǎn)v=5加入生成樹頂點(diǎn)集合：加入生成樹頂點(diǎn)集合：0 28 25 10 - -1 0 0 0 5 - -1 0 lowcostnearvex0 1 2 3 4 5 6選選 v=4選邊選邊 (5,4)50461322810251424221618原圖 邊 (0,5,10) 加入生成樹1204613210255第66頁/共116頁0 1 2 3 4 5 6頂點(diǎn)頂點(diǎn)v=4加入生成樹頂點(diǎn)集合：加入生成樹頂點(diǎn)集合：0 28 22 25 10 24 - -1 0 0 4 - -1 - -1 4 lowcostnearvex選選 v=3選邊選邊 (4,3)50461322810

21、251424221618原圖 邊 (5,4,25) 加入生成樹125046132102522第67頁/共116頁頂點(diǎn)頂點(diǎn)v=3加入生成樹頂點(diǎn)集合：加入生成樹頂點(diǎn)集合：0 28 12 22 25 10 18 - -1 0 3 - -1 - -1 - -1 3 lowcostnearvex0 1 2 3 4 5 6選選 v=2選邊選邊 (3,2)50461322810251424221618原圖 邊 (4,3,22) 加入生成樹12504613210252212第68頁/共116頁lowcostnearvex0 1 2 3 4 5 6頂點(diǎn)頂點(diǎn)v=2加入生成樹頂點(diǎn)集合：加入生成樹頂點(diǎn)集合：0 16

22、12 22 25 10 18 - -1 2 - -1 - -1 - -1 - -1 3 選選 v=1選邊選邊 (2,1)50461322810251424221618原圖 邊 (3,2,12) 加入生成樹125041321025221612第69頁/共116頁頂點(diǎn)頂點(diǎn)v=1加入生成樹頂點(diǎn)集合：加入生成樹頂點(diǎn)集合：0 16 12 22 25 10 14 - -1 - -1 - -1 - -1 - -1 - -1 1 lowcostnearvex0 1 2 3 4 5 6選選 v=6選邊選邊 (1,6)50461322810251424221618原圖 邊 (2,1,16) 加入生成樹125046

23、132102514221612第70頁/共116頁lowcostnearvex0 1 2 3 4 5 6頂點(diǎn)頂點(diǎn)v=6加入生成樹頂點(diǎn)集合：加入生成樹頂點(diǎn)集合：0 16 12 22 25 10 14 - -1 - -1 - -1 - -1 - -1 - -1 - -1 50461322810251424221618原圖 邊 (1,6,14) 加入生成樹125046132102514221612第71頁/共116頁(0, 5, 10), (5, 4, 25), (4, 3, 22),(3, 2, 12), (2, 1, 16), (1, 6, 14)第72頁/共116頁void Graph :Pr

24、im ( MinSpanTree &T ) int NumVertices = VerticesList.last; /頂點(diǎn)數(shù) float * lowcost = new floatNumVertices; int * nearvex = new intNumVertices; for ( int i = 1; i NumVertices; i+ ) lowcosti = Edge0i; /頂點(diǎn)0到各邊代價 nearvexi = 0; /及最短帶權(quán)路徑 nearvex0 = -1; /加到生成樹頂點(diǎn)集合 MSTEdgeNode e; /最小生成樹結(jié)點(diǎn)單元 第73頁/共116頁for (

25、 i = 1; i NumVertices; i+ ) /循環(huán)n-1次, 加入n-1條邊 float min = MAXNUM; int v = 0; for ( int j = 0; j NumVertices; j+ ) if ( nearvexj != -1 & lowcostj min ) v = j; min = lowcostj; /1 /求生成樹外頂點(diǎn)到生成樹內(nèi)頂點(diǎn)具有最 /小權(quán)值的邊, v是當(dāng)前具最小權(quán)值的邊 if ( v ) /v=0表示再也找不到要求頂點(diǎn) e.tail = nearvexv; e.head = v; e.cost = lowcostv; T.Inse

26、rt (e); /選出的邊加入生成樹 2 nearvexv = -1; /該邊加入生成樹標(biāo)記 第74頁/共116頁 for ( j = 1; j NumVertices; j+ ) if ( nearvex j != -1 & Edgev j lowcost j ) lowcost j = Edgev j; /需要修改 3 nearvex j = v; /4 /end for循環(huán)n-1次, 加入n-1條邊第75頁/共116頁第76頁/共116頁第77頁/共116頁10432101003050206010v0 v1 (v0,v1) 10 v2 (v0,v1,v2) (v0,v3,v2)

27、,60,50 v3 (v0,v3) 30 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100,90,60 第78頁/共116頁第79頁/共116頁對于每一個對于每一個i V- S ; 判斷：若判斷：若S = V, 則算法結(jié)束，否則轉(zhuǎn)則算法結(jié)束，否則轉(zhuǎn) 。第80頁/共116頁Demo of Dijkstra algorithm041231050102060301000 10 30 100 0 50 0 10 20 0 60 0第81頁/共116頁How to get the path from vertex 0 (source) to i (dest)? path4

28、 = 2 path2 = 3 path3 = 0，The path is 0, 3, 2, 4，(from 0 to 4)第82頁/共116頁const int NumVertices = 6; /圖最大頂點(diǎn)個數(shù)class Graph /圖的類定義 private: float EdgeNumVerticesNumVertices; float distNumVertices; /最短路徑長度數(shù)組 int pathNumVertices; /最短路徑數(shù)組 int SNumVertices;/最短路徑頂點(diǎn)集public: void ShortestPath ( int, int ); int c

29、hoose ( int ); 第83頁/共116頁void Graph : ShortestPath ( int n, int v )/Graph是一個具有 n 個頂點(diǎn)的帶權(quán)有向圖, 各/邊上的權(quán)值由Edgeij給出。本算法建立起/一個數(shù)組: distj, 0 jn, 是當(dāng)前求到的從頂/點(diǎn) v 到頂點(diǎn) j 的最短路徑長度, 同時用數(shù)組/pathj, 0 jn, 存放求到的最短路徑。 for ( int i = 0; i n; i+) disti = Edgevi; /dist數(shù)組初始化 Si = 0; if ( i != v & disti MAXNUM) pathi = v; els

30、e pathi = -1; /path數(shù)組初始化 Sv = 1; distv = 0; /頂點(diǎn)v加入頂點(diǎn)集合 第84頁/共116頁/選當(dāng)前不在集合S中具有最短路徑的頂點(diǎn)u for ( i = 0; i n-1; i+ ) float min = MAXNUM; int u = v; for ( int j = 0; j n; j+ ) if ( !Sj & distj min ) u = j; min = distj; Su = 1; /將頂點(diǎn)u加入集合S for ( int w = 0; w n; w+ ) /修改 if ( !Sw & Edgeuw MAXNUM &

31、 distu + Edgeuw distw ) /頂點(diǎn)w未加入S, 且通過u可以縮短路徑 distw = distu + Edgeuw; pathw = u; /修改到w的最短路徑 第85頁/共116頁例子 按Dijkstra算法計算從頂點(diǎn)A到其他各頂點(diǎn)的最短路徑和最短路徑長度。ABCDE101855222第86頁/共116頁答案： 10 A-B-D 15 A-B-D-C 17 A-B-D-E 17第87頁/共116頁所有頂點(diǎn)之間的最短路徑 問題：已知一個各邊權(quán)值均大于0的帶權(quán)有向圖，對每一對頂點(diǎn)vi vj，要求求出vi與vj之間的最短路徑和最短路徑長度。 算法思想： 如果利用一個二維數(shù)組存放

32、頂點(diǎn)之間的最短路徑值，那么這個數(shù)組的最初狀態(tài)就是圖的鄰接矩陣。即：Aij是vi與vj之間的最短路徑的長度。 如果存在一個k，且Aik+AkjAij，那么Aik+Akj應(yīng)該成為vi與vj之間的最短路徑的長度。 整個得Floyd算法的基本思想是：在原來的鄰接矩陣的基礎(chǔ)上，依次用V0,V1.Vn-1試圖在vi與vj之間插入，減小Aij的值。第88頁/共116頁例如：原始的從頂點(diǎn)例如：原始的從頂點(diǎn)v2到到v1的距離為邊的距離為邊上的權(quán)上的權(quán)值值5，當(dāng)加入中間頂點(diǎn)，當(dāng)加入中間頂點(diǎn)v0后，邊后，邊上的權(quán)上的權(quán)值之和值之和4小于原來邊小于原來邊上的權(quán)值，則以此新路徑上的權(quán)值，則以此新路徑的長度頂點(diǎn)的長度頂點(diǎn)

33、v2到到v1的距離，并修改相應(yīng)的矩的距離，并修改相應(yīng)的矩陣元素。陣元素。第89頁/共116頁弗洛伊德算法定義一個n階方陣序列：A(-1), A(0), A(n-1),其中：A(-1)ij=Edgeij；A(k)ij=minA(k-1)ij，A(k-1)ik+A(k-1)kj，k=0,1,n-1A(0)ij是從頂點(diǎn)vi到vj，中間頂點(diǎn)是v0的最短路徑長度， A(k)ij是從頂點(diǎn)vi到vj，中間頂點(diǎn)的序號不大于k的最短路徑的長度， A(n-1)ij是從頂點(diǎn)vi到vj的最短路徑長度。第90頁/共116頁Example of Floyd Algorithm第91頁/共116頁Example of Fl

34、oyd Algorithm第92頁/共116頁Example of Floyd Algorithm第93頁/共116頁Example of Floyd Algorithm第94頁/共116頁Example of Floyd Algorithm第95頁/共116頁void Graph:AllLengths(int n)/Edgenn是鄰接矩陣，aij是頂點(diǎn)i和j之間的最短路徑長度/pathij是相應(yīng)路徑上頂點(diǎn)j的前一頂點(diǎn)的頂點(diǎn)號 for(int i=0; in; i+) for(int j=0; jn; j+) aij=Edgeij;/矩陣a初始化 if(ij&aijMAXNUM)pat

35、hij=i;/有路徑 else pathij=0;/i到j(luò)無路徑 for(int k=0; kn; k+)/產(chǎn)生a(k)及相應(yīng)的path(k) for(i=0; in; i+) for(j=0; jn; j+) if(aik+akjaij) aij=aik+akj; pathij=pathkj; /縮短路徑長度，通過k到j(luò)第96頁/共116頁從A(3)可知，頂點(diǎn)1到頂點(diǎn)0的最短路徑長度為a10=11，在path(3)中對應(yīng)的最短路徑首先看path10=2，表示頂點(diǎn)0的前一個頂點(diǎn)是2，path12=3，表示頂點(diǎn)2的前一個頂點(diǎn)是3，path13=1，表示頂點(diǎn)3的前一個頂點(diǎn)是1，最后從頂點(diǎn)1到頂點(diǎn)3

36、的最短路徑為。算法復(fù)雜度為O(n3)第97頁/共116頁第98頁/共116頁第99頁/共116頁學(xué)生課程學(xué)習(xí)工程圖學(xué)生課程學(xué)習(xí)工程圖C8C3C5C4C9C6C7C1C2第100頁/共116頁第101頁/共116頁第102頁/共116頁C8C3C5C4C9C6C7C1C2第103頁/共116頁 第104頁/共116頁C0C1C2C3C4C5(a) 有向無環(huán)圖有向無環(huán)圖C2C5C1C0C3(b) 輸出頂點(diǎn)輸出頂點(diǎn)C4C1C2C5C3C4C0C2C5C1C3(c) 輸出頂點(diǎn)輸出頂點(diǎn)C0(d) 輸出頂點(diǎn)輸出頂點(diǎn)C3第105頁/共116頁C1C2C5(e) 輸出頂點(diǎn)輸出頂點(diǎn)C2C5C1(f) 輸出頂點(diǎn)輸出頂點(diǎn)C1C5(g) 輸出頂點(diǎn)輸出頂點(diǎn)C5(h) 拓?fù)渑判蛲瓿赏?/p>