1、 1 / 10 課程設計題目和內容 一.圖的基本操作的實現(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)如果選用的存儲結構是鄰接矩

2、陣,則用鄰接矩陣的信息生成圖G的鄰接表,即復制圖G,然再執(zhí)行操作 (2)；反之亦然。 二.程序中所采用的數(shù)據(jù)結構及存儲結構的說明1鄰接矩陣： 適用于圖中邊或弧的數(shù)目比較多的情況，壓縮存儲方式結構。鄰接矩陣是表示頂點之間相鄰關系的矩陣。若圖有n個頂點，則鄰接矩陣是一個n*n階的方陣，結構唯一。鄰接矩陣A的元素規(guī)定為： 用鄰接矩陣存儲網(wǎng)時只需要將矩陣中的1換為相應的權值，將0用一個不可能存在的權值代替即可。當圖用鄰接矩陣表示后圖的某些操作的實現(xiàn)是很方便的，如求某一頂點v i的第一鄰接點，只需在第i行找到第1個非零元即可。若求某一頂點v 2 / 10 i的度，對于無向圖來說，只須統(tǒng)計第i行的非零元個

3、數(shù)或第i列的非零元個數(shù)（無向圖的鄰接矩陣是對稱的）；當圖中頂點數(shù)確定，插入一條邊（v i,v j）只須將矩陣中第i行j列和第j行i列的元素分別改為1或相應的權值；插入一條弧i,v j>只須將矩陣中第i行j列的元素改為1或相應的權值即可。 2鄰接表： 一種鏈式存儲結構 在鄰接表中對圖的每個頂點建立一個單鏈表，第i個單鏈表中包含第i個頂點的所有鄰接點，每一個單鏈表包含兩種結點，頭結點和表結點。 在圖的鄰接表中，可以比較方便地查找一個頂點的邊（出邊）或鄰接點（出邊鄰接點），這只要首先從表頭向量中取出對應的表頭指針，然后從表頭指針出發(fā)進行查找即可。鄰接表則是以一數(shù)組(結構體數(shù)組)的元素作為頭指針

4、,后面鏈接和它相鄰的結點. 3鄰接矩陣表示法與鄰接表表示法的比較：1）鄰接矩陣是唯一的，鄰接表不唯一； 2）存儲稀疏圖用鄰接表，存儲稠密圖用鄰接矩陣；3）求無向圖頂點的度都容易，求有向圖頂點的度鄰接矩陣較方便； 4）判斷是否是圖中的邊，鄰接矩陣容易，鄰接表最壞時間為O(n)； 5）求邊數(shù)e，鄰接矩陣耗時為O(n2)，與e無關，鄰接表的耗時 三.算法的設計思想 1鄰接矩陣存儲圖的基本思路： 圖用鄰接矩陣表示后圖的某些操作的實現(xiàn)是很方便的，如求某一頂點v 3 / 10 i的第一鄰接點，只需在第i行找到第1個非零元即可。若求某一頂點v i的度，對于無向圖來說，只須統(tǒng)計第i行的非零元個數(shù)或第i列的非零

5、元個數(shù)（無向圖的鄰接矩陣是對稱的）；對于有向圖來說，第i行的非零元個數(shù)為該頂點的出度，第i列的非零元個數(shù)為該頂點的入度，兩者相加為該頂點的度。當圖中頂點數(shù)確定，插入一條邊（v i,v j）只須將矩陣中第i行j列和第j行i列的元素分別改為1或相應的權值；插入一條弧i,v j>只須將矩陣中第i行j列的元素改為1或相應的權值即可。 2鄰接表存儲圖的基本思路： 若無向圖中有n個頂點e條邊，則鄰接表需要n個頭結點和2e個表結點。在邊稀疏的情況下，采用鄰接表比采用鄰接矩陣節(jié)省存儲空間。 在無向圖的鄰接表中，頂點v i的度恰好為第i個鏈表中的表結點數(shù)。 若有向圖中有n個頂點e條弧，則鄰接表需要n個頭結

