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

1、摘 要圖（Graph）是一種復(fù)雜的非線性結(jié)構(gòu)。圖可以分為無向圖、有向圖。若將圖的每條邊都賦上一個權(quán)，則稱這種帶權(quán)圖網(wǎng)絡(luò)。在人工智能、工程、數(shù)學(xué)、物理、化學(xué)、計算機(jī)科學(xué)等領(lǐng)域中，圖結(jié)構(gòu)有著廣泛的應(yīng)用。在圖結(jié)構(gòu)中，對結(jié)點(diǎn)（圖中常稱為頂點(diǎn)）的前趨和后繼個數(shù)都是不加以限制的，即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個結(jié)點(diǎn)之間都可能相關(guān)。圖有兩種常用的存儲表示方法：鄰接矩陣表示法和鄰接表表示法。在一個圖中，鄰接矩陣表示是唯一的，但鄰接表表示不唯一。在表示的過程中還可以實(shí)現(xiàn)圖的遍歷（深度優(yōu)先遍歷和廣度優(yōu)先遍歷）及求圖中頂點(diǎn)的度。當(dāng)然對于圖的廣度優(yōu)先遍歷還利用了隊列的五種基本運(yùn)算（置空隊列、進(jìn)隊、出隊、取隊頭元

2、素、判隊空）來實(shí)現(xiàn)。這不僅讓我們鞏固了之前學(xué)的隊列的基本操作，還懂得了將算法相互融合和運(yùn)用。目 錄第一章 課程設(shè)計目的3第二章 課程設(shè)計內(nèi)容和要求32.1課程設(shè)計內(nèi)容3圖的鄰接矩陣的建立與輸出3圖的鄰接表的建立與輸出3圖的遍歷的實(shí)現(xiàn)42.1.4 圖的頂點(diǎn)的度42.2 運(yùn)行環(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圖的頂點(diǎn)的度7第四章 算法（數(shù)據(jù)結(jié)構(gòu)）描述74.1 圖的存儲結(jié)構(gòu)的建立。74.1.1 定義鄰接矩陣的定義類型7定義鄰接表的邊結(jié)點(diǎn)類型以

3、及鄰接表類型7初始化圖的鄰接矩陣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第八章 參考文獻(xiàn)22第一章 課程設(shè)計目的本學(xué)期我們對數(shù)據(jù)結(jié)構(gòu)這門課程進(jìn)行了學(xué)習(xí)。這門課程是一門實(shí)踐性非常強(qiáng)的課程，為了讓大家更好地理解與運(yùn)用所學(xué)知識，提高動手能力，我們進(jìn)行了此次課程設(shè)計。數(shù)據(jù)結(jié)構(gòu)是計算機(jī)軟件和計算機(jī)應(yīng)用專業(yè)的核心課程之一，在眾多的計算機(jī)系統(tǒng)軟件和應(yīng)用軟件中都要用到各種數(shù)據(jù)結(jié)構(gòu)。這次課程設(shè)計不但要求學(xué)習(xí)者掌握數(shù)據(jù)結(jié)構(gòu)中的各方面知識，還要求

4、學(xué)習(xí)者具備一定的C語言基礎(chǔ)和編程能力。具體說來，這次課程設(shè)計主要有兩大方面目的：一是讓學(xué)習(xí)者通過學(xué)習(xí)掌握數(shù)據(jù)結(jié)構(gòu)中的知識。對于圖的存儲與遍歷這一課題來說，所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識主要有：圖的鄰接矩陣存儲、圖的鄰接表存儲、隊列的基本運(yùn)算實(shí)現(xiàn)、鄰接矩陣的算法實(shí)現(xiàn)、鄰接表的算法實(shí)現(xiàn)、圖的廣度優(yōu)先遍歷算法實(shí)現(xiàn)、圖的深度優(yōu)先遍歷算法實(shí)現(xiàn)。二是通過學(xué)習(xí)鞏固并提高學(xué)習(xí)者的C語言知識，并初步了解Visual C+的知識，提高其編程能力與專業(yè)水平。第二章 課程設(shè)計內(nèi)容和要求2.1課程設(shè)計內(nèi)容該課題要求以鄰接矩陣和鄰接表的方式存儲圖，輸出鄰接矩陣和鄰接表，并要求實(shí)現(xiàn)圖的深度、廣度兩種遍歷及頂點(diǎn)的度。圖的鄰接矩陣的

5、建立與輸出 對任意輸入頂點(diǎn)數(shù)和邊數(shù)的圖，若對無向圖進(jìn)行討論，根據(jù)鄰接矩陣的存儲結(jié)構(gòu)建立圖的鄰接矩陣并輸出。要求輸出的格式是矩陣形式，這樣便于直觀的了解。圖的鄰接表的建立與輸出對任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)可以宏定義），若對無向圖進(jìn)行討論，根據(jù)鄰接表的存儲結(jié)構(gòu)建立圖的鄰接表并輸出。圖的遍歷的實(shí)現(xiàn)圖的遍歷包括圖的廣度優(yōu)先遍歷與深度優(yōu)先遍歷。對于廣度優(yōu)先遍歷應(yīng)利用隊列的五種基本運(yùn)算（置空隊列、進(jìn)隊、出隊、取隊頭元素、判隊空）來實(shí)現(xiàn)。首先建立一空隊列，從初始點(diǎn)出發(fā)進(jìn)行訪問，當(dāng)被訪問時入隊，訪問完出隊。并以隊列是否為空作為循環(huán)控制條件。對于深度優(yōu)先遍歷則采用遞歸算法來實(shí)現(xiàn)。當(dāng)然，若存儲圖的表示不一樣，進(jìn)行

