圖的基本概念圖的存儲結(jié)構(gòu)圖的遍歷圖的連通性問題最小生成樹最短路徑

活動網(wǎng)絡(luò)圖圖的基本概念圖定義

圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)其中

V={x|x

某個數(shù)據(jù)對象}

是頂點(diǎn)的有窮非空集合；

E1={(x,y)|x,yV}或E2={<x,y>|x,yV&&Path(x,y)}

其中，E1是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合，此時的圖稱為無向圖。

E2表示從x到y(tǒng)的一條弧，且稱x為弧尾，y為弧頭，這樣的圖稱為有向圖。例G1=<V1,E1>V1={v1,v2,v3,v4,v5}E1={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}

V5V1

V2

V4

V3無序?qū)?vi,vj)：用連接頂點(diǎn)vi、vj的線段表示，稱為無向邊；無向圖：在圖G中，若所有邊是無向邊，則稱G為無向圖例G2=<V2,E2>V2={v1,v2,v3,v4}E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}

V1

V2

V3

V4有序?qū)?lt;vi,vj>:以vi為起點(diǎn)(弧尾),以vj為終點(diǎn)(弧頭)的有向線段表示,稱為有向邊或弧有向圖：在圖G中，若所有邊是有向邊(弧)，則稱G為有向圖；混和圖：在圖G中，即有無向邊也有有向邊，則稱G為混合圖例1交通圖（公路、鐵路）頂點(diǎn)：地點(diǎn)邊：連接地點(diǎn)的公路交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；例2電路圖頂點(diǎn)：元件邊：連接元件之間的線路例3通訊線路圖頂點(diǎn)：地點(diǎn)邊：地點(diǎn)間的連線例4各種流程圖如產(chǎn)品的生產(chǎn)流程圖頂點(diǎn)：工序邊：各道工序之間的順序關(guān)系圖的應(yīng)用舉例有向圖與無向圖

在有向圖中，頂點(diǎn)對 <x,y>是有序的。在無向圖中，頂點(diǎn)對(x,y)是無序的。完全圖

若有n個頂點(diǎn)的無向圖有

n(n-1)/2

條邊,

則此圖為無向完全圖。有n個頂點(diǎn)的有向圖有n(n-1)

條邊,則此圖為有向完全圖。00001111222265433圖的基本術(shù)語

鄰接頂點(diǎn)

如果(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點(diǎn)。（鄰接點(diǎn)：邊的兩個頂點(diǎn)）關(guān)聯(lián)邊：若邊e=(v,u),則稱邊e和頂點(diǎn)v、u相關(guān)聯(lián)子圖

設(shè)有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。權(quán)

某些圖的邊具有與它相關(guān)的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)0123子圖0130123023頂點(diǎn)的度

一個頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。頂點(diǎn)v的入度是以

v為終點(diǎn)的有向邊的條數(shù),記作

ID(v);

頂點(diǎn)v的出度是以

v為始點(diǎn)的有向邊的條數(shù),記作OD(v)頂點(diǎn)的出度:以頂點(diǎn)v為弧尾的弧的數(shù)目;頂點(diǎn)的入度:以頂點(diǎn)v為弧頭的弧的數(shù)目。ABECF有向圖頂點(diǎn)的度(TD)=出度(OD)+入度(ID)TD(B)=OD(B)+ID(B)=3例如:路徑

在圖G＝(V,E)中,若從頂點(diǎn)vi出發(fā),沿一些邊經(jīng)過一些頂點(diǎn)vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vivp1vp2...vpm

vj)為從頂點(diǎn)vi

到頂點(diǎn)vj

的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。

V5V1

V2

V4

V3

V1

V2

V3

V4在圖1中，V1,V2,V3,V4是V1到V4的路徑;V1,V2,V3,V4,V1是回路;

在圖2中，V1,V3,V4是V1到V4的路徑；V1,V3,V4,V1是回路；路徑長度

非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑

若路徑上各頂點(diǎn)

v1,v2,...,vm

均不互相重復(fù),則稱這樣的路徑為簡單路徑。簡單回路

