【文章內(nèi)容簡介】 一、 目的掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu)；掌握DFS及BFS對圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。二、 要求采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。三、 DFS和BFS 的基本思想深度優(yōu)先搜索法DFS的基本思想：從圖G中某個頂點Vo出發(fā)，首先訪問Vo，然后選擇一個與Vo相鄰且沒被訪問過的頂點Vi訪問，再從Vi出發(fā)選擇一個與Vi相鄰且沒被訪問過的頂點Vj訪問，……依次繼續(xù)。如果當(dāng)前被訪問過的頂點的所有鄰接頂點都已被訪問，則回退到已被訪問的頂點序列中最后一個擁有未被訪問的相鄰頂點的頂點W，從W出發(fā)按同樣方法向前遍歷。直到圖中所有的頂點都被訪問。 廣度優(yōu)先算法BFS的基本思想：從圖G中某個頂點Vo出發(fā)，首先訪問Vo，然后訪問與Vo相鄰的所有未被訪問過的頂點V1，V2，……，Vt；再依次訪問與V1，V2，……，Vt相鄰的起且未被訪問過的的所有頂點。如此繼續(xù)，直到訪問完圖中的所有頂點。四、 程序源代碼1． 鄰接矩陣作為存儲結(jié)構(gòu)的程序示例includeincludedefine MaxVertexNum 100 //定義最大頂點數(shù)typedef struct{ char vexs[MaxVertexNum]。 //頂點表 int edges[MaxVertexNum][MaxVertexNum]。 //鄰接矩陣，可看作邊表 int n,e。 //圖中的頂點數(shù)n和邊數(shù)e}MGraph。 //用鄰接矩陣表示的圖的類型//=========建立鄰接矩陣=======void CreatMGraph(MGraph *G){ int i,j,k。 char a。 printf(Input VertexNum(n) and EdgesNum(e): )。 scanf(%d,%d,amp。Gn,amp。Ge)。 //輸入頂點數(shù)和邊數(shù) scanf(%c,amp。a)。 printf(Input Vertex string:)。 for(i=0。iGn。i++) { scanf(%c,amp。a)。 Gvexs[i]=a。 //讀入頂點信息，建立頂點表 } for(i=0。iGn。i++) for(j=0。jGn。j++) Gedges[i][j]=0。 //初始化鄰接矩陣 printf(Input edges,Creat Adjacency Matrix\n)。 for(k=0。kGe。k++) { //讀入e條邊，建立鄰接矩陣 scanf(%d%d,amp。i,amp。j)。 //輸入邊（Vi，Vj）的頂點序號 Gedges[i][j]=1。 Gedges[j][i]=1。 //若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句 }}//=========定義標(biāo)志向量，為全局變量=======typedef enum{FALSE,TRUE} Boolean。Boolean visited[MaxVertexNum]。//========DFS：深度優(yōu)先遍歷的遞歸算法======void DFSM(MGraph *G,int i){ //以Vi為出發(fā)點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣 int j。 printf(%c,Gvexs[i])。 //訪問頂點Vi visited[i]=TRUE。 //置已訪問標(biāo)志 for(j=0。jGn。j++) //依次搜索Vi的鄰接點 if(Gedges[i][j]==1 amp。amp。 ! visited[j]) DFSM(G,j)。 //（Vi，Vj）∈E，且Vj未訪問過，故Vj為新出發(fā)點}void DFS(MGraph *G){ int i。 for(i=0。iGn。i++) visited[i]=FALSE。 //標(biāo)志向量初始化 for(i=0。iGn。i++) if(!visited[i]) //Vi未訪問過 DFSM(G,i)。 //以Vi為源點開始DFS搜索}//===========BFS：廣度優(yōu)先遍歷=======void BFS(MGraph *G,int k){ //以Vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索 int i,j,f=0,r=0。 int cq[MaxVertexNum]。 //定義隊列 for(i=0。iGn。i++) visited[i]=FALSE。 //標(biāo)志向量初始化 for(i=0。iGn。i++) cq[i]=1。 //隊列初始化 printf(%c,Gvexs[k])。 //訪問源點Vk visited[k]=TRUE。 cq[r]=k。 //Vk已訪問，將其入隊。注意，實際上是將其序號入隊 while(cq[f]!=1) { //隊非空則執(zhí)行 i=cq[f]。 f=f+1。 //Vf出隊 for(j=0。jGn。j++) //依次Vi的鄰接點Vj if(Gedges[i][j]==1 amp。amp。 !visited[j]) { //Vj未訪問 printf(%c,Gvexs[j])。 //訪問Vj visited[j]=TRUE。
r=r+1。 cq[r]=j。 //訪問過Vj入隊 } }}//==========main=====void main(){ int i。 MGraph *G。 G=(MGraph *)malloc(sizeof(MGraph))。 //為圖G申請內(nèi)存空間 CreatMGraph(G)。 //建立鄰接矩陣 printf(Print Graph DFS: )。 DFS(G)。 //深度優(yōu)先遍歷 printf(\n)。 printf(Print Graph BFS: )。 BFS(G,3)。 //以序號為3的頂點開始廣度優(yōu)先遍歷 printf(\n)。}調(diào)試結(jié)果：自己畫的圖： 1對應(yīng)頂點下標(biāo)0 以此類推 9對應(yīng)下標(biāo)8預(yù)計運行結(jié)果：DFS:012345678BFS:324105687對應(yīng)我這個圖：DFS：123456789BFS：435216798實驗心得：圖在數(shù)據(jù)結(jié)構(gòu)中是相當(dāng)重要的一部分 聯(lián)系很多現(xiàn)實問題 圖的根本就是頂點和邊 通過頂點和邊建立鄰接矩陣以及鄰接鏈表 廣度搜索和深度搜索是此算法著重關(guān)注的地方。要學(xué)會自己畫圖 然后寫出這兩種搜索的結(jié)果，程序中用了隊的算法 是亮點 通過TRUE和FAUSE來標(biāo)記頂點是否以及訪問 避免重復(fù) 實驗四、排序一、 目的掌握各種排序方法的基本思想、排序過程、算法實現(xiàn)，能進行時間和空間性能的分析，根據(jù)實際問題的特點和要求選擇合適的排序方法。二、 要求實現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運行速度。三、 程序示例includeincludedefine Max 100 //假設(shè)文件長度typedef struct{ //定義記錄類型