6、兩種遍歷的方式也不一樣。 圖的頂點(diǎn)的度 在圖中，可以求頂點(diǎn)的度。在無向圖用鄰接矩陣表示，Vi頂點(diǎn)的度即是該矩陣第i行或第j列中非0元素的個數(shù)之和。若無向圖用鄰接表表示，頂點(diǎn)Vi的度則是第i個邊表中的結(jié)點(diǎn)個數(shù)。2.2 運(yùn)行環(huán)境該程序的運(yùn)行環(huán)境為Windows xp系統(tǒng)，Microsoft Visual C+6.0版本。第三章 課程設(shè)計分析3.1圖的存儲 圖的存儲表示方法很多，但常用的是：圖的矩陣表示和鄰接表表示。至于在遇到問題具體選擇哪一種表示法，主要取決于具體的應(yīng)用和欲施加的操作。 圖的鄰接矩陣存儲表示本課題有鄰接矩陣存儲表示，鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=（V，E）是具有n個頂

7、點(diǎn)的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣：Ai,j=1：若（Vi，Vj）是E（G）中的邊；Ai,j=0：若（Vi，Vj）不是E(G)中的邊。用鄰接矩陣表示法表示圖，除了存儲用于表示頂點(diǎn)間相鄰關(guān)系的鄰接矩陣外，通常還需要用一個順序表存儲頂點(diǎn)信息。因此，我們就要進(jìn)行定義數(shù)據(jù)類型。由于無向圖的鄰接矩陣是對稱的，故采用壓縮存儲方式，僅存儲上三角陣（不包括對角線上的元素）中的元素即可。顯然，鄰接矩陣表示法的空間雜度S（n）=O（n2）。開始進(jìn)行類型定義，用輸入的方式來控制圖的頂點(diǎn)數(shù)和邊數(shù)，并對鄰接矩陣進(jìn)行初始化，將G->arcsij=0，再從鍵盤上獲得頂點(diǎn)信息，建立頂點(diǎn)表，在此同時G->

8、;arcsij=1，G->arcsji=1，最后輸出鄰接矩陣，用兩層for循環(huán)語句來控制。 圖的鄰接表存儲表示 另外還有鄰接表的存儲表示。鄰接表是一種鏈?zhǔn)降拇鎯Y(jié)構(gòu)，在鄰接表中，對圖中每個頂點(diǎn)建立一個單鏈表，第i個單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊。每個結(jié)點(diǎn)由2個域組成，其中鄰接點(diǎn)域（adjvex）指示與頂點(diǎn)Vi鄰接的點(diǎn)在圖中的位置，鏈域（next）指示下一條邊的結(jié)點(diǎn)。所以一開始必須先定義鄰接表的邊結(jié)點(diǎn)類型以及鄰接表類型，并對鄰接表進(jìn)行初始化，然后根據(jù)所輸入的相關(guān)信息，包括圖的頂點(diǎn)數(shù)、邊數(shù)以及各條邊的起點(diǎn)與終點(diǎn)序號，建立圖的鄰接表。對于無向圖，一條邊的兩的個頂點(diǎn)，互為鄰接點(diǎn)，所以在存儲

