摘 要 本課程設計主要解決圖的搜尋實現，通過圖的鄰接矩陣實現深度優先搜尋和廣度優先搜尋。圖是一種較線形表和樹更復雜的資料結構，其應用極為廣泛，目前已滲入到語言學，邏輯學，物理，化學以及計算機科學等諸多領域中。在本課程設計中，系統開發平臺為Windows xp，程式設計設計語言主要採用C語言，程式執行平臺為Windows 2000/XP。程式開始後，通過輸入各結點與邊的相關資料，可以得出相應的深度優先和廣度優先搜尋結果。
關鍵詞 程式設計；C語言；圖的鄰接矩陣；圖的深度優先搜尋、廣度優先搜尋
1 引 言
圖是一種較複雜的資料結構，圖的搜尋在圖書索引，城市道路建設，人工智慧等領域中發揮著重要作用。圖的搜尋有深度優先搜尋和廣度優先搜尋，我們可以通過圖的鄰接矩陣或鄰接表實現圖的這兩種搜尋。
本次程式設計我們通過C語言編寫程式實現圖的搜尋。在編寫過程中我們將圖定義為鄰接矩陣型別，通過深度優先搜尋遍歷和廣度優先搜尋遍歷分別實現圖的搜尋。
我們學習兩年的有關C語言和資料結構的相關知識，而課程設計是將我們把所學的理論和生產實踐相結合的重要環節， 通過這次課程設計，可以使我們所學的專業技能得到鞏固、擴大、深入和系統化；培養綜合運用所學知識解決圖的搜尋的能力，初步掌握資料結構程式設計的方法和步驟；使我們進一步提高編寫程式的效率；提高我們獨立鑽研問題的能力，培養嚴肅認真，實事求是，刻苦鑽研的工作作風。
2 開發工具介紹
C 語言是1972年由美國的Dennis Ritchie設計發明的, 並首次在UNIX作業系統DEC PDP-11 計算機上使用。 它由早期的程式語言 BCPL( Basic Combind Programming Language) 發展演變而來。在1970年, AT&T 貝爾實驗室的 Ken Thompson根據BCPL語言設計出較先進的並取名為 B的語言, 最後導了C 語言的問世。 隨著微型計算機的日益普及, 出現了許多C語言版本。由於沒有統一的標準, 使得這些C 語言之間出現了一些不一致的地方。為了改變這種情況, 美國國家標準研究所(ANSI)為C 語言制定了一套ANSI標準,成為現行的C語言標準。
C語言具有強大的功能，它具有以下特點：
1. C是中級語言
它把高階語言的基本結構和語句與低階語言的實用性結合起來。C 語言可以象組合語言一樣對位、位元組和地址進行操作, 而這三者是計算機最基本的工作單元。
2. C是結構式語言
結構式語言的顯著特點是程式碼及資料的分隔化, 即程式的各個部分除了必要的資訊交流外彼此獨立。這種結構化方式可使程式層次清晰, 便於使用、維護以及除錯。C
語言是以函式形式提供給使用者的, 這些函式可方便的呼叫, 並具有多種迴圈、條件語句控制程式流向, 從而使程式完全結構化。
3. C語言功能齊全
C 語言具有各種各樣的資料型別, 並引入了指標概念, 可使程式效率更高。另外C 語言也具有強大的圖形功能,
支援多種顯示器和驅動器。而且計算功能、邏輯判斷功能也比較強大, 可以實現決策目的。
4. C語言適用範圍大
C 語言還有一個突出的優點就是適合於多種作業系統, 如DOS、UNIX,也適用於多種機型。
3 相關知識
圖的概念：圖是一種較線形表和樹更復雜的資料結構，是一種資料元素間為多對多關係的資料結構，加上一組基本操作構成的抽象資料型別，圖作為一種非線性資料結構，被廣泛應用於多個技術領域，諸如系統工程、化學分析、統計力學、遺傳學、控制論、計算機的人工智慧、編譯系統等領域。
圖的基本操作：建立、插入、刪除、查詢等。
圖的幾種儲存結構型別：圖的鄰接矩陣表示法，圖的'鄰接表表示法
深度優先搜尋（DFS）:a、深度優先搜尋類似於樹的前序遍歷，也是一遇到頂點就進行訪問。其特點是儘可能先對縱深方向進行搜尋，因此很容易用遞迴演算法實現。如果將遍歷過程中走過的邊連線起來，即可得到深度優先遍歷生成樹。b、深度優先搜尋遍歷圖的演算法：首先訪問指定的起始頂點v0，從v0出發，訪問v0的一個未被訪問過的鄰接頂點w1，再從w1出發，訪問w1的一個未被訪問過的頂點w2，然後從w2出發，訪問w2的一個未被訪問過的鄰接頂點w3。依次類推，直到一個所有鄰接頂點都被訪問過為止。
廣度優先搜尋（BFS）:廣度優先搜尋類似於樹的按層次遍歷。首先訪問指定的起始點v0，從v0出發，訪問v0的所有未被訪問過的鄰接頂點w1，w2，… wk，然後再依次從w1，w2，… wk出發，訪問它們的所有未被訪問過的鄰接頂點，依次類推，直到圖中所有未被訪問過的鄰接頂點都被訪問過為止。廣度優先遍歷的特點是儘可能進行橫向搜尋，即最先訪問的頂點其鄰接點也被先訪問。因此，藉助一個佇列來儲存已被訪問過的頂點序列。訪問一個頂點vi時（出隊），同時將vi相鄰的其餘結點入隊。每個頂點只能入隊一次。
4 程式的設計與實現
4．1 程式相關演算法虛擬碼[3]
圖的深度優先搜尋演算法虛擬碼：
DFS（v）//訪問由v到達的所有頂點
1. Visited(v)=1;
2. for鄰接於v的每個頂點w do
3． if Visited(w)=0 then
4. DFS(w);
5. endif
6. endfor
7．end DFS
圖的廣度優先搜尋演算法虛擬碼：
BFS(v) //寬度優先搜尋G，從頂點v開始執行
// 所有已搜尋的頂點i都標記為Visited(i)=1.
//Visited的初始分量值全為0
1. Visited(v)=1; u＝v;
2. Q=[];//將Q初始化為空佇列
3. loop
4. for 鄰接於u的所有頂點w do
5. if Visited(w)=0 then
6. AddQ(w,Q); //將w放於佇列Q之尾
7. Visited(w)=1;
8