圖基礎(chǔ)

一、圖的定義

在數(shù)學(xué)中，圖是描述于一組對(duì)象的結(jié)構(gòu)，其中某些對(duì)象對(duì)在某種意義上是“相關(guān)的”。這些對(duì)象對(duì)應(yīng)于稱為頂點(diǎn)的數(shù)學(xué)抽象（也稱為節(jié)點(diǎn)或點(diǎn)），并且每個(gè)相關(guān)的頂點(diǎn)對(duì)都稱為邊（也稱為鏈接或線）。通常，圖形以圖解形式描繪為頂點(diǎn)的一組點(diǎn)或環(huán)，并通過邊的線或曲線連接。圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間的連線（邊）的集合組成，通常表示為G=(V, E)，其中G表示一個(gè)圖，V(G)代表圖G中的頂點(diǎn)集合，E(G)代表圖G中的邊集合。

二、圖的相關(guān)概念

1. 階：圖G中點(diǎn)集V的大小稱作圖G的階。

2. 子圖：當(dāng)圖G’=(V’,E’)，其中V’包含于V，E’包含于E，則G’稱作圖G=(V,E)的子圖。每個(gè)圖都是本身的子圖。

3. 生成子圖：指滿足條件V(G’)=V(G)的G的子圖G’。

4. 導(dǎo)出子圖：

   • 以圖G的頂點(diǎn)集V的非空子集V1為頂點(diǎn)集，以兩端點(diǎn)均在V1中的全體邊為邊集的G的子圖，稱為V1導(dǎo)出的導(dǎo)出子圖。
   • 以圖G的邊集E的非空子集E1為邊集，以E1中邊關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集的G的子圖，稱為E1導(dǎo)出的導(dǎo)出子圖。

5. 度：一個(gè)頂點(diǎn)的度是指與該頂點(diǎn)相關(guān)聯(lián)的邊的條數(shù)，頂點(diǎn)v的度記作d(v)。

6. 入度和出度：對(duì)于有向圖來說，一個(gè)頂點(diǎn)的度可細(xì)分為入度和出度。一個(gè)頂點(diǎn)的入度是指與其關(guān)聯(lián)的各邊之中，以其為終點(diǎn)的邊數(shù)；出度則是相對(duì)的概念，指以該頂點(diǎn)為起點(diǎn)的邊數(shù)。

7. 自環(huán)：若一條邊的兩個(gè)頂點(diǎn)為同一頂點(diǎn)，則此邊稱作自環(huán)。

8. 路徑：從u到v的一條路徑是指一個(gè)序列v0,e1,v1,e2,v2,…ek,vk，其中ei的頂點(diǎn)為vi及vi-1，k稱作路徑的長度。如果它的起止頂點(diǎn)相同，該路徑是“閉”的，反之，則稱為“開”的。

9. 簡單路徑：如果路徑中除起始與終止頂點(diǎn)可以重合外，所有頂點(diǎn)兩兩不等，則稱為簡單路徑。

10. 行跡：如果路徑P(u,v)中的邊各不相同，則該路徑稱為u到v的一條行跡。

11. 軌道：如果路徑P(u,v)中的頂點(diǎn)各不相同，則該路徑稱為u到v的一條軌道。

12. 回路和圈：閉的行跡稱作回路（Circuit），閉的軌稱作圈（Cycle）。

13. 橋：若去掉一條邊，便會(huì)使得整個(gè)圖不連通，該邊稱為橋。

三、圖的分類

1. 無向圖和有向圖：

   • 無向圖：邊沒有方向的圖。在無向圖中，邊記作(vi,vj)，它蘊(yùn)涵著存在< vi,vj>和< vj,vi>兩條弧。若無向圖中有n個(gè)頂點(diǎn)，則最多有n(n-1)/2條弧。
   • 有向圖：給圖的每條邊規(guī)定一個(gè)方向得到的圖。在有向圖中，邊稱作弧，含箭頭的一端稱為弧頭，另一端稱為弧尾。在有向圖中，路徑也是有向的。

2. 簡單圖、多重圖、完全圖：

   • 簡單圖：圖中若不存在頂點(diǎn)到其自身的邊，并且同一條邊不會(huì)重復(fù)出現(xiàn)，這種圖稱為簡單圖。簡單圖分為簡單無向圖和簡單有向圖。
   • 多重圖：圖中某兩個(gè)頂點(diǎn)之間的邊數(shù)多于一條，或者頂點(diǎn)通過一條邊和自己關(guān)聯(lián)，這種圖稱為多重圖。多重圖分為多重?zé)o向圖和多重有向圖。數(shù)據(jù)結(jié)構(gòu)中所討論的圖一般都是簡單圖。
   • 完全圖：在無向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無向完全圖。含有n個(gè)頂點(diǎn)的無向完全圖有n(n-1)/2條邊。在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。含有n個(gè)頂點(diǎn)的有向完全圖有n(n-1)條邊。

3. 稀疏圖和稠密圖：有很少條邊或者弧的圖稱為稀疏圖，反之稱為稠密圖。稀疏和稠密都是相對(duì)而言的，并不是一個(gè)精確的數(shù)值。

四、圖的使用場景

圖是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，在多個(gè)領(lǐng)域都有廣泛的應(yīng)用：

