圖的設計作業(yè)

課程設計題目和內(nèi)容

一.圖的基本操作的實現(xiàn)

1)自選存儲結構，輸入含n個頂點(用字符表示頂點)和

e條邊的圖G；

(2)求每個頂點的度，輸出結果；

(3)指定任意頂點x為初始頂點，對圖G作DFS遍歷，輸

出DFS頂點序列(提示:使用一個棧實現(xiàn)DFS)；

(4)指定任意頂點x為初始頂點，對圖G作BFS遍歷，輸出

BFS頂點序列(提示:使用一個隊列實現(xiàn)BFS)；

(5)輸入頂點x,查找圖G:若存在含x的頂點，則刪除該結

點及與之相關連的邊，并作DFS遍歷(執(zhí)行操作3)；否則

輸出信息“無X”；

(6)判斷圖G是否是連通圖，輸出信息“YES”/“NO”；

(7)如果選用的存儲結構是鄰接矩陣，則用鄰接矩陣的信

息生成圖G的鄰接表，即復制圖G,然再執(zhí)行操作(2)；反

之亦然。

二.程序中所采用的數(shù)據(jù)結構及存儲結構的說明

1鄰接矩陣：適用于圖中邊或弧的

數(shù)目比較多的情況，壓縮存儲方式結構。

鄰接矩陣是表示頂點之間相鄰關系的矩陣。若圖有n個

頂點，則鄰接矩陣是一個n*n階的方陣，結構唯一。鄰

接矩陣A的元素規(guī)定為：用鄰接矩陣存儲網(wǎng)時只需要將

矩陣中的1換為相應的權值，將0用一個不可能存在的

權值代替即可。當圖用鄰接矩陣表示后圖的某些操作的

實現(xiàn)是很方便的，如求某一頂點Vi的第一鄰接點，只需

在第i行找到第1個非零元即可。若求某一頂點vi的度,

對于無向圖來說，只須統(tǒng)計第i行的非零元個數(shù)或第i

列的非零元個數(shù)（無向圖的鄰接矩陣是對稱的）；當圖

中頂點數(shù)確定，插入一條邊（V“Vj）只須將矩陣中第i

行j列和第j行i列的元素分別改為1或相應的權值；

插入一條弧i,V。只須將矩陣中第i行j列的元素改為1

或相應的權值即可。

2鄰接表：一種鏈式存儲結構

在鄰接表中對圖的每個頂點建立一個單鏈表，第i個單

鏈表中包含第i個頂點的所有鄰接點，每一個單鏈表包

含兩種結點，頭結點和表結點。

在圖的鄰接表中，可以比較方便地查找一個頂點的邊（出

邊）或鄰接點（出邊鄰接點），這只要首先從表頭向量

中取出對應的表頭指針，然后從表頭指針出發(fā)進行查找

即可。

鄰接表則是以一數(shù)組（結構體數(shù)組）的元素作為頭指針，

后面鏈接和它相鄰的結點.

3鄰接矩陣表示法與鄰接表表示法的

比較：

1）鄰接矩陣是唯一的，鄰接表不唯一；

2）存儲稀疏圖用鄰接表，存儲稠密圖用鄰接矩陣；

3）求無向圖頂點的度都容易，求有向圖頂點的度鄰

接矩陣較方便；

4）判斷是否是圖中的邊，鄰接矩陣容易，鄰接表最

壞時間為0（n）；

5）求邊數(shù)e,鄰接矩陣耗時為0（rT2）,與e無關，

鄰接表的耗時

三.算法的設計思想

1鄰接矩陣存儲圖的基本思路：

圖用鄰接矩陣表示后圖的某些操作的實現(xiàn)是很方便的，

如求某一頂點V1的第一鄰接點，只需在第i行找到第1

個非零元即可。若求某一頂點X的度，對于無向圖來說,

只須統(tǒng)計第i行的非零元個數(shù)或第i列的非零元個數(shù)（無

向圖的鄰接矩陣是對稱的）；對于有向圖來說，第i行

的非零元個數(shù)為該頂點的出度，第i列的非零元個數(shù)為

該頂點的入度，兩者相加為該頂點的度。當圖中頂點數(shù)

確定，插入一條邊（Vi,Vj）只須將矩陣中第i行j列和

第j行i列的元素分別改為1或相應的權值；插入一條

弧i,V。只須將矩陣中第i行j列的元素改為1或相應的

權值即可。

2鄰接表存儲圖的基本思路：

若無向圖中有n個頂點e條邊，則鄰接表需要n個頭結

點和2e個表結點。在邊稀疏的情況下，采用鄰接表比采

用鄰接矩陣節(jié)省存儲空間。

在無向圖的鄰接表中，頂點Vi的度恰好為第i個鏈表中

的表結點數(shù)。

若有向圖中有n個頂點e條弧，則鄰接表需要n個頭結

點和e個表結點。在有向圖的鄰接表中，第i個鏈表中

的結點數(shù)為頂點Vi的出度。為求頂點V1的入度，需要遍

歷整個鄰接表，在所有鏈表中其鄰接點域的值為i的結

點個數(shù)為頂點口的入度。在鄰接表中，容易找到任意一

頂點的第一鄰接點和下一個鄰接點，但要判斷任意兩個