6、點和e個表結點。在有向圖的鄰接表中，第i個鏈表中的結點數(shù)為頂點v i的出度。為求頂點v i的入度，需要遍歷整個鄰接表，在所有鏈表中其鄰接點域的值為i的結點個數(shù)為頂點v i的入度。在鄰接表中，容易找到任意一頂點的第一鄰接點和下一個鄰接點，但要判斷任意兩個頂點v i和v j之間是否有邊相連，則須搜索第i或j個鏈表，因此，不及鄰接矩陣方便。3深度優(yōu)先遍歷圖的基本思路是： 4 / 10 （1）訪問圖中的指定起始點v 0； （2）從v 0出發(fā)，訪問一個與v 0鄰接的頂點w 1后，再從w 1出發(fā)，訪問與w 1鄰接的且未訪問的頂點w 2。然后從w 2出發(fā)，重復上述過程，直到找不到未被訪問的頂點為止。 （3）

7、回退到尚有未被訪問過的鄰接點的頂點，從該頂點出發(fā)，重復上面的步驟，直到所有被訪問過的頂點的鄰接點都已訪問為止。 4xx優(yōu)先遍歷是圖的實現(xiàn)思路是： （1）訪問圖中的指定起始點v 0； （2）從v 0出發(fā)，依次訪問v 0的未被訪問的鄰接點w 1,w 2,w 3,w 5 / 10 n。然后依次訪問w 1,w 2,w 3,w n的未被訪問的鄰接點。 （3）重復上面的第二步，直到所有頂點的鄰接點都已訪問為止。 四.程序清單 #include<stdio.h> #include<stdlib.h> #define NULL 0 #define maxsize 10 typedef

8、struct nodeint data; struct node *next; dnode; typedef struct int vex; dnode *first; Node; typedef structNode arrymaxsize; int num; graph; 6 / 10 int visitmaxsize; graph creat()/創(chuàng)建鄰接表graph a; dnode *p; int i,x,y,e; printf(輸入頂點數(shù)和邊數(shù)（以空格分割）： );scanf(%d%d,&a.num,&e); for(i=1;i<=a.num;i+)a.arr

9、yi.first=NULL; a.arryi.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.arryx.first; a.arryx.first=p; p=(dnode*)malloc(sizeof(dnode); p->data=x; p->next=a.arryy.first ; a.arryy.first=p;return a;void copy(grap

10、h b,int vmaxsize)/鄰接矩陣與鄰接表轉換int i,j; dnode *p; for(i=1;i<=b.num;i+) for(j=1;j<=b.num;j+) 7 / 10 vij=0; for(i=1;i<=b.num;i+)p=(dnode*)malloc(sizeof(dnode); p=b.arryi.first; while(p)vip->data=1; p=p->next ; for(i=1;i<=b.num;i+)for(j=1;j<=b.num;j+) printf(%d,vij); printf(n); void v

11、exdu(graph a)/求度數(shù)dnode *p; int i,count; for(i=1;i<=a.num;i+)p=a.arryi.first; count=0; while(p)count+; p=p->next ;printf(%d的度數(shù): %dn,a.arryi.vex,count); void clr()int i; for(i=1;i<=maxsize;i+) visiti=0;void dfs(graph a,int v)dnode *p; if(a.arryv.vex!=0) printf(%d,a.arryv.vex); visitv=1; 8 / 1

12、0 p=a.arryv.first ; while(p)if(!visitp->data) dfs(a,p->data ); p=p->next; void find1(graph a)int v; clr(); printf(輸入開始搜索節(jié)點： ); scanf(%d,&v); dfs(a,v); printf(n);void find2(graph a)int x,i; dnode *p,*q; clr(); printf(輸入要查找刪除的點： scanf(%d,&x); for(i=1;i<=a.num;i+) if(a.arryi.vex=x)b

13、reak; if(i>a.num)printf(沒找到！n); return; ); elseprintf(找到！n); 9 / 10 q=p=a.arryi.first ; a.arryi.vex=0; 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);void find3(graph a)int i; clr(); dfs(a,1); for(i=1;i<a.num;i+) if(v