- 線性結構中，元素僅有線性關系，每個元素只有一個直接前驅和直接后繼；
- 樹形結構中，資料元素（結點）之間有著明顯的層次關系，每層上的元素可能和下一層中多個元素相關，但只能和上一層中一個元素相關；
- 圖形結構中，資料元素（頂點）之間具有任意關系，圖中任意兩個資料元素之間都可能相關，
(1) 圖的定義
圖是由頂點的有窮非空集合和頂點之間邊的集合組成， 通常表示為: G（V，E）， 其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合，
無向邊：若頂點Vi到Vj之間的邊沒有方向，則稱這條邊為無向邊，用無序偶對(Vi，Vj) 來表示，如下左圖，G= (V1,{E1})，其中頂點集合V1={A，B，C，D}; 邊集合E1={ (A,B) ，（B,C），(C,D)， (D,A) , (A,C) } ，圓括號有向邊：若從頂點Vi 到Vj的邊有方向，則稱這條邊為有向邊，也稱為弧，用有序偶〈Vi,Vj>來表示， Vi稱為弧尾， Vj稱為弧頭， 如果圖中任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖，連接頂點A到D的有向邊就是弧，A是弧尾，D是弧頭，<A, D>表示弧，注意不能寫成<D， A>，如下右圖，G= (V2,{E2})，其中頂點集合V2={A，B，C，D}; 弧集合E2={<A，D>，<B，A>，<C，A>，<B，C>}，尖括號
(2) 圖的基本術語
子圖：假設有兩個圖G= (V，{E})和G'= (V'，{E'})，如果V'是V的子集，且E'是E的子集，則稱G'為G的子圖，如下圖帶底紋的圖均為左側無向圖與有向圖的子圖，
無向完全圖和有向完全能圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖，含有n個頂點的無向完全圖有n(n-1)/2條邊，在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩潭訓，則稱該圖為有向完全圖，含有n個頂點的有向完全圖有n (n-1) 條邊，
稀疏圖和稠密圖：有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖，這里的概念是相對而言的，
權和網：有些圖的邊或弧具有與它相關的數字，這種與圖的邊或弧相關的數叫做權，這些權可以表示從一個頂點到另一個頂點的距離或耗費，這種帶權的圖通常稱為網，如下圖就是一張帶權的圖，即標識中國四大城市的直線距離的網，此圖中的權就是兩地的距離，
鄰接點：對于無向圖G= (V,{E})， 如果邊(v,v')屬于E， 則稱頂點v和v‘互為鄰接點，即v和v'相鄰接、邊(v,v')依附于頂點v和v'，或者說(v,v')與頂點v和v'相關聯，
度、入度和出度：點v的度是和v相關聯的邊的數目，記為TD(v)，如上圖左側上方的無向圖，頂點A與B互為鄰接點，邊(A，B) 依附于頂點A 與B 上，頂點A 的度為3，而此圖的邊數是5，各個頂點度的和=3+2+3+2=10，推敲后發現，邊數其實就是各頂點度數和的一半，多出的一半是因為重復兩次計數，
對于有向圖G= (V,{E})，如果弧<v,v'>屬于E，則稱頂點v鄰接到頂點v'，頂點v'鄰接自頂點v的弧<v,v'>和頂點v， v'相關聯，以頂點v為頭的弧的數自稱為v的入度
，記為ID (v); 以v為尾的弧的數目稱為v的出度，記為OD (v); 頂點v的度為TD(v) =ID(v) +OD (v)，上圖 左側下方的有向圖，頂點A的入度是2 (從B到A的弧，從C到A的弧)，出度是1 (從A到D的弧)，所以頂點A 的度為2+1=3，此有向圖的弧有4 條，而各頂點的出度和=1+2+1+0=4，各頂點的入度和=2+0+1+1=4，路徑和路徑的長度*：從頂點v 到頂點v'的路徑是一個頂點序列，路徑的長度是路徑上的邊或弧的數目，有向圖的路徑也是有向的，
回路或環：第一個頂點到最后一個頂點相同的路徑稱為回路或環，
簡單路徑、簡單回路或簡單環：序列中頂點不重復出現的路徑稱為簡單路徑，除了第一個頂點和最后一個頂點之外，其余頂點不重復出現的回路，稱為簡單回路或簡單環，如下圖，左側的環因第一個頂點和最后一個頂點都是B，且C、 D、 A沒有重復出現，因此是一個簡單環， 而右側的環，由于頂點C的重復，它就不是簡單環，
10.連通、連通圖和連通分量：在無向圖G中，如果從頂點v到頂點v'有路徑，則稱v和v'是連通的， 如果對于圖中任意兩個頂點vi、vj ∈E， vi，和vj都是連通的，則稱G是連通圖， 下圖的圖1，它的頂點A到頂點B、 C、 D都是連通的，但顯然頂點A與頂點E或F就無路徑，因此不能算是連通圖，而圖2，頂點A、 B、 C、D相互都是連通的，所以它本身是連通圖，
無向圖中的極大連通子圖稱為連通分量，注意連通分量的概念，它強調:
- 要是子圖；
- 子圖要是連通的；
- 連通子圖含有極大頂點數；
- 具有極大頂點數的連通子圖包含依附于這些頂點的所有邊，
上圖中，圖1是一個無向非連通圖， 但是有兩個連通分量，即圖2和圖3，而圖4，盡管是圖1的子圖，但是它卻不滿足連通子圖的極大頂點數(圖2滿足)， 因此它不是圖1的無向圖的連通分量，11.強連通圖和強分量：在有向圖G中，如果對于每一對vi，vj屬于E，vi不等于vj，從vi到vj和vj 到vi都有路徑，則稱G是強連通圖，有向圖中的極大強連通子圖稱作有向圖的強連通分量，
12.連通圖的生成樹：一個極小的連通子圖， 它含有圖中全部的n 個頂點，但只有足以構成一棵樹的n-1條邊，比如下圖的圖1是一普通圖，但顯然它不是生成樹，當去掉兩條構成環的邊后，比如圖2 或圖3，就滿足n個頂點n-1條邊且連通的定義了， 它們都是一棵生成樹，從這里也可知道，如果一個圖有n 個頂點和小于n-1條邊，則是非連通圖，如果多于n-1 邊條，必定構成一個環， 因為這條邊使得它依附的那兩個頂點之間有了第二條路徑，比如圖2 和圖3，隨便加哪兩頂點的邊都將構成環， 不過有n-1條邊并不一定是生成樹，比如圖4，
13.有向樹和生成森林：如果一個有向圖恰有一個頂點的入度為0，其余頂點的入度均為1，則是一棵有向樹，對有向樹的理解比較容易，所謂入度為0其實就相當于樹中的根結點， 其余頂點入度為1就是說樹的非根結點的雙親只有一個，一個有向圖的生成森林由若干棵有向樹組成， 含有圖中全部頂點，但只有足以構成若干棵不相交的有向樹的弧， 如下圖的圖1 是一棵有向圖，去掉一些弧后，它可以分解為兩棵有向樹，如圖2和圖3，這兩棵就是圖1有向圖的生成森林，
鏈接：https://www.jianshu.com/p/d9ca383e2bd8
來源：簡書
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/521827.html
標籤：其他
上一篇：現在入行Java真的還有出路嗎？