图与网.ppt

3/30/2017 1第五章图与网 3/30/2017 2第五章图与网? 图与网的基本概念? 图与网的存储结构? 图的遍历? 无向连通网的最小生成树? 有向网的最短路径? 有向无环图及其应用 3/30/2017 3 图与网的基本概念 图与网的定义和术语图的定义 G=(V,E) ADC BE 无向图 ADC BE 有向图顶点边弧弧尾弧头 3/30/2017 4 图与网的定义和术语顶点与边的关系无向图: 0≤e≤ n(n-1)/2 有向图: 0≤e≤ n(n-1) ADC BE 完全图 ADC BE 稀疏图 e< nlogn 3/30/2017 5 图与网的定义和术语网的定义弧或边标上具体的数字,这些数称为权。带有权的图称为网 ADC BE 无向网 567 43429 3/30/2017 6 图与网的定义和术语?子图的定义 ADC BE 图G ADC E 图G的子图 3/30/2017 7 图的相关术语?无向图顶点的度无向图顶点的度等于依附于该顶点的边的数目,例: TD(A)=3 ADC BE 无向图 3/30/2017 8 图的相关术语?有向图顶点的度有向图中:分为入度 ID(V) 和出度 OD(V) TD(V)= ID(V)+ OD(V) 例: TD(E)=3 ,其中出度为 OD(E) 1 ,入度 ID(E) 为2 ADC BE 有向图 3/30/2017 9 图的相关术语?顶点的度和边的关系 e=1/2 ∑ TD(V i) i=1 nADC BE 无向图 3/30/2017 10 图的相关术语?路径、回路(环),简单路径路径:从 A到D所经过的顶点序列回路(环):A EDB A简单路径:顶点不重复出现 ADC BE 无向图