數(shù)據(jù)結(jié)構(gòu)-使用C語言版-朱戰(zhàn)立叢書版本圖教學課件2

第9章圖圖的基本概念圖的存儲結(jié)構(gòu)主圖的實現(xiàn)知圖的遍歷識最小生成樹點最短路徑拓撲排序關鍵路徑9.1圖1.圖的基本概念圖是由頂點集合及頂點間的關系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。圖G的定義是:G=(V,E)其中,V={xx∈某個數(shù)據(jù)元素集合}E={(X,y)kx,y∈v或E={<x,y>kx,y∈ⅴ并且Path(x,y)}其中,(x,y)表示從x到y(tǒng)的一條雙向通路,即(x,y)是無方向的;Path(x,y)表示從x到y(tǒng)的一條單向通路,即Path(x,y)是有方向的。本課程只討論最基本的圖,不包括帶自身環(huán)的圖、多重圖。基本術語:(1)頂點和邊:圖中的結(jié)點一般稱作頂點,圖中的第個頂點記做v。兩個頂點v和v相關聯(lián)稱作頂點v和v之間有一條邊,圖中的第k條邊記做,e=(v2Y)或<v(2)有向圖和無向圖:在有向圖中,頂點對<x,y>是有序的,頂點對<x,y>稱為從頂點x到頂點y的一條有向邊,有向圖中的邊也稱作弧;在無向圖中,頂點對(x,y)是無序的,頂點對(x,y)稱為與頂點x和頂點y相關聯(lián)的一條邊。(3)完全圖:在有n個頂點的無向圖中,若有n(m-1)2條邊,即任意兩個頂點之間有且只有一條邊,則稱此圖為無向完全圖;在有n個頂點的有向圖中,若有m(n-1)條邊,即任意兩個頂點之間有且只有方向相反的兩條邊,則稱此圖為有向完全圖a)無向完全圖(b)無向圖(c)有向圖(d)有向圖(4)鄰接頂點:在無向圖G中,若(u,)是E(G)中的一條邊,則稱u和v互為鄰接頂點,并稱邊(u,v)依附于頂點u和v在有向圖G中,若<,>是E(G)中的一條邊,則稱頂點u鄰接到頂點,頂點v鄰接自頂點u,并稱邊<u,w>和頂點u和頂點v相關聯(lián)。(5)頂點的度:頂點v的度是與它相關聯(lián)的邊的條數(shù),記作TD(v)。頂點的度=入度+出度。(6)路徑:在圖G=(V,E)中,若從頂點v:出發(fā)有一組邊使可到達頂點",則稱頂點到頂點的頂點序列為從頂點到頂點y的路徑(7)權:有些圖的邊附帶有數(shù)據(jù)信息,這些附帶的數(shù)據(jù)信息稱為權。帶權的圖也稱作網(wǎng)絡或網(wǎng)。(8)路徑長度:對于不帶權的圖,一條路徑的路徑長度是指該路徑上的邊的條數(shù);對于帶權的圖,一條路徑的路徑長度是指該路徑上各個邊權值的總和。(9)子圖:設有圖G={V1E}和圖G2={V2E2},若V≥V2,且EE2,則稱圖G2是圖G1的子圖7616施工進度圖交通網(wǎng)絡圖(10)連通圖和強連通圖:在無向圖中,若從頂點v到頂點v點都是連通的,則稱該圖是連通累。如果圖中任意一對頂有路徑,則稱頂點v和頂點v是連通在有向圖中,若對于任意一對頂點v和頂點v1(V;)都存在路徑,則稱圖G是強連通圖(11)生成樹:一個連通圖的最小連通子圖稱作該圖的生成樹。有n個頂點的連通圖的生成樹有n個頂點和n-1條邊。生成樹一般是對無向圖來討論。(12)簡單路徑和回路:若路徑上各頂點v2…,n,互不重復,則稱這樣的路徑為簡單路徑;若路徑上第一個頂點v與最后一個頂點v重合,則稱這樣的路徑為回路或環(huán)2圖的抽象數(shù)據(jù)類型數(shù)據(jù)集合:由一組頂點集合{v和一組邊e}集合組成。當為帶權圖時每條邊上權w還構(gòu)成權集合{W,}操作集合:(1)初始化Initiate(,n)(2)插入頂點Insertvertex(G,vertex)(3)插入邊InsertEd(,v1,v2,weight)(4)刪除邊DeleteEdge(G,vl,v2)(5)刪除頂點DeleteVertex(G,vertex)(6)第一個鄰接頂點GetFirstvex(G,v)(7)下一個鄰接頂點GetNextvex(G,intv1l,v2(8)遍歷DepthFirstSearch(G)92圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)主要有鄰接矩陣和鄰接表兩種1.圖的鄰接矩陣存儲結(jié)構(gòu)假設圖G=(V,E)有n個頂點,即v={vp1…,”n1},E可用如下形式的矩陣A描述,對于A中的每一個元素an,滿足若(v;,v