頂點Vi和Vj之間是否有邊相連，則須搜索第i或j個鏈

表，因此，不及鄰接矩陣方便。

3深度優(yōu)先遍歷圖的基本思路是：

(1)訪問圖中的指定起始點Vo；

(2)從Vo出發(fā)，訪問一個與Vo鄰接的頂點叫

后，再從W1出發(fā)，訪問與W1鄰接的且未訪問的頂點W2。

然后從W2出發(fā)，重復上述過程，直到找不到未被訪問的

頂點為止。

(3)回退到尚有未被訪問過的鄰接點的頂點，

從該頂點出發(fā)，重復上面的步驟，直到所有被

訪問過的頂點的鄰接點都已訪問為止。

4廣度優(yōu)先遍歷是圖的實現(xiàn)思路是：

(1)訪問圖中的指定起始點Vo；

(2)從Vo出發(fā)，依次訪問Vo的未被訪問的鄰

接點W),w2,W3,,,,,Wno然后依次訪問Wl,W2,W3,,,,,Wn的未被

訪問的鄰接點。

(3)重復上面的第二步，直到所有頂點的鄰

接點都已訪問為止。

四.程序清單

#include<stdio.h>

#include<stdlib.h>

#defineNULL0

#definemaxsize10

typedefstructnode

{

intdata;

structnode*next;

}dnode;

typedefstruct

{intvex;

dnode*first;

}Node;

typedefstruct

{

Nodearry[maxsize];

intnum;

}graph;

intvisit[maxsize];

graphcreat()〃創(chuàng)建鄰接表

grapha;

dnode*p;

inti,x,y,e;

printf("輸入頂點數(shù)和邊數(shù)(以空格分割)：")；

scanf("%d%d",&a.num,&e);

for(i=1;i<=a.num;i++)

{

a.arry[i].first=NULL;

a.arry[i].vex=i;

)

for(i=1;i<=e;i++)

{

printf("輸入第%d個頂點的邊二i);

scanf("%d%d",&x,&y);

p=(dnode*)malloc(sizeof(dnode));

p->data=y;

p->next=a.arry[x].first;

a.arry[x].first=p;

p=(dnode*)malloc(sizeof(dnode));

p->data=x;

p->next=a.arry[y].first;

a.arry[y].first=p;

returna;

voidcopy(graphb,intv[][maxsize])〃令B接矩陣與令B接表

轉(zhuǎn)換

{

inti,j;

dnode*p;

for(i=1;i<=b.num;i++)

for(j=1;j<=b.num;j++)

v[i]U]=O;

for(i=1;i<=b.num;i++)

(

p=(dnode*)malloc(sizeof(dnode));

p=b.arry[i].first;

while(p)

v[i][p->data]=1;

p=p->next;

for(i=1;i<=b.num;i++)

for(j=1;j<=b.num;j++)

printf("%d",v[i][j]);

printf("\n")；

)

)

voidvexdu(grapha)//求度數(shù)

{

dnode*p;

inti,count;

for(i=1;i<=a.num;i++)

(

p=a.arry[i].first;

count=0;

while(p)

{

count++;

p=p->next;

)

printf("%d的度數(shù):％d\rT,a.arry[i].vex,count);

voidclr()

inti;

for(i=1;i<=maxsize;i++)

visit[i]=0;

)

voiddfs(grapha,intv)

{

dnode*p;

if(a.arry[v].vex!=O)

printf("%d",a.arry[v].vex);

visit[v]=1;

p=a.arry[v].first;

while(p)

if(!visit[p->data])

dfs(a,p->data);

p=p->next;

voidfindl(grapha)

intv;

clr();

printf("輸入開始搜索節(jié)點：");

scanf("%d",&v);

dfs(a,v);

printf("\n");

)

voidfind2(grapha)

{

intx,i;

dnode*p,*q;

dr()；

printf("輸入要查找刪除的點：")；

scanf("%d",&x);

for(i=1;i<=a.num;i++)

if(a.arry[i].vex==x)break;

if(i>a.num)

printf("沒找到！\rT);

return;

)

else

{

printf("找至U!\n");

q=p=a.arry[i].first;

a.arry[i].vex=O;

if(p->data==x)p=p->next;

else

while(p)

(

if(p->data==x)

{

q->next=p->next;

break;

)

q=p;

p=p->next;

)

)

dfs(a,x);

printf("\n");

voidfind3(grapha)

inti;

clr();

dfs(a,1);

for(i=1;i<a.num;i++)

if(visit[i]==O)

{

printf("此圖不是連通的。\n")；

return;

)

printf("此圖不是連通的。\n");

return;

)

voidfind4(grapha)

(

intv[maxsize][maxsize];

copy(a,v);

voidmain()

graphh;

h=creat();

vexdu(h);

find1(h);

find2(h);

find3(h);

find4(h);

}

五.運行結果

6*C:\DOCUIEITSAUDSETTIIGSXADIINISTRATOR.IICROSOF-ABlFF7\^ffi\Debug\fe...

以

敢

好

入

頂V

j44

邊

□點L

入

T頂12

度

點

邊

個

入

頂22

邊

點

入

個

頂32

度

點

邊

入

頂