熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構之圖的概念[1]

2013-11-15 15:40:43  來源: 數據結構 

三種數據結構比較

  線性表數據元素之間僅有線性關系每個數據元素只有一個直接前驅和一個直接後繼
  樹形結構數據元素之間有著明顯的層次關系並且每一層上的數據元素可能和下一層中多個元素相關但只能和上一層中一個元素相關
  圖形結構結點之間的關系可以是任意的圖中任意兩個元素之間都可能相關

圖的基本術語

  圖(Graph)圖G由兩個集合V和E組成記為G=(VE)這裡V是頂點的有窮非空集合E是邊(或弧)的集合而邊(或弧)是V中頂點的偶對
  頂點(Vertex)圖中的結點又稱為頂點
  邊(Edge)相關頂點的偶對稱為邊


  有向圖(Digraph)若圖G中的每條邊都是有方向的則稱G為有向圖
  弧(Arc)又稱為有向邊在有向圖中一條有向邊是由兩個頂點組成的有序對有序對通常用尖括號表示
  弧尾(Tail)邊的始點
  弧頭(Head)邊的終點 
 


  無向圖(Undigraph)若圖G中的每條邊都是沒有方向的則稱G為無向圖
  無向完全圖(Undirected Complete Graph)恰好有n(n)/的無向圖
  有向完全圖(Directed Complete Graph)恰好有n(n)條弧的有向圖
  鄰接點(Adjacent)若(vivj)是一條無向邊則稱頂點vi和vj互為鄰接點
  度(Degree)無向圖中頂點v的度是關聯於該頂點的邊的數目記為TD(v)
  入度(Indegree)若G為有向圖則把以頂點v為終點的邊的數目稱為v的入度記為ID(v)
  出度(Outdegree)若G為有向圖則把以頂點v為始點的邊的數目稱為v的出度記為OD(v)
  對於有向圖TD(v)=ID(v)+OD(v) 

 
  子圖(Subgraph)設G=(VE)是一個圖若E是E的子集V是V的子集使得E中的邊僅與V中頂點相關聯則圖G=(VE)稱為圖G的子圖
  路徑(Path)無向圖G=(VE)中從頂點v到頂點v的路徑是一個頂點序列(v=vivivin=v)其中(vijvij)∈E≤j≤n有向圖G=(VE)中從頂點v到頂點v的路徑是一個頂點序列(v=vivivin=v)其中〈vijvij〉∈E≤j≤n
  簡單路徑序列中頂點不重復出現的路徑
  環(Cycle)又稱回路第一個頂點和最後一個頂點相同的路徑
  簡單回路又稱簡單環除了第一個頂點和最後一個頂點外其余頂點不重復的回路
連通在無向圖G中如果從頂點v到頂點v有路徑則稱v和v是連通的

[]  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23784.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.