數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-圖的遍歷和構(gòu)建.doc

摘 要圖（Graph）是一種復雜的非線性結(jié)構(gòu)。圖可以分為無向圖、有向圖。若將圖的每條邊都賦上一個權(quán)，則稱這種帶權(quán)圖網(wǎng)絡(luò)。在人工智能、工程、數(shù)學、物理、化學、計算機科學等領(lǐng)域中，圖結(jié)構(gòu)有著廣泛的應用。在圖結(jié)構(gòu)中，對結(jié)點（圖中常稱為頂點）的前趨和后繼個數(shù)都是不加以限制的，即結(jié)點之間的關(guān)系是任意的。圖中任意兩個結(jié)點之間都可能相關(guān)。圖有兩種常用的存儲表示方法：鄰接矩陣表示法和鄰接表表示法。在一個圖中，鄰接矩陣表示是唯一的，但鄰接表表示不唯一。在表示的過程中還可以實現(xiàn)圖的遍歷（深度優(yōu)先遍歷和廣度優(yōu)先遍歷）及求圖中頂點的度。當然對于圖的廣度優(yōu)先遍歷還利用了隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）來實現(xiàn)。這不僅讓我們鞏固了之前學的隊列的基本操作，還懂得了將算法相互融合和運用。目 錄第一章 課程設(shè)計目的3第二章 課程設(shè)計內(nèi)容和要求32.1課程設(shè)計內(nèi)容32.1.1圖的鄰接矩陣的建立與輸出32.1.2圖的鄰接表的建立與輸出32.1.3圖的遍歷的實現(xiàn)42.1.4 圖的頂點的度42.2 運行環(huán)境4第三章 課程設(shè)計分析43.1圖的存儲43.1.1 圖的鄰接矩陣存儲表示43.1.2 圖的鄰接表存儲表示53.2 圖的遍歷53.2.1 圖的深度優(yōu)先遍歷53.2.2 圖的廣度優(yōu)先遍歷63.3圖的頂點的度7第四章 算法（數(shù)據(jù)結(jié)構(gòu)）描述74.1 圖的存儲結(jié)構(gòu)的建立。74.1.1 定義鄰接矩陣的定義類型74.1.2定義鄰接表的邊結(jié)點類型以及鄰接表類型74.1.3初始化圖的鄰接矩陣84.1.4 初始化圖的鄰接表84.2 圖的遍歷84.2.1 深度優(yōu)先遍歷圖84.2.2 廣度優(yōu)先遍歷圖94.3 main函數(shù)94.4 圖的大致流程表10第五章 源代碼10第六章 測試結(jié)果20第七章 思想總結(jié)21第八章 參考文獻22第一章 課程設(shè)計目的本學期我們對數(shù)據(jù)結(jié)構(gòu)這門課程進行了學習。這門課程是一門實踐性非常強的課程，為了讓大家更好地理解與運用所學知識，提高動手能力，我們進行了此次課程設(shè)計。數(shù)據(jù)結(jié)構(gòu)是計算機軟件和計算機應用專業(yè)的核心課程之一，在眾多的計算機系統(tǒng)軟件和應用軟件中都要用到各種數(shù)據(jù)結(jié)構(gòu)。這次課程設(shè)計不但要求學習者掌握數(shù)據(jù)結(jié)構(gòu)中的各方面知識，還要求學習者具備一定的C語言基礎(chǔ)和編程能力。具體說來，這次課程設(shè)計主要有兩大方面目的：一是讓學習者通過學習掌握數(shù)據(jù)結(jié)構(gòu)中的知識。對于圖的存儲與遍歷這一課題來說，所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識主要有：圖的鄰接矩陣存儲、圖的鄰接表存儲、隊列的基本運算實現(xiàn)、鄰接矩陣的算法實現(xiàn)、鄰接表的算法實現(xiàn)、圖的廣度優(yōu)先遍歷算法實現(xiàn)、圖的深度優(yōu)先遍歷算法實現(xiàn)。二是通過學習鞏固并提高學習者的C語言知識，并初步了解Visual C+的知識，提高其編程能力與專業(yè)水平。第二章 課程設(shè)計內(nèi)容和要求2.1課程設(shè)計內(nèi)容該課題要求以鄰接矩陣和鄰接表的方式存儲圖，輸出鄰接矩陣和鄰接表，并要求實現(xiàn)圖的深度、廣度兩種遍歷及頂點的度。2.1.1圖的鄰接矩陣的建立與輸出 對任意輸入頂點數(shù)和邊數(shù)的圖，若對無向圖進行討論，根據(jù)鄰接矩陣的存儲結(jié)構(gòu)建立圖的鄰接矩陣并輸出。要求輸出的格式是矩陣形式，這樣便于直觀的了解。2.1.2圖的鄰接表的建立與輸出對任意給定的圖（頂點數(shù)和邊數(shù)可以宏定義），若對無向圖進行討論，根據(jù)鄰接表的存儲結(jié)構(gòu)建立圖的鄰接表并輸出。2.1.3圖的遍歷的實現(xiàn)圖的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對于廣度優(yōu)先遍歷應利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）來實現(xiàn)。首先建立一空隊列，從初始點出發(fā)進行訪問，當被訪問時入隊，訪問完出隊。并以隊列是否為空作為循環(huán)控制條件。對于深度優(yōu)先遍歷則采用遞歸算法來實現(xiàn)。當然，若存儲圖的表示不一樣，進行兩種遍歷的方式也不一樣。2.1.4 圖的頂點的度 在圖中，可以求頂點的度。在無向圖用鄰接矩陣表示，Vi頂點的度即是該矩陣第i行或第j列中非0元素的個數(shù)之和。若無向圖用鄰接表表示，頂點Vi的度則是第i個邊表中的結(jié)點個數(shù)。2.2 運行環(huán)境該程序的運行環(huán)境為Windows xp系統(tǒng)，Microsoft Visual C+6.0版本。第三章 課程設(shè)計分析3.1圖的存儲 圖的存儲表示方法很多，但常用的是：圖的矩陣表示和鄰接表表示。至于在遇到問題具體選擇哪一種表示法，主要取決于具體的應用和欲施加的操作。3.1.1 圖的鄰接矩陣存儲表示本課題有鄰接矩陣存儲表示，鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G=（V，E）是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣：Ai,j=1：若（Vi，Vj）是E（G）中的邊；Ai,j=0：若（Vi，Vj）不是E(G)中的邊。用鄰接矩陣表示法表示圖，除了存儲用于表示頂點間相鄰關(guān)系的鄰接矩陣外，通常還需要用一個順序表存儲頂點信息。因此，我們就要進行定義數(shù)據(jù)類型。由于無向圖的鄰接矩陣是對稱的，故采用壓縮存儲方式，僅存儲上三角陣（不包括對角線上的元素）中的元素即可。顯然，鄰接矩陣表示法的空間雜度S（n）=O（n2）。開始進行類型定義，用輸入的方式來控制圖的頂點數(shù)和邊數(shù)，并對鄰接矩陣進行初始化，將G-arcsij=0，再從鍵盤上獲得頂點信息，建立頂點表，在此同時G-arcsij=1，G-arcsji=1，最后輸出鄰接矩陣，用兩層for循環(huán)語句來控制。3.1.2 圖的鄰接表存儲表示 另外還有鄰接表的存儲表示。鄰接表是一種鏈式的存儲結(jié)構(gòu)，在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點Vi的邊。每個結(jié)點由2個域組成，其中鄰接點域（adjvex）指示與頂點Vi鄰接的點在圖中的位置，鏈域（next）指示下一條邊的結(jié)點。所以一開始必須先定義鄰接表的邊結(jié)點類型以及鄰接表類型，并對鄰接表進行初始化，然后根據(jù)所輸入的相關(guān)信息，包括圖的頂點數(shù)、邊數(shù)以及各條邊的起點與終點序號，建立圖的鄰接表。對于無向圖，一條邊的兩的個頂點，互為鄰接點，所以在存儲時，應向起點的單鏈表表頭插入一邊結(jié)點，即終點。同時將終點的單鏈表表頭插入一邊結(jié)點，即起點。對于鄰接表的輸出，采用for語句輸出各結(jié)點。3.2 圖的遍歷和樹的遍歷類似，圖的遍歷也是從某個頂點出發(fā)，沿著某條搜索路徑對圖中所有的頂點各作一次訪問。若給定的圖是連通圖，則從圖中任一頂點出發(fā)順著邊可以訪問到該圖的所有頂點。圖的遍歷比樹的遍歷復雜得多，這是因為圖中的任一頂點都可能和其余頂點相鄰接，故在訪問了某個頂點之后，可能順著某條回路又回到了頂點。為了避免重復訪問同一個頂點必須記住每個頂點是否被訪問過。為此，可設(shè)置一個布爾向量visitedn，它的初始值為0，一旦訪問了頂點Vi，便將visitedi-1置為1。 根據(jù)搜索路徑的方向不同，有兩種常用的遍歷圖的方法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。3.2.1 圖的深度優(yōu)先遍歷假設(shè)給定圖G的初態(tài)是所有頂點未曾被訪問，在G中任選一頂點Vi為初始出發(fā)點，則深度優(yōu)先遍歷可定義如下：首先，訪問出發(fā)點Vi，并將其標記為已訪問過，然后，依次從Vi出發(fā)搜索Vi的每一個鄰接點Vj，若Vj未曾訪問過，則以Vj為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷。顯然這是一個遞歸的過程，它的特點是盡可能先對縱深方向進行搜索，故稱之為深度優(yōu)先遍歷。在實現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。具體過程應為：先訪問初始點Vi，并標志其已被訪問。此時定義一指向邊結(jié)點的指針p，并建立一個while（）循環(huán)，以指針所指對象不為空為控制條件，當Vi的鄰接點未被訪問時，遞歸調(diào)用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向下一個邊結(jié)點。這樣就可以完成圖的深度優(yōu)先遍歷了。 對圖進行深度優(yōu)先遍歷時，按訪問頂點的先后順序所得到的頂點序列，稱為該圖的深度優(yōu)先遍歷序列，簡稱DFS序列。一個圖的DFS序列不唯一，它與算法、圖的存儲結(jié)構(gòu)以及初始出發(fā)點有關(guān)。在DFS算法中，當從Vi出發(fā)搜索時，是在鄰接矩陣的第i行中從左至右選擇下一個未曾訪問的鄰接點作為新的出發(fā)點，若這種鄰接點多于一個，則選中的是序號較小的那一個。因為圖的鄰接矩陣表示是唯一的，故對于指定的初始出發(fā)點，有DFS算法所得的DFS序列是序列是唯一的。3.2.2 圖的廣度優(yōu)先遍歷廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。設(shè)圖G中某頂點Vi出發(fā)，在訪問了Vi之后訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點的鄰接點”被訪問，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尙有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直到圖中所有頂點都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以Vi為起始點，由近及遠，依次訪問和Vi有路徑相通且路徑長度為1，2，的頂點。所以要實現(xiàn)算法必須先建立一個元素類型為整型的空隊列，并定義隊首與隊尾指針，同時也要定義一個標志數(shù)組以標記結(jié)點是否被訪問。同樣，也是從初始點出發(fā)開始訪問，訪問初始點，標志其已被訪問，并將其入隊。當隊列非空時進行循環(huán)處理。當結(jié)點被訪問時對其進行標志，并入隊列。通過while（）循環(huán)，并以是否被訪問為控制條件，訪問所有結(jié)點，完成圖的廣度優(yōu)先遍歷。和定義圖的DFS序列類似，我們可將廣度優(yōu)先遍歷圖所得到的頂點序列，定義為圖的廣度優(yōu)先搜索遍歷序列，簡稱BFS序列。一個圖的BFS序列也是不唯一的，它與算法、圖的存儲結(jié)構(gòu)以及初始出發(fā)點有關(guān)。3.3圖的頂點的度若無向圖用鄰接矩陣表示，Vi頂點的度即是該矩陣第i行或第j列中非0元素的個數(shù)之和。若無向圖用鄰接表表示，Vi的度分為出度和入度。出度即是表結(jié)點的個數(shù)，入度即是逆鄰接表的出度。第四章 算法（數(shù)據(jù)結(jié)構(gòu)）描述4.1 圖的存儲結(jié)構(gòu)的建立。4.1.1 定義鄰接矩陣的定義類型typedef int datatype;typedef structchar vexsmax;int arcsmaxmax;int vexsnum,arcsnum; /* 頂點個數(shù)及邊的個數(shù) */graph;4.1.2定義鄰接表的邊結(jié)點類型以及鄰接表類型typedef char vextype;typedef struct node int adjvex; /* 鄰接點域 */ struct node *next; /* 鏈域 */enode; /* 邊表結(jié)點 */typedef struct vextype vertex; /* 頂點信息 */ enode *link; /* 邊表頭指針 */vnode; /* 頂點表結(jié)點4.1.3初始化圖的鄰接矩陣for(i=0;ivexsnum;i+)G-vexsi=getchar(); for(i=0;ivexsnum;i+)for(j=0;jvexsnum;j+)G-arcsij=0; 4.1.4 初始化圖的鄰接表需建立一個鄰接表初始化函數(shù)對圖的鄰接表進行初始化。即建立一個所有邊結(jié)點都為空的鄰接表。for(i=0;inext。這樣就可以訪問所有結(jié)點，完成圖的廣度優(yōu)先遍歷。廣度優(yōu)先遍歷的相關(guān)代碼在下面的源代碼中給出。4.3 main函數(shù)在main函數(shù)中運用了菜單。用主菜單來控制是選擇鄰接矩陣的存儲表示還是鄰接表的存儲表示，用子菜單來控制選擇深度優(yōu)先遍歷還是廣度優(yōu)先遍歷。4.4 圖的大致流程表圖的存儲與遍歷鄰接矩陣表示法鄰接表表示法深度優(yōu)先遍歷廣度優(yōu)先遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷各頂點的度各頂點的度第五章 源代碼程序 圖的存儲與遍歷#include#include #define max 6typedef int datatype;typedef structchar vexsmax;int arcsmaxmax;int vexsnum,arcsnum; /* 頂點個數(shù)及邊的個數(shù) */graph;void creatgraph(graph *G) /* 建立鄰接矩陣的無向圖 */int i,j,k,sum;printf(請輸入頂點個數(shù)及邊的個數(shù)：n);scanf(%d%d,&G-vexsnum,&G-arcsnum);printf(請讀入頂點信息，建立頂點表：n);getchar();for(i=0;ivexsnum;i+)G-vexsi=getchar(); for(i=0;ivexsnum;i+)for(j=0;jvexsnum;j+)G-arcsij=0; /* 鄰接矩陣初始化 */printf(請輸入相鄰接的兩邊的頂點信息：n);for(k=0;karcsnum;k+)scanf(%d%d,&i,&j);G-arcsij=1;G-arcsji=1; /* 讀入邊（Vi,Vj） */printf(輸出的鄰接矩陣為：n);for(i=0;ivexsnum;i+)printf(n);for(j=0;jvexsnum;j+)printf(%3d,G-arcsij); /* 鄰接矩陣的輸出 */printf(n輸出鄰接矩陣Vi頂點的度為：n);for(i=0;ivexsnum;i+)sum=0;for(j=0;jvexsnum;j+)if(G-arcsij=1)sum+;printf(V%d的度為：%dn,i,sum); /* 各頂點的度 */#define n 4#define m 5typedef char vextype;typedef struct node int adjvex; /* 鄰接點域 */ struct node *next; /* 鏈域 */enode; /* 邊表結(jié)點 */typedef struct vextype vertex; /* 頂點信息 */ enode *link; /* 邊表頭指針 */vnode; /* 頂點表結(jié)點 */vnode an;void creatlist() /* 建立無向圖的鄰接表 */ int i,j,k,sum; enode *s; printf(請讀入頂點信息，建立頂點表：n); getchar(); for(i=0;in;i+) ai.vertex=getchar(); ai.link=NULL; /* 邊表頭指針初始化 */ printf(請輸入相鄰接的兩邊的頂點信息：n); for(k=0;kadjvex=j; s-next=ai.link; ai.link=s; /* 將*s插入頂點Vi的邊表頭部 */ s=(enode*)malloc(sizeof(enode); /* 生成鄰接點序號為i的邊表結(jié)點*s */ s-adjvex=i; s-next=aj.link; aj.link=s; /* 將*s插入頂點Vj的邊表頭部 */ printf(輸出的鄰接表為：n); for(i=0;i,s-adjvex); s=s-next; /* 鄰接表的輸出 */printf(輸出鄰接表Vi頂點的度為：n); for(i=0;inext; printf(V%d的度為：%dn,i,sum); /* 各頂點的度 */int visited1max=0; /* 定義布爾向量visited1為全程量 */void dfs1(graph *G,int i) /* 從Vi+1出發(fā)深度優(yōu)先搜索圖G，G用鄰接矩陣表示 */int j;printf(node:%cn,G-vexsi); /* 訪問出發(fā)點Vi+1 */visited1i=1; /* 標記Vi+1已被訪問 */for(j=0;jvexsnum;j+) /* 依次搜索Vi+1的鄰接點 */if(G-arcsij)&(!visited1j)dfs1(G,j);/* 若Vi+1的鄰接點Vi+1未曾訪問過，則從Vi+1出發(fā)進行深度優(yōu)先搜索 */#define maxsize 80typedef int datatype;typedef structdatatype datamaxsize;int front,rear;sequeue; /* 順序隊列的類型 */sequeue *p; /* p是順序隊列類型的指針 */void setnull() /* 置隊列p為空對 */p-front=maxsize-1;p-rear=maxsize-1;int empty() /* 判別p是否為空 */if(p-front=p-rear)return 1;else return 0;int front() /* 取p的隊頭元素 */if(empty()printf(the sequeue is empty);return 0;else return p-data(p-front+1)%maxsize;int enqueue(int x) /* 將新元素x插入隊列p的隊尾 */if(p-rear+1)%maxsize=p-front)printf(the queue is full.);return 0;else p-rear=(p-rear+1)%maxsize;p-datap-rear=x;return x; int dequeue() /* 刪除隊列p的頭元素，并返回該元素 */if(empty()printf(the sequeue is empty);return 0;elsep-front=(p-front+1)%maxsize;return (p-datap-front);int visited2max=0;void bfs1(graph *G,int k)/*從Vi+1出發(fā)廣度優(yōu)先搜索圖G，G用鄰接矩陣表示*/int i,j;setnull();printf(node:%cn,G-vexsk); /* 訪問出發(fā)點Vk+1 */visited2k=1;enqueue(k);while(!empty() /* 隊非空時執(zhí)行 */i=dequeue();for(j=0;jvexsnum;j+)if(G-arcsij)&(!visited2j)printf(%cn,G-vexsj); /* 訪問Vi+1的未曾訪問的鄰接點Vj+1 */visited2j=1;enqueue(j); /* 訪問過的頂點入隊 */int visited3n=0;void dfs2(int i) /* 從Vi+1出發(fā)深度優(yōu)先遍歷搜索圖a，a圖用鄰接表表示*/enode *p;printf(node:%cn,ai.vertex);visited3i=1;p=ai.link; /* 取Vi+1的邊表頭指針 */while(p!=NULL) /* 依次搜索Vi+1的鄰接點 */if(!visited3p-adjvex)dfs2(p-adjvex); /* 從Vi+1的未曾訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索 */p=p-next; /* 找Vi+1下一個鄰接點 */int visited4n=0;void bfs2(int k) /* 從Vi+1出發(fā)廣度優(yōu)先搜索圖a,a用鄰接表表示 */int i;enode *p;setnull();printf(node:%cn,ak.vertex);visited4k=1;enqueue(k);while(!empty()i=dequeue();p=ai.link; /* 取Vi+1的邊表頭指針 */while(p!=NULL) /* 依次搜索Vi+1的鄰接點 */if(!visited4p-adjvex) /* 訪問Vi+1的未曾訪問的鄰接點 */printf(node:%cn,ap-adjvex.vertex);visited4p-adjvex=1;enqueue(p-adjvex); /* 訪問過的頂點入隊 */p=p-next; /* 找Vi+1的下一個鄰接點 */void main()int i,j,x,y,z,s,t;graph a;int flag=0;p=(sequeue*)malloc(sizeof(sequeue);printf(=歡迎進入=n);while(1)printf(請選擇輸入n1為用鄰接矩陣存儲圖n2為用鄰接表存儲圖n0為退出：n); scanf(%d,&x);switch(x)case 1:creatgraph(&a);while(flag=0) printf(請選擇輸入n1為鄰接矩陣深度優(yōu)先遍歷n2為鄰接矩陣廣度優(yōu)先遍歷n0為返回繼續(xù)選擇圖的存儲：n); scanf(%d,&y); switch(y) case 1:printf(請輸入深度優(yōu)先遍歷的頂點：n); scanf(%d,&i); dfs1(&a,i);break; case 2:printf(請輸入廣度優(yōu)先遍歷的頂點：n); scanf(%d,&j); bfs1(&a,j);break; case 0:flag=1; break;case 2:creatlist();while(flag=0)printf(請選擇輸入n1為鄰接表深度優(yōu)先遍歷n2為鄰接表廣度優(yōu)先遍歷n0為返回繼續(xù)選擇圖的存儲：n：); scanf(%d,& z); switch(z) case 1:printf(請輸入深度優(yōu)先遍歷的頂點：n); scanf(%d,&s); dfs2(s);break; case 2:printf(請輸入廣度優(yōu)先遍歷的頂點：n); scanf(%d,&t); bfs2(t);break; case 0:flag=1; break;case 0:exit(0);第六章 測試結(jié)果由于學習之初對圖的存儲結(jié)構(gòu)了解不是很清楚，所以在運行出了錯誤。首先在運行當中少了一句算法：在建立鄰接表，輸入頂點信息時，少了getchar()語句。因為程序本身沒報