若路徑上第一個頂點(diǎn)v1與最后一個頂點(diǎn)vm

重合,則稱這樣的路徑為回路或環(huán)。V2,V3,V5是簡單路徑,V2,V3,V5,V2,V3不是簡單路徑

V2,V3,V5,V2是簡單回路.V1,V2,V3,V4是V1到V4的路徑,路徑長度為3;V1,V2是V1到V2的路徑,路徑長度為1.

V5V1

V2

V4

V3ABECF如:從A到F長度為3的路徑{A,B,C,F}連通圖與連通分量

在無向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對頂點(diǎn)都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強(qiáng)連通圖與強(qiáng)連通分量

在有向圖中,

若對于每一對頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。無向圖,若圖中任意兩個頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BACDFEBACDFE有向圖,若任意兩個頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。否則，其各個強(qiáng)連通子圖稱作它的強(qiáng)連通分量。ABECFAEBCF生成樹:假設(shè)一個連通圖有n個頂點(diǎn)和e條邊，其中n-1條邊和n個頂點(diǎn)構(gòu)成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。在極小連通子圖中增加一條邊，則一定有環(huán)。在極小連通子圖中去掉一條邊，則成為非連通圖。若T是G的生成樹當(dāng)且僅當(dāng)T滿足如下條件:T是G的連通子圖

T包含G的所有頂點(diǎn)

T中無回路(n個頂點(diǎn),有且僅有n-1條邊)BACDFEBACDFE如果一個有向圖恰有一個頂點(diǎn)的入度為0,其余頂點(diǎn)的入度為1,則是一棵有向樹.一個有向圖的生成森林由若干棵有向樹組成,含有圖中全部頂點(diǎn),但只有足以構(gòu)成若干棵不相交的有向樹的弧.BACDFEBACDFE2圖的存儲結(jié)構(gòu)數(shù)組表示法鄰接表十字鏈表鄰接多重表

圖是多對多的結(jié)構(gòu)，比線性結(jié)構(gòu)、樹結(jié)構(gòu)復(fù)雜，所以其存儲結(jié)構(gòu)也要復(fù)雜些。與線性結(jié)構(gòu)、樹結(jié)構(gòu)一樣，圖的存儲結(jié)構(gòu)至少要保存兩類信息：

1)頂點(diǎn)的信息

2)頂點(diǎn)間的關(guān)系頂點(diǎn)的編號

為了使圖的存儲結(jié)構(gòu)與圖一一對應(yīng)，在討論圖的存儲結(jié)構(gòu)時，首先要給圖的所有頂點(diǎn)編號。本課程介紹四類圖的存儲結(jié)構(gòu)

二維數(shù)組(矩陣)表示法,鄰接表(鄰接表,逆鄰接表),

十字鏈表和鄰接多重表表示法等.

設(shè)

G=<V,E>是圖,V={v1,v2,v3,…vn},設(shè)頂點(diǎn)的下標(biāo)為它的編號在圖的鄰接矩陣表示中，有一個記錄各個頂點(diǎn)信息的頂點(diǎn)表，還有一個表示各個頂點(diǎn)之間關(guān)系的鄰接矩陣。設(shè)圖

A=(V,E)是一個有

