第弋章 图的定义和术语 图的存储结 图的遍历与连通性 最小性生成树 活动网络 最短路径
图的定义和术语 图的存储结构 图的遍历与连通性 最小生成树 活动网络 最短路径
71图的定义和术语 图形结构的形式定义图是由顶点集合 vertex)及顶点 间的关系集合组成的一种数据结构: Graph=(V,R) 其中 V={x|x∈某个数据对象},是顶点的有穷非空集合; R边的有限集合 R={(x,y)|x,y∈V}无向图或 R={x,y>|x,y∈&&Path(x,y)}有向图 是顶点之间关系的有穷集合,也叫做边(edge)集合。 Pth(x,y)表示从x到y的一条单向通路,它是有方向 的。x弧尾,y弧头
7.1 图的定义和术语 图形结构的形式定义 图是由顶点集合(vertex)及顶点 间的关系集合组成的一种数据结构： Graph＝( V, R ) 其中： V = { x | x 某个数据对象} ， 是顶点的有穷非空集合； R——边的有限集合 R = {(x, y) | x, y V } 无向图 或 R = {<x, y> | x, y V && Path (x, y)}有向图 是顶点之间关系的有穷集合，也叫做边(edge)集合。 Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向 的。x弧尾，y弧头
有向图与无向图 令有向图中:边用<x,y>表示,且x与y是有序的。 a.有向图中的边称为“弧 bx弧尾或初始点y弧头或终端点 无向图:边用(x,y)表示,且顶x与y是无序的 完全图 令在具有n个顶点的有向图中,最大孤数为n(n-1) 令在具有n个顶点的无向图中,最大边数为n(n-1)2 顶点的度 无向图:与该页点相关的边的数目 令有向图 入度(v):以该顶点为头的弧的数目 出度OD(v):以该顶点为尾头的弧的数目
有向图与无向图 ❖ 有向图中：边用<x, y>表示，且x与y是有序的。 a. 有向图中的边称为“弧” b. x——弧尾或初始点 y——弧头或终端点 ❖ 无向图：边用(x, y) 表示，且顶x与 y是无序的。 完全图 ❖ 在具有n 个顶点的有向图中，最大弧数为n(n-1) ❖ 在具有n 个顶点的无向图中，最大边数为n(n-1)/2 顶点的度 ❖ 无向图：与该顶点相关的边的数目 ❖ 有向图： 入度ID(v) ：以该顶点为头的弧的数目 出度OD(v) ：以该顶点为尾头的弧的数目
在有向图中,顶点的度等于该顶点的入度与出度 之和 邻接点 令无向图:两顶点之间有条边,则两顶点互为邻接点 -y( y) 令有向图:从x到y有一条弧,则y是x的邻接点, 但x不是y的邻接点 X→→y<x,y>
在有向图中, 顶点的度等于该顶点的入度与出度 之和。 邻接点 ❖ 无向图：两顶点之间有条边，则两顶点互为邻接点 x —— y ( x ,y ) ❖ 有向图：从x到y有一条弧，则y是x的邻接点， 但x不是y的邻接点 x y <x ,y >
权某些图的边具有与它相关的数,称之为权。 这种带权图叫做网络。 0子图设有两个图G=(VE)和G=(V,E") 若vcV且EcE,则称图G是图G的子图 1 3 (a)G1 子图 子图 子图 b)63子图子图子图
权 某些图的边具有与它相关的数, 称之为权。 这种带权图叫做网络。 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。 若 V’ V 且 E‘E, 则称 图G’是 图G 的子图