9、時，應(yīng)向起點(diǎn)的單鏈表表頭插入一邊結(jié)點(diǎn)，即終點(diǎn)。同時將終點(diǎn)的單鏈表表頭插入一邊結(jié)點(diǎn)，即起點(diǎn)。對于鄰接表的輸出，采用for語句輸出各結(jié)點(diǎn)。3.2 圖的遍歷和樹的遍歷類似，圖的遍歷也是從某個頂點(diǎn)出發(fā)，沿著某條搜索路徑對圖中所有的頂點(diǎn)各作一次訪問。若給定的圖是連通圖，則從圖中任一頂點(diǎn)出發(fā)順著邊可以訪問到該圖的所有頂點(diǎn)。圖的遍歷比樹的遍歷復(fù)雜得多，這是因為圖中的任一頂點(diǎn)都可能和其余頂點(diǎn)相鄰接，故在訪問了某個頂點(diǎn)之后，可能順著某條回路又回到了頂點(diǎn)。為了避免重復(fù)訪問同一個頂點(diǎn)必須記住每個頂點(diǎn)是否被訪問過。為此，可設(shè)置一個布爾向量visitedn，它的初始值為0，一旦訪問了頂點(diǎn)Vi，便將visitedi-1置

10、為1。 根據(jù)搜索路徑的方向不同，有兩種常用的遍歷圖的方法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。 圖的深度優(yōu)先遍歷假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)未曾被訪問，在G中任選一頂點(diǎn)Vi為初始出發(fā)點(diǎn)，則深度優(yōu)先遍歷可定義如下：首先，訪問出發(fā)點(diǎn)Vi，并將其標(biāo)記為已訪問過，然后，依次從Vi出發(fā)搜索Vi的每一個鄰接點(diǎn)Vj，若Vj未曾訪問過，則以Vj為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷。顯然這是一個遞歸的過程，它的特點(diǎn)是盡可能先對縱深方向進(jìn)行搜索，故稱之為深度優(yōu)先遍歷。在實(shí)現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。具體過程應(yīng)為：先訪問初始點(diǎn)Vi，并標(biāo)志其已被訪問。此時定義一指向邊結(jié)點(diǎn)的指針p，并建立一個while（）

11、循環(huán)，以指針?biāo)笇ο蟛粸榭諡榭刂茥l件，當(dāng)Vi的鄰接點(diǎn)未被訪問時，遞歸調(diào)用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向下一個邊結(jié)點(diǎn)。這樣就可以完成圖的深度優(yōu)先遍歷了。 對圖進(jìn)行深度優(yōu)先遍歷時，按訪問頂點(diǎn)的先后順序所得到的頂點(diǎn)序列，稱為該圖的深度優(yōu)先遍歷序列，簡稱DFS序列。一個圖的DFS序列不唯一，它與算法、圖的存儲結(jié)構(gòu)以及初始出發(fā)點(diǎn)有關(guān)。在DFS算法中，當(dāng)從Vi出發(fā)搜索時，是在鄰接矩陣的第i行中從左至右選擇下一個未曾訪問的鄰接點(diǎn)作為新的出發(fā)點(diǎn)，若這種鄰接點(diǎn)多于一個，則選中的是序號較小的那一個。因為圖的鄰接矩陣表示是唯一的，故對于指定的初始出發(fā)點(diǎn)，有DFS算法所得的DFS序列是序列是唯一的。 圖的廣

12、度優(yōu)先遍歷廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。設(shè)圖G中某頂點(diǎn)Vi出發(fā)，在訪問了Vi之后訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)的鄰接點(diǎn)”被訪問，直到圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時圖中尙有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以Vi為起始點(diǎn)，由近及遠(yuǎn)，依次訪問和Vi有路徑相通且路徑長度為1，2，的頂點(diǎn)。所以要實(shí)現(xiàn)算法必須先建立一個元素類型為整型的空隊列，并定義隊首與隊尾指針，同時也要定義一個標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪問。同樣，也是從初始點(diǎn)

