iT邦幫忙

1

【資料結構】圖的基本定義

一個圖形具有兩個集合的基本組成:G(V,E)

  • V:表示頂點的集合

      V(G1)={1,2,3,4}
    
  • E:表示邊的集合

      E(G1)={(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(2,3)}
    

圖1

無向圖與有向圖

  • 無向圖:圖的邊不具有方向性

      (V0,V1)=(V1,V0)
    

圖2

  • 有向圖:圖的邊具有方向性

      <V0,V1>!=<V1,V0>
    

    <u,v>表示u-->v

          u是邊的尾巴
          v是邊的頭
    

圖3

圖的限制

  • 自我邊:從同一個頂點出發,連接到自己
  • 重複邊:兩個頂點重複連接

圖4
圖6

完全圖

一個圖形有最大的邊數量

設頂點數為n
    無向圖:n(n-1)
    有向圖:n(n-1)/2

圖5

鄰近與附接

子圖

屬於圖的子集合為子圖

圖7

路徑相關

路徑:從頂點到頂點所經過的邊

長度:路徑上的邊數目

圖8

除了第一個點和最後一個點,其餘經過頂點不重複為簡單路徑,當第一個點和最後一個點相同時可稱為迴圈

強連結組件

強連結:在有向圖中,點u連向v,點v連向u

強連結組:具有強連結的最大子圖

圖9

分支度

該頂點附接的邊數量
有向圖:

  • in-degree:以頂點作為箭頭的數量
  • out-degree:以頂點作為箭尾的數量

圖10


尚未有邦友留言

立即登入留言