【0】README

0.1）本文總結(jié)于 數(shù)據(jù)結(jié)構(gòu)與算法分析， 旨在復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)中圖論算法的基礎(chǔ)知識；

---

【1】圖論若干相關(guān)定義

1.1）圖G定義：一個圖G=（V，E）由頂點(diǎn)及集V 和 邊集E組成， 每一條邊就是一個點(diǎn)對（v， w）；
1.2）邊鄰接：當(dāng)且僅當(dāng)（v，w）∈E， 在無向圖中， w和v鄰接，且v也和w鄰接；（還有第3中成分：邊的權(quán)值）
1.3）路徑： 一條路徑是一個頂點(diǎn)序列 w1， w2，…，wn， 使得（wi，wi+1）∈E，這樣一條路徑長是該路徑上的邊數(shù)；
1.4）簡單路徑：其上的所有頂點(diǎn)都是互異的，但第一個頂點(diǎn)和最后一個頂點(diǎn)可能相同；
1.5）連通圖（對于無向圖而言）： 如果在一個無向圖中從每一個頂點(diǎn)到每個其他頂點(diǎn)都存在一條路徑，則稱該無向圖是連通的；
1.6）強(qiáng)連通圖（對于有向圖而言）：具有無向圖連通性質(zhì)的有向圖稱為是強(qiáng)連通的；
1.7）基礎(chǔ)圖：去掉有向圖上的方向所形成的圖；
1.8）弱連通圖：如果有向圖不是強(qiáng)連通的， 但基礎(chǔ)圖是連通的， 那么該圖稱為是弱連通的；
1.9）完全圖： 是指每一對頂點(diǎn)間都存在一條邊的圖；

---

【2】圖的表示

2.1）鄰接矩陣：對于每條邊（u， v）， 我們設(shè)置 A[u][v]=1，否則數(shù)組的元素為0；如果邊是有權(quán)的，設(shè)置A[u][v] 等于該權(quán)值 且用一個很大或者很小的權(quán)作為標(biāo)記表示不存在的邊；（∞）

• 2.1.1）鄰接表的空間需求是 Θ(|V|^2)；如果圖是稠密的：|E| = Θ(|V|^2) ， 則鄰接矩陣是合適的表示方法；如果在大部分應(yīng)用中，圖都是稀疏的；

2.2）鄰接表（圖的標(biāo)準(zhǔn)表示方法）：如果圖是稀疏的， 則使用鄰接表來表示。對每一個頂點(diǎn)，我們使用一個表存放所有鄰接的頂點(diǎn)。此時的空間需求為 O（|E| + |V|）；

• 2.2.1）引入散列表：在應(yīng)用中，頂點(diǎn)都是名字而不是數(shù)字， 這些名字在編譯時是未知的。由于我們不能夠通過未知名字為一個數(shù)組做索引， 因此我們必須提供從名字到數(shù)字的映射。完成這項(xiàng)工作最容易的 方法是使用散列表， 在該散列表中我們對每個頂點(diǎn)存儲一個名字以及一個范圍在1到 |V| 之間的內(nèi)部編號；
• 2.2.2）鄰接表的一個荔枝：

總結(jié)

以上是生活随笔為你收集整理的图论算法基础的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。