13、出發(fā)開始訪問，訪問初始點(diǎn)，標(biāo)志其已被訪問，并將其入隊。當(dāng)隊列非空時進(jìn)行循環(huán)處理。當(dāng)結(jié)點(diǎn)被訪問時對其進(jìn)行標(biāo)志，并入隊列。通過while（）循環(huán)，并以是否被訪問為控制條件，訪問所有結(jié)點(diǎn)，完成圖的廣度優(yōu)先遍歷。和定義圖的DFS序列類似，我們可將廣度優(yōu)先遍歷圖所得到的頂點(diǎn)序列，定義為圖的廣度優(yōu)先搜索遍歷序列，簡稱BFS序列。一個圖的BFS序列也是不唯一的，它與算法、圖的存儲結(jié)構(gòu)以及初始出發(fā)點(diǎn)有關(guān)。3.3圖的頂點(diǎn)的度若無向圖用鄰接矩陣表示，Vi頂點(diǎn)的度即是該矩陣第i行或第j列中非0元素的個數(shù)之和。若無向圖用鄰接表表示，Vi的度分為出度和入度。出度即是表結(jié)點(diǎn)的個數(shù)，入度即是逆鄰接表的出度。第四章 算法（數(shù)

14、據(jù)結(jié)構(gòu)）描述4.1 圖的存儲結(jié)構(gòu)的建立。 定義鄰接矩陣的定義類型typedef int datatype;typedef structchar vexsmax;int arcsmaxmax;int vexsnum,arcsnum; /* 頂點(diǎn)個數(shù)及邊的個數(shù) */graph;定義鄰接表的邊結(jié)點(diǎn)類型以及鄰接表類型typedef char vextype;typedef struct node int adjvex; /* 鄰接點(diǎn)域 */ struct node *next; /* 鏈域 */enode; /* 邊表結(jié)點(diǎn) */typedef struct vextype vertex; /* 頂點(diǎn)信

15、息 */ enode *link; /* 邊表頭指針 */vnode; /* 頂點(diǎn)表結(jié)點(diǎn)初始化圖的鄰接矩陣for(i=0;i<G->vexsnum;i+)G->vexsi=getchar(); for(i=0;i<G->vexsnum;i+)for(j=0;j<G->vexsnum;j+)G->arcsij=0; 初始化圖的鄰接表需建立一個鄰接表初始化函數(shù)對圖的鄰接表進(jìn)行初始化。即建立一個所有邊結(jié)點(diǎn)都為空的鄰接表。for(i=0;i<n;i+) ai.vertex=getchar(); ai.link=NULL; /* 邊表頭指針初始化 *

16、/ 4.2 圖的遍歷 深度優(yōu)先遍歷圖具體過程應(yīng)為：在深度優(yōu)先遍歷函數(shù)的參數(shù)中定義一個標(biāo)志數(shù)組visited1n（鄰接矩陣表示）和visited3n（鄰接表表示），當(dāng)某結(jié)點(diǎn)已被訪問時visited1i=1或visited3i=1，未被訪問時visited1i=0或visited3i=0。先訪問初始點(diǎn)Vi，并標(biāo)志其已被訪問。若是鄰接矩陣表示時將定義一指向邊結(jié)點(diǎn)的指針p，并建立一個while（）循環(huán)，以指針?biāo)笇ο蟛粸榭諡榭刂茥l件，當(dāng)Vi的鄰接點(diǎn)未被訪問時，遞歸調(diào)用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向下一個邊結(jié)點(diǎn)。這樣就可以完成圖的深度優(yōu)先遍歷了。深度優(yōu)先遍歷的相關(guān)代碼在下面的源代碼中給出。 廣

17、度優(yōu)先遍歷圖要實(shí)現(xiàn)算法必須先建立一個元素類型為整形的空隊列，并定義隊首與隊尾指針，同時也要定義一個標(biāo)志數(shù)組visited2n（鄰接矩陣表示）和visited4n（鄰接表表示）和以標(biāo)記結(jié)點(diǎn)是否被訪問。同樣，也是從初始點(diǎn)Vi出發(fā)開始訪問，訪問初始點(diǎn)，標(biāo)志其已被訪問，并將已訪問過的初始點(diǎn)序號i入隊。當(dāng)隊列非空時進(jìn)行循環(huán)處理，刪除隊首元素，第一次執(zhí)行時k的值為i，即front=(front+1)%maxsize。然后取Vk鄰接表的表頭指針int k=pfront; enode* p=ak。當(dāng)邊結(jié)點(diǎn)指針p不為空時，通過while（）循環(huán)，并以p是否為空為控制條件，依次搜索Vk的每一個結(jié)點(diǎn)。訪問完后，將p

18、指向p->next。這樣就可以訪問所有結(jié)點(diǎn)，完成圖的廣度優(yōu)先遍歷。廣度優(yōu)先遍歷的相關(guān)代碼在下面的源代碼中給出。4.3 main函數(shù)在main函數(shù)中運(yùn)用了菜單。用主菜單來控制是選擇鄰接矩陣的存儲表示還是鄰接表的存儲表示，用子菜單來控制選擇深度優(yōu)先遍歷還是廣度優(yōu)先遍歷。4.4 圖的大致流程表圖的存儲與遍歷鄰接矩陣表示法鄰接表表示法深度優(yōu)先遍歷廣度優(yōu)先遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷各頂點(diǎn)的度各頂點(diǎn)的度第五章 源代碼程序 圖的存儲與遍歷#include<stdio.h>#include<malloc.h> #define max 6typedef int datatype;

19、typedef structchar vexsmax;int arcsmaxmax;int vexsnum,arcsnum; /* 頂點(diǎn)個數(shù)及邊的個數(shù) */graph;void creatgraph(graph *G) /* 建立鄰接矩陣的無向圖 */int i,j,k,sum;printf("請輸入頂點(diǎn)個數(shù)及邊的個數(shù)：n");scanf("%d%d",&G->vexsnum,&G->arcsnum);printf("請讀入頂點(diǎn)信息，建立頂點(diǎn)表：n");getchar();for(i=0;i<G-&g

20、t;vexsnum;i+)G->vexsi=getchar(); for(i=0;i<G->vexsnum;i+)for(j=0;j<G->vexsnum;j+)G->arcsij=0; /* 鄰接矩陣初始化 */printf("請輸入相鄰接的兩邊的頂點(diǎn)信息：n");for(k=0;k<G->arcsnum;k+)scanf("%d%d",&i,&j);G->arcsij=1;G->arcsji=1; /* 讀入邊（Vi,Vj） */printf("輸出的鄰接矩陣為：n

21、");for(i=0;i<G->vexsnum;i+)printf("n");for(j=0;j<G->vexsnum;j+)printf("%3d",G->arcsij); /* 鄰接矩陣的輸出 */printf("n輸出鄰接矩陣Vi頂點(diǎn)的度為：n");for(i=0;i<G->vexsnum;i+)sum=0;for(j=0;j<G->vexsnum;j+)if(G->arcsij=1)sum+;printf("V%d的度為：%dn",i,s

22、um); /* 各頂點(diǎn)的度 */#define n 4#define m 5typedef char vextype;typedef struct node int adjvex; /* 鄰接點(diǎn)域 */ struct node *next; /* 鏈域 */enode; /* 邊表結(jié)點(diǎn) */typedef struct vextype vertex; /* 頂點(diǎn)信息 */ enode *link; /* 邊表頭指針 */vnode; /* 頂點(diǎn)表結(jié)點(diǎn) */vnode an;void creatlist() /* 建立無向圖的鄰接表 */ int i,j,k,sum; enode *s; pri

