圖的定義與術(shù)語

?

讓編程改變世界

Change the world by program

---

? 在前邊講解的線性表中，每個元素之間只有一個直接前驅(qū)和一個直接后繼，在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間是層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素相關(guān)，但只能和上一層中一個元素相關(guān)。 ? 但這僅僅都只是一對一，一對多的簡單模型，如果要研究如人與人之間關(guān)系就非常復(fù)雜了。 萬惡圖為首，前邊可能有些童鞋會感覺樹的術(shù)語好多，可來到了圖這章節(jié)，你才知道什么叫做真正的術(shù)語多！ ?

圖的定義

? 圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。 ? 對于圖的定義，我們需要明確幾個注意的地方：

線性表中我們把數(shù)據(jù)元素叫元素，樹中叫結(jié)點，在圖中數(shù)據(jù)元素我們則稱之為頂點(Vertex)。

線性表可以沒有數(shù)據(jù)元素，稱為空表，樹中可以沒有結(jié)點，叫做空樹，而圖結(jié)構(gòu)在咱國內(nèi)大部分的教材中強(qiáng)調(diào)頂點集合V要有窮非空。

線性表中，相鄰的數(shù)據(jù)元素之間具有線性關(guān)系，樹結(jié)構(gòu)中，相鄰兩層的結(jié)點具有層次關(guān)系，而圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系，頂點之間的邏輯關(guān)系用邊來表示，邊集可以是空的。

?

圖的各種奇葩定義

?

無向邊：若頂點Vi到Vj之間的邊沒有方向，則稱這條邊為無向邊(Edge)，用無序偶(Vi,Vj)來表示。

上圖G1是一個無向圖，G1={V1,E1}，其中

• V1={A,B,C,D}，
• E1={(A,B),(B,C),(C,D),(D,A),(A,C)}

?

有向邊：若從頂點Vi到Vj的邊有方向，則稱這條邊為有向邊，也成為弧(Arc)，用有序偶<Vi,Vj>來表示，Vi稱為弧尾，Vj稱為弧頭。

上圖G2是一個無向圖，G2={V2,E2}，其中

• V2={A,B,C,D}，
• E2={<B,A>,<B,C>,<C,A>,<A,D>}

?

簡單圖：在圖結(jié)構(gòu)中，若不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡單圖。

以下兩個則不屬于簡單圖： ?

無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。含有n個頂點的無向完全圖有n*(n-1)/2條邊。

?

有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有n個頂點的有向完全圖有n*(n-1)條邊。

?

稀疏圖和稠密圖：這里的稀疏和稠密是模糊的概念，都是相對而言的，通常認(rèn)為邊或弧數(shù)小于n*logn（n是頂點的個數(shù)）的圖稱為稀疏圖，反之稱為稠密圖。

?

有些圖的邊或弧帶有與它相關(guān)的數(shù)字，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)(Weight)，帶權(quán)的圖通常稱為網(wǎng)(Network)。

? 假設(shè)有兩個圖G1=(V1,E1)和G2=(V2,E2)，如果V2?V1，E2?E1，則稱G2為G1的子圖(Subgraph)。 [buy]?獲得所有教學(xué)視頻、課件、源代碼等資源打包?[/buy] [Downlink href='http://kuai.xunlei.com/d/BdsUAwJ47wDRc3lRd20']視頻下載[/Downlink]

轉(zhuǎn)載于:https://www.cnblogs.com/LoveFishC/archive/2013/04/26/3847305.html

總結(jié)

以上是生活随笔為你收集整理的图的定义与术语 - 数据结构和算法54的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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