1. 計(jì)算機(jī)科學(xué)：圖論被廣泛應(yīng)用于算法設(shè)計(jì)中，如最短路徑算法、網(wǎng)絡(luò)流算法等。此外，圖還是許多數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，如鄰接表、鄰接矩陣等。
2. 工程領(lǐng)域：在電路設(shè)計(jì)中，圖可以用來表示電路元件之間的連接關(guān)系；在機(jī)械設(shè)計(jì)中，圖可以用來表示零件之間的裝配關(guān)系。
3. 社會(huì)學(xué)：在社會(huì)網(wǎng)絡(luò)分析中，圖可以用來表示人與人之間的社會(huì)關(guān)系，如朋友關(guān)系、合作關(guān)系等。
4. 生物學(xué)：在生物信息學(xué)中，圖可以用來表示基因之間的相互作用關(guān)系、蛋白質(zhì)之間的相互作用關(guān)系等。
5. 經(jīng)濟(jì)學(xué)和金融學(xué)：圖可以用來表示不同經(jīng)濟(jì)實(shí)體之間的交易關(guān)系、投資關(guān)系等。
6. 地理信息系統(tǒng)：在GIS中，圖可以用來表示地理實(shí)體之間的空間關(guān)系，如城市之間的交通網(wǎng)絡(luò)、河流的流向等。

總的來說，圖作為一種強(qiáng)大的工具，在各個(gè)領(lǐng)域都發(fā)揮著重要的作用。通過構(gòu)建和分析圖，人們可以更好地理解和解決復(fù)雜的問題。

和圖相關(guān)的算法

圖是一種重要的數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)（或節(jié)點(diǎn)）和邊組成，用于表示對(duì)象及其相互之間的關(guān)系。以下是與圖相關(guān)的一些經(jīng)典算法：

一、圖的遍歷算法

1. 廣度優(yōu)先搜索（BFS）
   

   • 從起始節(jié)點(diǎn)開始，先訪問所有相鄰的節(jié)點(diǎn)，再依次訪問這些相鄰節(jié)點(diǎn)的未訪問過的相鄰節(jié)點(diǎn)，直到所有節(jié)點(diǎn)都被訪問過。
   • 適用于尋找最短路徑（未考慮邊權(quán)）等問題。
   • 實(shí)現(xiàn)時(shí)通常使用隊(duì)列數(shù)據(jù)結(jié)構(gòu)。

2. 深度優(yōu)先搜索（DFS）
   

   • 從起始節(jié)點(diǎn)開始，沿著一個(gè)分支盡可能深地搜索，直到該分支的末端，然后回溯到上一個(gè)節(jié)點(diǎn)，繼續(xù)搜索其他未訪問的分支。
   • 適用于解決連通性問題、路徑查找、圖的遍歷等問題。
   • 可以通過遞歸或顯式棧來實(shí)現(xiàn)。

3. A*算法

   • 啟發(fā)式搜索算法，使用啟發(fā)式函數(shù)來評(píng)估從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑成本。
   • 通過優(yōu)先隊(duì)列來選擇下一個(gè)要訪問的節(jié)點(diǎn)，以找到最短路徑。
   • 估值函數(shù)f(n)=g(n)+h(n)，其中g(shù)(n)是從起始搜索點(diǎn)到當(dāng)前點(diǎn)的代價(jià)，h(n)是當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估值。

二、最短路徑算法

1. Dijkstra算法

   • 解決單源最短路徑問題，即求出給定頂點(diǎn)到其他任一頂點(diǎn)的最短路徑。
   • 適用于加權(quán)圖，且圖中不包含負(fù)權(quán)邊。
   • 算法依據(jù)最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)，從起點(diǎn)開始，每一步都走最短的路徑，并不斷更新每個(gè)點(diǎn)到起點(diǎn)的最短距離。

2. Bellman-Ford算法

   • 解決含負(fù)權(quán)圖的單源最短路徑問題。
   • 通過連續(xù)進(jìn)行松弛操作來更新最短路徑估計(jì)值。
   • 如果在n-1次松弛后還能更新，則說明圖中有負(fù)環(huán)，因此無法得出結(jié)果。

3. Floyd-Warshall算法

   • 解決任意兩點(diǎn)間的最短路徑問題。
   • 適用于所有類型的圖，包括有向圖和帶負(fù)權(quán)邊的圖。
   • 算法通過考慮最佳子路徑來得到最佳路徑，使用鄰接矩陣來儲(chǔ)存邊。

三、最小生成樹算法

1. Prim算法

   • 在加權(quán)連通圖中搜索最小生成樹。
   • 從任意一個(gè)頂點(diǎn)開始，逐步擴(kuò)展生成樹，每次選擇權(quán)值最小的連接新頂點(diǎn)和生成樹中頂點(diǎn)的邊。

2. Kruskal算法

   • 另一種求加權(quán)連通圖的最小生成樹的算法。
   • 基于貪心策略，首先將所有邊按權(quán)值從小到大排序，然后依次選擇邊，如果選擇的邊不會(huì)形成環(huán)，則將其加入生成樹中。

四、圖匹配算法

• 匈牙利算法

  • 在多項(xiàng)式時(shí)間內(nèi)求解任務(wù)分配問題的組合優(yōu)化算法。
  • 用于求解指派問題（assignment problem），算法時(shí)間復(fù)雜度為O(n^3)。
  • 適用于二分圖的最大匹配問題。

五、網(wǎng)絡(luò)流算法

• Ford-Fulkerson算法

  • 用于計(jì)算流網(wǎng)絡(luò)中的最大流量。
  • 流網(wǎng)絡(luò)是一個(gè)有向圖，其中每條邊都有一個(gè)非負(fù)容量。
  • 算法通過尋找增廣路徑來不斷更新流量，直到無法再找到增廣路徑為止。

這些算法在圖論和網(wǎng)絡(luò)分析中有著廣泛的應(yīng)用，包括網(wǎng)絡(luò)路由、社交媒體分析、推薦系統(tǒng)等領(lǐng)域。根據(jù)具體問題的需求和圖的結(jié)構(gòu)特性，可以選擇合適的算法來解決問題。