23、ntf("請讀入頂點(diǎn)信息，建立頂點(diǎn)表：n"); getchar(); for(i=0;i<n;i+) ai.vertex=getchar(); ai.link=NULL; /* 邊表頭指針初始化 */ printf("請輸入相鄰接的兩邊的頂點(diǎn)信息：n"); for(k=0;k<m;k+) scanf("%d%d",&i,&j); /* 讀入邊（Vi,Vj） */ s=(enode*)malloc(sizeof(enode); /* 生成鄰接點(diǎn)序號為j的表結(jié)點(diǎn)*s */ s->adjvex=j; s-&

24、gt;next=ai.link; ai.link=s; /* 將*s插入頂點(diǎn)Vi的邊表頭部 */ s=(enode*)malloc(sizeof(enode); /* 生成鄰接點(diǎn)序號為i的邊表結(jié)點(diǎn)*s */ s->adjvex=i; s->next=aj.link; aj.link=s; /* 將*s插入頂點(diǎn)Vj的邊表頭部 */ printf("輸出的鄰接表為：n"); for(i=0;i<m;i+) printf("n%c ",ai.vertex); s=ai.link; while(s) printf("%d->&q

25、uot;,s->adjvex); s=s->next; /* 鄰接表的輸出 */printf("輸出鄰接表Vi頂點(diǎn)的度為：n"); for(i=0;i<n;i+) s=ai.link; sum=0; while(s) sum+; s=s->next; printf("V%d的度為：%dn",i,sum); /* 各頂點(diǎn)的度 */int visited1max=0; /* 定義布爾向量visited1為全程量 */void dfs1(graph *G,int i) /* 從Vi+1出發(fā)深度優(yōu)先搜索圖G，G用鄰接矩陣表示 */int

26、j;printf("node:%cn",G->vexsi); /* 訪問出發(fā)點(diǎn)Vi+1 */visited1i=1; /* 標(biāo)記Vi+1已被訪問 */for(j=0;j<G->vexsnum;j+) /* 依次搜索Vi+1的鄰接點(diǎn) */if(G->arcsij)&&(!visited1j)dfs1(G,j);/* 若Vi+1的鄰接點(diǎn)Vi+1未曾訪問過，則從Vi+1出發(fā)進(jìn)行深度優(yōu)先搜索 */#define maxsize 80typedef int datatype;typedef structdatatype datamaxsize;

27、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

28、 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

29、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ā)點(diǎn)Vk+1 */visited2k=1;enqueue(k);while(!empty() /* 隊非空時執(zhí)行 */

30、i=dequeue();for(j=0;j<G->vexsnum;j+)if(G->arcsij)&&(!visited2j)printf("%cn",G->vexsj); /* 訪問Vi+1的未曾訪問的鄰接點(diǎn)Vj+1 */visited2j=1;enqueue(j); /* 訪問過的頂點(diǎn)入隊 */int visited3n=0;void dfs2(int i) /* 從Vi+1出發(fā)深度優(yōu)先遍歷搜索圖a，a圖用鄰接表表示*/enode *p;printf("node:%cn",ai.vertex);visited3

31、i=1;p=ai.link; /* 取Vi+1的邊表頭指針 */while(p!=NULL) /* 依次搜索Vi+1的鄰接點(diǎn) */if(!visited3p->adjvex)dfs2(p->adjvex); /* 從Vi+1的未曾訪問過的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索 */p=p->next; /* 找Vi+1下一個鄰接點(diǎn) */int visited4n=0;void bfs2(int k) /* 從Vi+1出發(fā)廣度優(yōu)先搜索圖a,a用鄰接表表示 */int i;enode *p;setnull();printf("node:%cn",ak.vertex);vi

32、sited4k=1;enqueue(k);while(!empty()i=dequeue();p=ai.link; /* 取Vi+1的邊表頭指針 */while(p!=NULL) /* 依次搜索Vi+1的鄰接點(diǎn) */if(!visited4p->adjvex) /* 訪問Vi+1的未曾訪問的鄰接點(diǎn) */printf("node:%cn",ap->adjvex.vertex);visited4p->adjvex=1;enqueue(p->adjvex); /* 訪問過的頂點(diǎn)入隊 */p=p->next; /* 找Vi+1的下一個鄰接點(diǎn) */voi

33、d main()int i,j,x,y,z,s,t;graph a;int flag=0;p=(sequeue*)malloc(sizeof(sequeue);printf("=歡迎進(jìn)入=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ù)

34、選擇圖的存儲：n"); scanf("%d",&y); switch(y) case 1:printf("請輸入深度優(yōu)先遍歷的頂點(diǎn)：n"); scanf("%d",&i); dfs1(&a,i);break; case 2:printf("請輸入廣度優(yōu)先遍歷的頂點(diǎn)：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)先遍歷的頂點(diǎn)：n"); scanf("%d",&s); dfs2(s);break; case 2:printf("請輸入廣度優(yōu)先遍歷的頂點(diǎn)：n&qu