n個頂點(diǎn)的圖,圖的鄰接矩陣是一個二維數(shù)組A.edge[n][n]，定義(滿足如下條件的n階矩陣)：2.1鄰接矩陣(AdjacencyMatrix)(二維數(shù)組表示法）無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。011000000001000

V5V1

V2

V4

V301010010101011010001100

V1

V2

V3

V4無向圖數(shù)組表示法特點(diǎn)1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；2）頂點(diǎn)v的度：在無向圖中等于二維數(shù)組對應(yīng)行（或列）中1的個數(shù)；在有向圖中,統(tǒng)計第i行1的個數(shù)可得頂點(diǎn)i的出度，統(tǒng)計第j列1的個數(shù)可得頂點(diǎn)j的入度。3）判斷兩頂點(diǎn)v、u是否為鄰接點(diǎn)：只需判二維數(shù)組對應(yīng)分量是否為1；無向圖數(shù)組表示法特點(diǎn)4）頂點(diǎn)不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦值1或清0；5）設(shè)存儲頂點(diǎn)的一維數(shù)組大小為n(圖的頂點(diǎn)數(shù)n),G占用存儲空間：n+n2；G占用存儲空間只與它的頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密的圖；網(wǎng)絡(luò)的鄰接矩陣186329543142頂點(diǎn)的存儲：用一維數(shù)組存儲（按編號順序）頂點(diǎn)間關(guān)系：用二維數(shù)組存儲圖的鄰接矩陣；012345m-1V1V2V3V4V5存儲頂點(diǎn)的一維數(shù)組存儲鄰接矩的二維數(shù)組010101010101234mm+1m+2m+3m+4用

鄰

接

矩

陣

表

示

的

結(jié)

構(gòu)

定

義typedef

struct

ArcCell{//弧的定義

VRType

adj;//VRType是頂點(diǎn)關(guān)系類型。

//對無權(quán)圖，用1或0表示相鄰否；

//對帶權(quán)圖，則為權(quán)值類型。

InfoType*info;//該弧相關(guān)信息的指針}ArcCell,

AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef

struct{//圖的定義

VertexType//頂點(diǎn)信息

vexs[MAX_VERTEX_NUM];

AdjMatrixarcs;//弧的信息

int

vexnum,arcnum;//頂點(diǎn)數(shù)，弧數(shù)

GraphKindkind;//圖的種類標(biāo)志

}MGraph;2.2鄰接表(AdjacencyList)鄰接表:是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。弧的結(jié)點(diǎn)結(jié)構(gòu)

adjvex;//該弧所指向的頂點(diǎn)的位置

nextarc;//指向下一條弧指針

info;

//該弧相關(guān)信息的指針adjvexnextedgeinfo頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)

datafirstedge

data;//頂點(diǎn)信息firstarc;//指向第一條依附該頂點(diǎn)的弧無向圖的鄰接表

同一個頂點(diǎn)發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點(diǎn)代表一條邊(邊結(jié)點(diǎn)),結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo)

adjvex

和指針

nextedgeABCDdatafirstedgeABCD0123adjvex

nextadge

adjvex

nextadge130210有向圖的鄰接表和逆鄰接表逆鄰接表(入邊表)datafirstedgeadjvex

nextarcABC012adjvex

nextarc鄰接表(出邊表)102datafirstedgeABC012adjvex

nextarc011可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧在有向圖的逆鄰接表中，對每個頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧BCA求出度容易求入度難求入度容易，求出度難有向圖的鄰接表和逆鄰接表網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表62BACD958datafirstedgeABCD0123adjvexcostnextarc1

53

62

83

21

9(出邊表)(頂點(diǎn)表)typedef

struct

ArcNode{

int

adjvex;//該弧所指向的頂點(diǎn)的位置

struct

ArcNode

*nextarc;

//指向下一條弧的指針

InfoType*info;//該弧相關(guān)信息的指針}ArcNode;adjvex

nextarcinfo弧的結(jié)點(diǎn)結(jié)構(gòu)圖的鄰接表存儲表示typedef

struct

VNode{

VertexTypedata;//頂點(diǎn)信息

ArcNode

*firstarc;

//指向第一條依附該頂點(diǎn)的弧

}VNode,AdjList[MAX_VERTEX_NUM];

datafirstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾頂點(diǎn)位置弧頭頂點(diǎn)位置弧的相關(guān)信息指向下一個有相同弧尾的結(jié)點(diǎn)指向下一個有相同弧頭的結(jié)點(diǎn)typedef

struct

ArcBox{//弧的結(jié)構(gòu)表示

int

tailvex,headvex;InfoType*info;

struct

ArcBox

*hlink,*tlink;}VexNode;tailvexheadvexhlinktlinkinfo2.3有向圖的十字鏈表存儲表示

頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù)指向該頂點(diǎn)的第一條入弧指向該頂點(diǎn)的第一條出弧typedef

struct

VexNode{//頂點(diǎn)的結(jié)構(gòu)表示

VertexTypedata;

ArcBox

*firstin,*firstout;}VexNode;datafirstinfirstouttypedef

struct{

VexNode

xlist[MAX_VERTEX_NUM];

//頂點(diǎn)結(jié)點(diǎn)(表頭向量)

int

vexnum,arcnum;

//有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}OLGraph;有向圖的結(jié)構(gòu)表示(十字鏈表)ABCABC012∧02∧∧0121∧20∧∧2.4無向圖的鄰接多重表存儲表示typedef

struct

Ebox{

VisitIfmark;//訪問標(biāo)記

int

ivex,jvex;

//該邊依附的兩個頂點(diǎn)的位置

struct

EBox

*ilink,*jlink;//分別指向依附這兩個頂點(diǎn)的下一條邊

InfoType*info;//該邊信息指針}EBox;邊的結(jié)構(gòu)表示typedef

struct{//鄰接多重表

VexBox

adjmulist[MAX_VERTEX_NUM];

int

vexnum,edgenum;//無向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)

}AMLGraph;頂點(diǎn)的結(jié)構(gòu)表示typedef

struct

VexBox{

VertexTypedata;

EBox

*firstedge;//指向第一條依附該頂點(diǎn)的邊}VexBox;無向圖的結(jié)構(gòu)表示圖的遍歷從圖中某一頂點(diǎn)出發(fā)訪遍圖中所有的頂點(diǎn)，且使每個頂點(diǎn)僅被訪問一次，這一過程就叫做圖的遍歷(TraversingGraph)。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個頂點(diǎn)之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，可設(shè)置一個標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組

visited[]。輔助數(shù)組visited[]的初始狀態(tài)為0,在圖的遍歷過程中,一旦某一個頂點(diǎn)

i

被訪問,就立即讓visited[i]為1,防止它被多次訪問兩種圖的遍歷方法:深度優(yōu)先搜索

DFS(DepthFirstSearch)廣度優(yōu)先搜索

BFS(BreadthFirstSearch)

從圖中某個頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)，然后依次從V0的各個未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。一、深度優(yōu)先搜索遍歷圖(DFS)連通圖的深度優(yōu)先搜索遍歷SG1SG2SG3W1、W2和W3

均為V的鄰接點(diǎn)，SG1、SG2和SG3分別為含頂點(diǎn)W1、W2和W3

的子圖。訪問頂點(diǎn)V

;for(W1、W2、W3)

若該鄰接點(diǎn)W未被訪問，

則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。Vw1w3w2從上頁的圖解可見:1.從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;解決的辦法是:為每個頂點(diǎn)設(shè)立一個“訪問標(biāo)志visited[w]”;2.如何判別V的鄰接點(diǎn)是否被訪問？voidDFS(GraphG,intv){

//從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖Gvisited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);

//對v的尚未訪問的鄰接頂點(diǎn)w

//遞歸調(diào)用DFS}//DFS首先將圖中每個頂點(diǎn)的訪問標(biāo)志設(shè)為FALSE,之后搜索圖中每個頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先搜索遍歷voidDFSTraverse(GraphG,Status(*Visit)(intv)){

//對圖G作深度優(yōu)先遍歷

VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問標(biāo)志數(shù)組初始化

for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);

//對尚未訪問的頂點(diǎn)調(diào)用DFS}abchdkefgFFFFFFFFFTTTTTTTTTachdefkbgachfekdbg訪問標(biāo)志:訪問次序:例如:012345678412385670二、廣度優(yōu)先搜索遍歷圖(BFS)Vw1w8w3w7w6w2w5w4對連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑。其中，V->w1,V->w2,V->w8

的路徑長度為1;V->w7,V->w3,V->w5

的路徑長度為2;V->w6,V->w4

的路徑長度為3。w1Vw2w7w6w3w8w5w4從圖中的某個頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。若此時圖中尚有頂點(diǎn)未被訪問,則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。

voidBFSTraverse(GraphG,Status(*Visit)(intv)){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//初始化訪問標(biāo)志

InitQueue(Q);//置空的輔助隊列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){//v