データ構造19————図の定義と基本概念
3570 ワード
データ構造19————図の定義と基本概念
記事の目次データ構造19――図の定義と基本概念 一.内容: 二.図の定義 1.形式化定義 三.図の関連概念 1.各種図定義 2.図の頂点と境界関係 3連図関連用語 四.図のADT 5.参考資料 一.内容:図の定義 各種図に関する概念 図のADT 二.図の定義
1.形式化定義
図(Graph)は、頂点の有窮非空集合と頂点直辺の集合からなり、通常はG(V,E)と表される.ここで、Gは図を表し、Vは図Gの頂点の集合であり、Eは図Gの辺の集合である.図中のデータ要素を頂点と呼ぶ 図に空セットはなく、図中に頂点なし いずれの頂点にも関係があり、頂点間の論理関係をサイド表示 三.図の関連概念
1.各種図の定義無向辺:頂点viからvjまでの間に方向がなければ、この辺を無向辺と呼び、無秩序偶然対(vi,vj)で表します. 無方向図:図のいずれかの頂点の間の辺が無方向であれば、この図は無方向図 向辺がある:頂点viからvjまでの辺に方向があれば、アークとも呼ばれ、順序偶数＜vi、vj＞で表される.viは弧尾と呼ばれ、vjは弧頭と呼ばれている. 図中の任意の2つの頂点の間の辺に向かっているものがあれば、この図を矢印と呼びます. 簡単図:図において、頂点が自身の端に存在しない場合、同一の辺に重複しない場合、このような図を簡単図という. 無方向完全図:無方向図で、いずれかの頂点の間にエッジが存在する場合、当該図を無方向完全図という. 向完全図がある:図中のいずれかの頂点の間に互いに逆の弧が存在する場合、この図を完全図 間引き図＆稠密図:少しの辺や弧がある図を疎図、逆に稠密図 権:一部の図の端や弧には彼に関する数字があり、これに関する数は権 ネット:このような権利を持つ図は通常ネット 2.図の頂点と辺の関係無方向図G=(V,｛E｝に対して、辺(v 1,v 2)∈Eであれば、頂点v 1とv 2は互いに隣接している、すなわちv 1,v 2は隣接している.エッジ(v 1、v 2)は、頂点v 1およびv 2に依存し、または(v 1、v 2)は、頂点v 1、v 2に関連する.頂点vの度はvに関連する辺の数で、TD(v) 図G=(V、{E}がある場合、アーク∈Eでは、頂点v 1が頂点v 2に隣接し、頂点v 2が頂点v 1.アークと頂点v 1,v 2に隣接し、頂点v 1より頭の弧の数がv 1の入力度となり、ID(v)の頂点v+1と記載されているODv(v)の数は、ODv+1の頂点ID(vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv)の弧の数は、ODv.の数、ODv.の数、ODv.の数がID(vvvvvvvvvvvvvvvvvvv=・ 経路:無方向図G(V,｛E｝)の頂点v 1から頂点v 2までの経路はv 1からv 2までの途中の頂点のシーケンス 経路の長さ:経路上の辺または弧の数 回路(ループ):最初の頂点から最後の頂点まで同じ経路を回路またはリング シンプルパス:シーケンスの頂点が重複しない経路をシンプルパス シンプル回路(ループ):最初の頂点と最後の頂点を除いて、残りの頂点が重複しない回路をシンプル回路またはシンプルリング 3連通図関連用語接続:無方向図Gにおいて、頂点v 1から頂点v 2までの経路があれば、v 1とv 2は接続されている 連通図:図中の任意の2つの頂点viがない場合、vj、vi、vjが接続されている場合、この図は連通図 連結成分:図中の極めて大きな連結子図を連結成分という. 強連通図:向図において、意の二つの頂点vi、vj、vi、vjが接続されている場合、この図は強連通図 強連通成分:図中の極大強連通子図に向図と呼ばれる強連通成分がある 四.図のADT
五.参考資料
「大話データ構造」「データ構造とアルゴリズム」
記事の目次
1.形式化定義
図(Graph)は、頂点の有窮非空集合と頂点直辺の集合からなり、通常はG(V,E)と表される.ここで、Gは図を表し、Vは図Gの頂点の集合であり、Eは図Gの辺の集合である.
1.各種図の定義
ADT Graph{
V：V ， 。
R：R={VR}
VR={|v,w∈V P(v,w)， v w ，
P(v,w) }
：
CreateGraph( &G, V, VR )
：V ，VR 。
： V VR G。
DestroyGraph( &G )
： G 。
： G。
LocateVex( G, u )
： G ，u G 。
： G u， ； 。
GetVex( G, v )
： G ，v G 。
： v 。
PutVex( &G, v, value )
： G ，v G 。
： v value。
FirstAdjVex( G, v )
： G ，v G 。
： v 。 G ， “ ”。
NextAdjVex( G, v, w )
： G ，v G ，w v 。
： v （ w ） 。 w v ， “ ”。
InsertVex( &G, v )
： G ，v 。
： G v。
DeleteVex( &G, v )
： G ，v G 。
： G v 。
InsertArc( &G, v, w )
： G ，v w G 。
： G ， G ， 。
DeleteArc( &G, v, w )
： G ，v w G 。
： G ， G ， 。
DFSTraverse( G, Visit() )
： G ，Visit 。
： 。 Visit 。 visit() ， 。
BFSTraverse( G, Visit() )
： G ，Visit 。
： 。 Visit 。 visit() ， 。
}ADT Graph
五.参考資料
「大話データ構造」「データ構造とアルゴリズム」