數(shù)據(jù)結(jié)構(gòu) D數(shù)據(jù)結(jié)構(gòu)習題課：圖學習課件

畫出1個頂點、2個頂點、3個頂點、4個頂點和5個頂點的無向完全圖。試證明在n個頂點的無向完全圖中，邊的條數(shù)為n(n-1)/2?！咀C明】

在有n個頂點的無向完全圖中，每一個頂點都有一條邊與其它某一頂點相連，所以每一個頂點有n-1條邊與其他n-1個頂點相連，總計n個頂點有n(n-1)條邊。但在無向圖中，頂點i到頂點j與頂點j到頂點i是同一條邊，所以總共有n(n-1)/2條邊。1對于如圖所示的有向圖，試寫出：(1)從頂點②出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；(2)從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；2右圖是一個連通圖，請畫出(1)以頂點①為根的深度優(yōu)先生成樹；(2)如果有關(guān)節(jié)點，請找出所有的關(guān)節(jié)點。(3)如果想把該連通圖變成重連通圖，至少在圖中加幾條邊？關(guān)節(jié)點為①,②,③,⑦,⑧(3)至少加四條邊(1,10),(3,4),(4,5),(5,6)。從③的子孫結(jié)點⑩到③的祖先結(jié)點①引一條邊，從②的子孫結(jié)點④到根①的另一分支③引一條邊,并將⑦的子孫結(jié)點⑤、⑥與結(jié)點④連結(jié)起來，可使其變?yōu)橹剡B通圖。3求最小生成樹4給出所有的拓撲序列1、3、2、4、5、61、3、2、5、4、65求單源最短路徑如右圖所示，設源點為A，求源點到其它各個頂點的最短路徑stepSwD:BD:CD:DD:ED:FD:G0{A}-123∞∞∞1{AB}B232∞∞2{ABC}C32∞∞3{ABCE}E3∞34{ABCED}D635{ABCEDG}G66{ABCEDGF}F123263結(jié)果如下表所示6在如圖所示的各無向圖中：

(1)找出所有的簡單環(huán)。

(2)哪些圖是連通圖?對非連通圖給出其連通分量。

(3)哪些圖是自由樹(或森林)?(1)所有的簡單環(huán)：(同一個環(huán)可以任一頂點作為起點)

(a)1231

(b)無

(c)12431

(d)無(3)自由樹(森林)：自由樹是指沒有確定根的樹，無回路的連通圖稱為自由樹：

(a)不是自由樹，因為有回路。

(b)是自由森林，其兩個連通分量為兩棵自由樹。

(c)不是自由樹。(d)是自由樹。(2)(a)、(c)、(d)是連通圖，

(b)不是連通圖，因為從1到2沒有路徑。具體連通分量為：7在右圖所示的有向圖中：

(1)該圖是強連通的嗎?若不是，則給出其強連通分量。

(2)請給出所有的簡單路徑及有向環(huán)。

(3)請給出每個頂點的度，入度和出度。

(4)請給出其鄰接表、鄰接矩陣及逆鄰接表。(3)每個頂點的度、入度和出度：

D(v1)=3

ID(v1)=1

OD(v1)=2

D(v2)=2

ID(v2)=1

OD(v2)=1

D(v3)=3

ID(v3)=2

OD(v3)=1

D(v4)=2

ID(v4)=1

OD(v4)=1(1)該圖是強連通的，所謂強連通是指有向圖中任意頂點都存在到其他各頂點的路徑。(2)簡單路徑是指在一條路徑上只有起點和終點可以相同的路徑：

有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向環(huán),有向環(huán)如下：

v1v2v3v1、v1v4v3v1(這兩個有向環(huán)可以任一頂點作為起點和終點)8(4)鄰接表：

vertexfirstedge

next

逆鄰接表鄰接矩陣:

0123v113∧v22∧v30∧v42∧0123v12∧v203∧v31∧v40∧鄰接表0101

0010

1000

0010假設圖的頂點是A,B...，請根據(jù)下述的鄰接矩陣畫出相應的無向圖或有向圖。011000001000010

10001

010100111

1011

110111109(b)(a)假設一棵完全二叉樹包括A,B,C...等七個結(jié)點，寫出其鄰接表和鄰接矩陣。鄰接矩陣如下：0110000

1001100

1000011

0100000

0100000

0010000

00100000123456A12∧B034∧C056∧D1∧E1∧F2∧G2∧

鄰接表如下：10對n個頂點的無向圖和有向圖，采用鄰接矩陣和鄰接表表示時，如何判別下列有關(guān)問題?

(1)圖中有多少條邊?

(2)任意兩個頂點i和j是否有邊相連?

(3)任意一個頂點的度是多少?(3)對于無向圖，任一頂點i的度為第i行中非零元素的個數(shù)。

對于有向圖，任一頂點i的入度為第i列中非零元素的個數(shù)，出度為第i行中非零元素的個數(shù)，度為入度出度之和。對于n個頂點的無向圖和有向圖，用鄰接矩陣表示時：

(1)設m為矩陣中非零元素的個數(shù)

無向圖的邊數(shù)=m/2

