graph

基本名詞
eulerian path(尤拉路徑),eulerian cycle(尤拉迴路):從某點出發,每個邊各經過一次,並回到原點
eulerian chain(尤拉串鏈):從某點出發,每個邊各經過一次即可

由頂點集合(vertex,V)與邊集合(edges,E)組成,因此圖形表示成G=(V,E)
vertex表示成V(G),由頂點組成的集合,不允許空集合
edges表示成E(G),由邊組成的集合,允許空集合

path(路徑):一組邊所形成
simple path(簡單路徑):路徑中的點只出現一次
相鄰:兩點存在一邊,稱兩點為相鄰
相連通:兩點存在一路徑,稱兩點為相連通
connected graph(連通圖):任二點都存在一個路徑的圖形,一個圖要連通至少要n-1個邊,若各點互連則邊數(n-1)n/2
connected component(連通單元):連通圖的子圖
degree(分支度):點所連接的邊數,對有向圖而言還分in degree進入分支度和out degree離去分支度
weighted graph(加權圖): 各邊皆有一個加權,表示兩點距離或成本

.............................

圖形表示法
相鄰矩陣:若有n個點則用n*n的二維矩陣表示,且對角線元素皆為0,若graph[i][j]=1表示點i和點j相連,若為加權圖則1可改成加權值,另外無向圖會對稱,有向圖不一定對稱
若點多邊少,則會成為稀疏矩陣,但若是無向圖則可只儲存對稱的另一邊以節省空間
要找多少邊,是否連通圖,都是big O(N^2),(因為要在n*n的二維矩陣找)
優點:最簡單安全的表示法
缺點:可能形成一個稀疏矩陣

相鄰串列:n個點的圖用n個鏈結串列表示,而第i個鏈結串列內的各節點=和第i個點相鄰的各點
對無向圖而言,會有n個起始頂點和2e個串列的節點,而i點的分支度=第i個鏈結串列中節點數
ps,2e個串列的節點:2*邊數=所有串列的節點加總,因為一個邊表示兩點互連,也就表示兩個點分別在自己的鏈結串列各增加一點
ps,當有向圖變為雙向時其實就成為了無向圖
對有向圖而言,會有n個起始頂點和e個串列的節點,而i點的離去分支度=第i個鏈結串列中節點數
若要找出有向圖的進入分支度則要利用反向相鄰串列協助
相鄰串列資料結構:
typedef struct node{
 int vertex;
 int count ;//若要計算該點邊數可加此一變數
 int weight; //若為加權圖可增此欄表示加權值
 struct nextnode *path;
}list;
nextnode headnode[n]; //n=點數
優點:只表示存在的邊
缺點:存取效率及安全性較差

相鄰多重串列
會有n個起始頂點和e個串列的節點,一個邊用一個節點表示
對無向圖而言,一個節點被二個鏈結串列共用
對有向圖而言,一個節點被一個鏈結串列共用(因為邊具方向性)
優點:每個邊只表示一次
缺點:串列表示最複雜

.................................

圖的走訪
depth first traversal(深度優先搜尋法):用堆疊處理頂點,以遞迴方式進行走訪
做法:先走訪起始點v,並選與v相鄰且未被走訪的點w,將其視為起始點,遞迴呼叫dfs

虛擬碼:
procedure dfs(v:integer);{
 w:integer;
 visit[v]:=true;write(v); //走訪起始點v,並紀錄點v己走訪
 for(each vertex w屬於neighbor(v))do{ //把每個點v的相鄰點都取出做以下步驟
  if(not visit[w])then{dfs(w);}
 }
}

若用相鄰矩陣則為bigO(n^2),演算法為:
void dfs_matrix(int i){ //N,matrix[][],vistied[]為全域
 int k;
 visit(i); //訪問點i
 visited[i]=1; //標示點i己被訪問過
 for(k=0;k < N;k++){
  if(matrix[i][k]==1 && !visited[k]){dfs_matrix(k);} //若有節點且沒走訪過則進行遞迴
 }
}

若用相鄰串列則為bigO(e),空間為...
演算法:
void dfs_list(int i){
 nextnode *P; int j;
 visit(i); //訪問點i
 visited[i]=1; //標示點i己被訪問過 
 p=headnode[i].nextnode;
 while(p!=null){
  j=p->vertex;
  if(!visited[j]){dfs_list(j);} //若有節點且沒走訪過則進行遞迴
  else{p=p->nextnode;}
 }
}

.......

breadth first travesal(廣度優先搜尋法):用佇列處理頂點,以迴圈方式進行走訪
做法:
1先走訪起始點v,並將v放入佇列
2從佇列取一點,走訪與該點相鄰且未走過的點放入佇列
重覆2直到佇列為空

虛擬碼:
procedure bfs(v:integer);{
 w:interger;
 q:queue;
 visit(v); visited[v]:=true; //走訪起始點v,並紀錄點v己走訪
 initialqueue(q);
 addqueue(q,v); //將點v放入佇列q
 while not emptyqueue(q)do{
  deletequeue(q,v); //從佇列q取出點v
  for(all vertex w屬於neighbor(v))do{ //把每個點v的相鄰點都取出做以下步驟
   if not visit[w] then{ //判斷該點是否己走訪
    visit[w]:=true;write(w); //走訪起始點v,並紀錄點v己走訪
    addqueue(q,w); //將點v放入佇列q
   }
  }//for
 }//while
}

