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

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