您當前位置：首頁 > 數據庫 > 數據庫應用 > 數據結構 - 圖的基本術語

數據結構 - 圖的基本術語

來源：程序員人生發布時間：2015-08-21 09:02:32 閱讀次數：3527次

圖(Graph)概念

 圖(Graph)是1種比線性表和樹更加復雜的數據結構。
   線性結構：研究數據元素之間的1對1關系。除第1個和最后1個元素外，任何1個元素都有唯1的1個直接先驅和直接后繼。
   樹結構：是研究數據元素之間的1對多的關系。每一個元素對下(層)可以有0個或多個元素相聯系，對上(層)只有唯1的1個元素相干，數據元素之間有明顯的層次關系。

圖結構：研究數據元素之間的多對多的關系。在這類結構中，任意兩個元素之間可能存在關系。即結點之間的關系可以是任意的，圖中任意元素之間都可能相干。
圖的利用極其廣泛，已滲透到諸如語言學、邏輯學、物理、化學、電訊、計算機科學和數學的其它分支。

圖的定義和術語

  圖：是由頂點構成的有窮非空集合和頂點之間邊的集合組成。通常表示為G=(V,E) 。其中：
  G：表示1個圖；
  V：G中頂點(Vertex)的集合，記為V(G)；
  E：圖G中邊的集合，記為E(G) 。

注意點：
1、圖中數據元素，稱為頂點(Vertex)（線性表：元素；樹：結點）
2、頂點集合有窮非空（線性表：空表；樹：空樹）
3、圖中任意兩個結點都可能有關系，頂點之間的邏輯關系用邊來表示。（線性表：線性關系；樹：層次關系）

無向圖（Undirected graphs）

無向圖（Undirected graphs）
無向邊：頂點v到w之間的邊沒有方向。用無序偶對(v, w)表示。

無向圖：圖中任意兩個頂點之間的邊都是無向邊。

在無向圖中，對?(v,w)?E(G) ，有(w,v)?E(G) ，即E(G)是對稱，則用 (v,w)或(w,v) 表示v和w之間的1條邊便可。

有向圖（Directed graphs）

有向邊：頂點v到w之間的邊有方向。有向邊也稱為?。ˋrc），用有序偶對（v, w）表示。 v稱為弧尾(tail)或初始點(initial node)，w稱為弧頭(head)或終點(terminal node) 。

有向圖：圖中任意兩個頂點之間的邊都是有向邊。

完全無向圖

對無向圖，若圖中頂點數為n ，邊的數目為e，則e ?[0，n(n-1)/2 ] 。
完全無向圖：具有n(n-1)/2條邊的無向圖；
即：圖中任意兩個不同的頂點間都有1條無向邊。
數學定義：
   對無向圖G=(V，E)，對?vi，vj?V ，當vi ≠vj，有<vi ,vj>?E。

安全有向圖

對有向圖，若圖中頂點數為n ，弧的數目為e，則e?[0，n(n-1)] 。
完全有向圖：具有n(n-1)條邊的有向圖；
即：圖中任意兩個不同的頂點間都存在方向相反的兩條弧。
數學定義：
        對有向圖G=(V，E)，對?vi，vj?V ，當vi ≠vj時，有<vi ,vj>?E∧<vj , vi >?E ，

有很少邊或弧的圖（e

圖的頂點與邊間關系

有向圖頂點與邊的關系：
頂點的鄰接，對有向圖G=(V ，E)，若有向弧（v,w）?E，則稱
頂點v “鄰接到”頂點w，
頂點w “鄰接自”頂點v ，
弧（v,w）與頂點v和w “相干聯” 。
頂點的入度、出度：對有向圖G=(V ，E)， ?vi ?V ，
以vi作為出發點（弧尾）的有向邊(弧)的數目稱為頂點vi的出度(Outdegree)，記為OD(vi) ；
以vi作為終點（弧頭）的有向邊(弧)的數目稱為頂點vi的入度(Indegree)，記為ID(vi) 。
頂點vi的出度與入度之和稱為vi的度，記為TD(vi) 。即
TD(vi)=OD(vi)+ID(vi)

路徑、路徑長度、回路

對無向圖G=(V，E)，若從頂點v經過若干條邊能到達w，稱頂點v和w是連通的，又稱頂點v到w有路徑(Path) 。其路徑是1個頂點序列
(v=vi0vi1…vim=w) ，vij?V且(vij⑴, vij)?E j=1,2, …,m
對有向圖G=(V，E)，從頂點v到w有有向路徑，指的是從頂點v經過若干條有向邊(弧)能到達w。即
(v=vi0vi1…vim=w) ，vij?V且（vij⑴, vij）?E j=1,2, …,m

路徑的長度：路徑上的邊或有向邊(弧)的數目。
簡單路徑：在1條路徑中，沒有重復相同的頂點；
回路(環)：第1個頂點和最后1個頂點相同的路徑；
簡單回路(簡單環)：在1個回路中，若除第1個與最后1個頂點外，其余頂點不重復出現。

連通圖、連通份量

對無向圖G=(V，E)，
如果對圖中任兩個頂點vi ，vj ?V，vi和vj都是連通的，則稱圖G是連通圖，否則稱為非連通圖。
若G是非連通圖，則極大的連通子圖稱為G的連通份量。（如果從頂點v到w有路徑，稱v和w是連通的。）
對有向圖G=(V，E)，
若?vi ，vj ?V， vi ≠vj都有從vi到 vj 和從vj到vi的有路徑，稱圖G是強連通圖，否則稱為非強連通圖。
若G是非強連通圖，則極大的強連通子圖稱為G的強連通份量。
“極大”的含義：指的是對子圖再增加圖G中的其它頂點，子圖就不再連通。

生成樹

生成樹：1個連通圖(無向圖)的生成樹是1個極小連通子圖，它含有圖中全部n個頂點和只有足以構成1棵樹的n⑴條邊，稱為圖的生成樹。
關于無向圖的生成樹的幾個結論：
1棵有n個頂點的生成樹有且唯一n⑴條邊；
如果1個圖有n個頂點和小于n⑴條邊，則是非連通圖；
如果多于n⑴條邊，則1定有環；
有n⑴條邊的圖不1定是生成樹。