若用相鄰矩陣則為bigO(n^2),演算法:
void bfs_matrix(int i){ //N,matrix[][],vistied[]為全域
 int k;
 visit(i); //訪問點i
 visited[i]=1; //標示點i己被訪問過
 addqueue(q,i);
 while(i=delqueue(q)){
  for(k=0;k < N;k++){
   if(matrix[i][k]==1 && !visited[k]){ //若有節點且沒走訪則做以下
    visit(k);visited[k]=1;addqueue(q,k);
   }
  }
 }
}

若用相鄰串列則為bigO(e),空間為...
演算法:
void bfs_list(int i){
 nextnode *P; int j;
 visit(i); //訪問點i
 visited[i]=1; //標示點i己被訪問過
 addqueue(q,i);//將點i放入佇列
 while(i=delqueue(q)){
  p=headnode[i].nextnode;
  while(p!=null){
   j=p->vertex;
   if(!visited[j]){visit(j);visited[j]=1;addqueue(q,j);} //若有節點且沒走訪過則進行遞迴
   else{p=p->nextnode;}
  }
 }
}

應用:
若可走完所有點,則為連通圖

若不是連通圖,而要決定圖形的所有連通單元,使用相鄰串列複雜度為bigO(n+e)
走訪過程中用到的邊稱為tree edges(樹邊),其餘的稱為back edges(後邊),若樹含所有點及樹邊則稱為擴張樹

............

spanning tree(擴張樹)
最小的連通子圖
說明:一個無向圖,有n個點,n-1個邊,不允許有迴路,(一張n個點的連通圖都存在對應的擴張樹)
the minimun weighted spanning tree(最小成本擴張樹):在一個加權圖的所有可能擴張樹中,所有邊的加權總和最小的擴張樹

求法:可用kruskal的演算法:此為greedy method,步驟如下:
1由邊集合中找出最小加權邊,
2檢查這個邊 加入tree後是否會形成迴路,若是則捨棄否則保留在tree內
3重覆1,2直到找完所有邊或邊集合為空為止
若用最小堆積結構表示各邊加權,對n個點e個邊的連通圖,則為bigO(e log2(e))

............

最短路徑
從點到另一點間所有可能路徑中,所有邊加權總合最小的路徑

從一點到其它所有點的最短路徑與距離
dijkstra的演算法:使用相鄰矩陣則為bigO(N^2)
資料結構:distance[1-n]表示到達點i(起始點)的最短距離(加權),path[1-n]表示點i(起始點)=點j到點i所達成
演算法:
procedure shortestpath(i){
 for(j:=1 to n)do{distance[j]:=cost[i][j];path[j]:=j}
 visit[i]:=true;
 for(all vertex j屬於neighbor(i))path[j]:=i;
 for(step:=1 to (n-1))do{
  for(all vertex j屬於not visit[j])choose a vertex K with a minimal distance; //每次執行都是還沒參觀過的點
  visit[k]:=true; //記在visit內表參觀過
  for(all vertex j屬於neighbor(k)){ //這裡最多跑n-1次,
   new_distance:=distance[k]+cost[k][j];
   if(new_distance < istance[j]){
    distance[j]:=new_distance;
    path[j]=k;
   }
  }
 }
}

任意兩點間的最短路徑與距離
重覆執行dijkstra的演算法n次即可,使用相鄰矩陣則為bigO(N^3)
dynamic programming(動態規畫法設計),可簡單得到,但同樣為bigO(n^3)

......

aov網路(activity on vertex network)
用點表activity工作,邊表工作間處理優先關係的有向圖,因工作間有先後關係所以不能有迴路存在,且擁有topological order(拓樸順序)
topological order ex:若邊為
表示必須先做vi才能做vj
用途:應用在有前後線性關性,如表示一個由多個工作所組成的專案的規劃,os表示多個執行的工作元間的等待圖,不能有迴路的組合電路

演算法為先找出進入分支度為0的點

aoe網路(activity on edge network)
臨界工作:工作最早開始時間=工作最晚開始時間
critical path(臨界路徑):起始到結束的頂點皆由臨界工作所組成的路徑
求法:
1先求前進階段在求後退階段,及可得到各點的最早及最晚開始時間
2找出各工作的最早e(ai)與最晚l(ai)開始時間,若相同則為臨界工作

頂點最早與最晚開始時間計算
forward stage(前進階段):從起始頂點到結束頂點,計算各點最早開始時間,也稱最大階段
求法:設工作ai用兩點表示時,點q的最早開始時間=點p最早開始時間+ai長度,若點q有多邊進入則設定其中最大者
backward stage(後退階段):從結束頂點到起始頂點,計算各點最晚開始時間,也稱最小階段
求法:設工作ai用兩點表示時,點p的最晚開始時間=點q的最晚開始時間-ai長度,若點p有多邊進入則設定其中最小者

邊(工作)最早e(ai)最晚l(ai)開始時間計算:可由頂點最早e(vi)最晚l(vi)開始時間推導
求法:設工作ai用兩點
表示時,e(ai)=點p最早開始時間,l(ai)=點q的最晚開始時間-ai長


2007-03-05 18:56:12發表 0000-00-00 00:00:00修改   

數據分析
程式開發
計算機組織與結構
資料結構與演算法

Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統
數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net