有向圖的邊數(shù)=m(2)無論是有向圖還是無向圖，在矩陣中第i行,第j列的元素若為非零值，則該兩頂點有邊相連。11當用鄰接表表示時：

(1)對于無向圖，圖中的邊數(shù)=邊表中結(jié)點總數(shù)的一半。

對于有向圖，圖中的邊數(shù)=邊表中結(jié)點總數(shù)。

(2)對于無向圖，任意兩頂點間是否有邊相連，可看其中一個頂點的鄰接表，若表中的adjvex域有另一頂點位置的結(jié)點，則表示有邊相連。

對于有向圖，則表示有出邊相連。(3)對于無向圖，任意一個頂點的度則由該頂點的邊表中結(jié)點的個數(shù)來決。

對于有向圖，任意一個頂點的出度由該頂點的邊表中結(jié)點的個數(shù)來決定，入度則需遍歷各頂點的邊表。

(用逆鄰接表可容易地得到其入度。)

n個頂點的連通圖至少有幾條邊?強連通圖呢?DFS和BFS遍歷各采用什么樣的數(shù)據(jù)結(jié)構(gòu)來暫存頂點?當要求連通圖的生成樹的高度最小，應采用何種遍歷?n個頂點的連通圖至少有n-1條邊，強連通圖至少有2(n-1)條邊。DFS遍歷采用棧來暫存頂點。BFS采用隊列來暫存頂點。當要求連通圖的生成樹的高度最小時，應采用BFS遍歷。1213畫出以頂點v1為初始源點遍歷下圖所示的有向圖所得到的DFS和BFS生成森林。

14對右圖所示的有向圖，試利用Dijkstra算法求出從源點1到其它各頂點的最短路徑，并寫出執(zhí)行算法過程中擴充紅點集的每次循環(huán)狀態(tài)從源點1到各點的路徑如下：

1到2：1321到3：1

1到4：1364

1到5：13251到6：136循環(huán)紅點集KD[i]P[i]123456123456初始化{1}-02015∞∞∞-111-1-1-11{1,3}

301915∞∞25-131-1-132{1,3,2}201915∞2925-131-1233{1,3,2,6}601915292925-1316234{1,3,2,6,4}401915292925-1316235{1,3,2,6,4,5}501915292925-1316236--------------15什么樣的DAG的拓撲序列是唯一的?

請以V0為源點，給出用DFS搜索下圖得到的逆拓撲序列。確定了排序的源點，DAG圖中無前趨頂點只有一個且從該點到終點只有一條路徑時，它的拓撲序列才是唯一的。

逆拓撲序列是：V4V2V1V0V1V6V51617利用拓撲排序算法的思想寫一算法判別有向圖中是否存在有向環(huán)，當有向環(huán)存在時，輸出構(gòu)成環(huán)的頂點。

typedef

enum{FALSE，TRUE}Boolean；//FALSE為0，TRUE為1

Booleanvisited[MaxVertexNum]；//訪問標志向量是全局量

inti；

for(i=0;i<G->n;i++)

visited[i]=FALSE；//標志向量初始化

以鄰接表作為存儲結(jié)構(gòu)

18voidNonSuccFirstTopSort(ALGraphG){

//優(yōu)先輸出無后繼的頂點,此處用逆鄰接表存儲

int

outdegree[MaxVertexNum];//出度向量，此處MaxVertexNum>=G.n

SeqStackS;//將棧中data向量的基類型改為int

int

i,j,count=0;//count對輸出的頂點數(shù)目計數(shù)，初值為0

EdgeNode*p;

for(i=0;i<G.n;i++)

{outdegree[i]=0;

visited[i]=FALSE；//標志向量初始化

}

for(i=0;i<G.n;i++)

for(p=G.adjlist[i].firstedge;p;p=p->next)//掃描i的入邊表

outdegree[p->adjvex]++;//設p->adjvex=j，則將<j,i>的起點j出度加1

InitStack(&s);

for(i=0;i<G.n;i++)

if(outdegree[i]==0)

Push(&S,i);//出度為0的頂點i入棧

while(!StackEmpty(S))//棧非空，有出度為0的頂點

{i=pop(&s);visited[i]=TRUE;

count++;//頂點計數(shù)加1

for(p=G.adjlist[i].firstedge;p;p=p->next)//修改以i為弧頭的弧的弧尾頂點的出度

{j=p->adjvex;

outdegree[j]--;

if(outdegree[j]==0)//將新生成的出度為0的頂點入棧

Push(&S,j);//出度為0的頂點j入棧

}//endoffor

}//endofwhile

if(count<G.n)//輸出頂點數(shù)小于n

{printf("G中存在有向環(huán)，排序失敗!");

for(i=0;i<G.n;i++)

if(visited[i]==FALSE)

printf("%c",G.adjlist[i].vertex);

}

elseprintf("G中無有向環(huán)!");}

typedef

enum{FALSE，TRUE}Boolean；//FALSE為0，TRUE為1

Booleanvisited[MaxVertexNum]；//訪問標志向量是全局量

voidDFSTraverse(ALGraph*G)

{//對以鄰接表表示的有向圖G，求所有根

int

i,j；

for(j=0;j<G->