圖（Graph）是數據結構中一種非常重要的非線性結構，它比樹形結構更為復雜。圖中結點之間的關系可以是任意的，任意兩個數據元素之間都可能相關。本章主要介紹圖的基本概念、存儲結構、遍歷算法以及在數據處理中的典型應用。

一、圖的基本概念
圖G由兩個集合V和E組成，記為G=(V, E)，其中V是頂點的有窮非空集合，E是V中頂點偶對（稱為邊）的有窮集合。圖分為有向圖和無向圖。相關重要概念包括：頂點、邊、度、路徑、連通圖、生成樹等。掌握這些概念是理解后續算法和應用的基礎。

二、圖的存儲結構
圖的存儲結構主要有兩種：鄰接矩陣和鄰接表。

1. 鄰接矩陣：使用一個二維數組來表示圖中頂點間的相鄰關系。對于無向圖，矩陣對稱且實現簡單，直觀體現頂點連接，但稀疏圖時空間浪費較大。
2. 鄰接表：為每個頂點建立一個單鏈表，鏈表中結點表示與該頂點相鄰的邊。這種結構尤其適用于稀疏圖，能有效節省存儲空間，但判斷任意兩頂點間是否有邊不如鄰接矩陣方便。
在實際數據處理中，應根據圖的具體特征（稠密或稀疏）和主要操作來選擇存儲結構。

三、圖的遍歷算法
與樹的遍歷類似，圖的遍歷是從圖中某一頂點出發，系統地訪問圖中所有頂點，且使每個頂點僅被訪問一次。主要算法有：

1. 深度優先搜索（DFS）：類似于樹的先序遍歷，它沿著圖的某一分支深入探索直到盡頭，再回溯探索其他分支。DFS通常借助遞歸或棧實現，可用于檢測圖的連通性、尋找路徑等。
2. 廣度優先搜索（BFS）：類似于樹的層序遍歷，它從起始頂點開始，依次訪問其所有鄰接點，然后再按訪問順序訪問它們的鄰接點。BFS通常借助隊列實現，常用于尋找最短路徑（在無權圖中）。
遍歷是許多圖算法的基礎，在數據處理中用于探索數據元素間的關聯關系。

四、圖在數據處理中的典型應用
圖結構非常適合表示數據之間的復雜關系，在數據處理領域有廣泛應用。

1. 最短路徑問題：例如在交通網絡、通信網絡或社交網絡中尋找兩點間的最優路徑。經典算法有迪杰斯特拉（Dijkstra）算法（單源、權值非負）和弗洛伊德（Floyd）算法（多源）。
2. 最小生成樹：在保證網絡連通的前提下，尋找使總成本（如線路長度、建設費用）最低的連接方案。典型算法有普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法，廣泛應用于網絡設計、電路布線等。
3. 拓撲排序與關鍵路徑：用于有向無環圖（DAG）。拓撲排序解決活動調度問題（如課程安排、任務執行順序）。關鍵路徑（AOE網）則用于估算項目完成的最短時間，找出影響整體進度的關鍵活動，是項目管理中的重要工具。
4. 網絡流與匹配問題：用于資源分配、運輸優化等，如最大流算法可用于分析交通流量、數據流傳輸能力。

五、
圖是一種強大的建模工具，能夠直觀且有效地表示現實世界中實體間的復雜聯系。理解圖的基本結構、掌握其核心遍歷與算法，并學會將其應用于解決最短路徑、最優連接、任務調度等實際問題，是進行高效數據處理和算法設計的關鍵能力。在實際應用中，應根據數據特性和問題需求，靈活選擇圖的表示方法與解決算法。