實驗圖的基本操作
一、實驗目的及要求
1、使學生1、使學生可以鞏固所學的有關圖的基本知識。
2、熟練掌握圖的儲存結構。
3、熟練掌握圖的兩種遍歷演算法。
基本要求：
以鄰接表為儲存結構，實現連通無向圖的深度優先和廣度優先遍歷。以使用者指定的結點為起點，分別輸出每種遍歷下的結點訪問序列。
二、演算法描述
[問題描述]
對給定圖，實現圖的深度優先遍歷和廣度優先遍歷。
【測試資料】
由學生依據軟體工程的測試技術自己確定。
四、實驗報告要求
1、實驗報告要按照實驗報告格式規範書寫。
2、實驗上要寫出多批測試資料的執行結果。
3、結合執行結果，對程式進行分析。
程式設計思路：
深度優先演算法：電腦程式的一種編制原理，就是在乙個問題出現多種可以實現的方法和技術的時候，應該優先選擇哪個更合適的，也是一種普遍的邏輯思想，此種思想在運算的過程中，用到電腦程式的一種遞迴的思想。
度優先搜尋演算法：又稱廣度優先搜尋，是最簡便的圖的搜尋演算法之一，這一演算法也是很多重要的圖的演算法的原型。dijkstra單源最短路徑演算法和prim 最小生成樹演算法都採用了和寬度優先搜尋類似的思想。
其別名又叫bfs，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位址，徹底地搜尋整張圖，直到找到結果為止。
以臨接鍊錶作為儲存結構，結合其儲存特點和上面兩種演算法思想，給出兩種遍歷步驟：
（1）既然圖中沒有確定的開始頂點，那麼可從圖中任一頂點出發，不妨按編號的順序，先從編號小的頂點開始。
（2）要遍歷到圖中所有頂點，只需多次呼叫從某一頂點出發遍歷圖的演算法。所以，下面只考慮從某一頂點出發遍歷圖的問題。
（3）為了在遍歷過程中便於區分頂點是否已經被訪問，設定乙個訪問標誌陣列 visited[n]，n為圖中頂點的個數，其初值為0，當被訪問過後，其值被置為1。
（4）這就是遍歷次序的問題，圖的遍歷通常有深度優先遍歷和廣度優先遍歷兩種方式，這兩種遍歷次序對無向圖和有向圖都適用。
1、深度優先遍歷從圖中某頂點v出發進行深度優先遍歷的基本思想是：
（1）訪問頂點v；
（2）從v的未被訪問的鄰接點中選取乙個頂點w，從w出發進行深度優先遍歷；
（3）重複上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。
2、廣度優先遍歷從圖中某頂點v出發進行廣度優先遍歷的基本思想是：
（1）訪問頂點v；
（2）依次訪問v的各個未被訪問的鄰接點v1，v2，……vk；
（3）分別從v1，v2，……vk出發依次訪問它們未被訪問的鄰接點， 並使「先被訪問頂點的鄰接點」先於「後被訪問頂點的鄰接點」被訪問，直至圖中所有與頂點v有路徑的頂點都被訪問到。廣度優先遍歷圖是以頂點v為起始點，由近至遠，依次訪問和v有路徑相通而且路徑長度為1，2，……的頂點。為了使「先被訪問頂點的鄰接點」先於「後被訪問頂點的鄰接點」被訪問，需設定佇列儲存訪問的頂點。
五附錄**解析：
#define maxvex 100
int visited[maxvex];
int n;
struct edgenode;連線結點的儲存型別
struct vexnode;陣列結點型別
/*bfs遍歷時所需儲存型別*/
struct queue;
typedef vexnode adjlist[maxvex];
採用使用者交換模式來建立臨接鍊錶：
void creatgroup(adjlist&g,int&n)
/*建立臨接鍊錶，建立的是有向圖*/
for(int i=0;i printf("第%d條邊=>\n\t起點序號，終點序號：",i+1);
cin>>s>>d;//表示弧由s指向d
edgenode*p=new edgenode;
每乙個點的臨接結點沒有順序，為了插入p->adjvex方便每次插入結點都插入在臨接表的首位置，這樣後插入的結點反而在前面*/
p->adjvex=d; p->info=g[d].data; p->next=g[s].link; g[s].link=p;
}void dfs(adjlist g,int v)
}/*廣度優先搜尋法(類似於樹的層次遍曆法)*/
void bfs(adjlist g,int v)
p=g[>adjvex].link;
}}心得體會：
資料結構顧名思義講求的是一種儲存結構，一路走來先後學習了表、樹，最後學習的是圖，對於每種儲存結構學習之初都會學習一些基本操作，而操作之中又以建立和遍歷為最基本的操作，只有熟練掌握了以後才能對其他操作進行研究和學習。
圖的儲存結構相比表和樹都要複雜，其操作過程也較難進行掌握。僅僅是建立圖的儲存結構便分為矩陣、臨接鍊錶、十字鍊錶等，對於每一種儲存結構又分為有向與無向之分。然而，深度優先和廣度優先是兩種演算法，其演算法思想並不依賴與元素的儲存方式，也就是說演算法思想不會因為儲存結構的改變而發生改變，當然對於不同的儲存結構僅僅是**的表現形式不同而已，正所謂一同百通，只要熟悉儲存結構的特點又對演算法思想爛熟於心便可無往不勝。
圖的遍歷實驗報告資料結構
華北電力大學 實驗報告 實驗名稱圖的遍歷 課程名稱演算法與資料結構試驗 專業班級學生姓名 學號成績 指導教師實驗日期 一 實驗名稱 圖的遍歷 二 實驗要求 試寫出乙個利用遍歷圖的方法輸出一條無向圖g中從頂點vi到vj長度為l的簡單路徑的程式。三 實驗內容 建立乙個圖，並分別用深度優先搜尋和廣度優先搜...
圖的實驗報告 1
1.實驗題目 編寫乙個程式，用來建立圖的鄰接表儲存並在此基礎上實現圖的深度優先遍歷，廣度優先遍歷。2.需求分析 本演示程式在c free環境下編寫除錯，完成圖的鄰接表儲存圖的深度和廣度優先遍歷。1 輸入的形式和輸入值得範圍 執行圖的建構函式時需要輸入圖的頂點數和邊數以及每條邊的關聯定點編號。執行輸出...
UML實驗類圖實驗報告
南京資訊工程大學實驗 實習 報告 實驗名稱類實驗 實習 日期 2014.05.10 得分指導老師 系計算機專業軟體工程班級 3班姓名學號 一 實驗目的 1 理解類的基本概念。2 掌握如何從需求分析中抽象出類的方法。3 掌握在rational rose中繪製類的操作方法。二 實驗器材 1 計算機一台。...