第七章图 图的定义 图的存储结构 图的遍历 图的应用
第七章 图 • 图的定义 • 图的存储结构 • 图的遍历 • 图的应用
7.1图的定义和术语 1.图 有向图( Digragh) 无向图( Undigraph) 图也是一种非线性地数据结构 其抽象数据类型见书P156
7.1 图的定义和术语 1. 图 有向图（Digragh） 无向图（Undigraph） 图也是一种非线性地数据结构 其抽象数据类型见书P156
7.1图的定义和术语 ·有向图( Digragh) G=(V,{A}) 其中,V为顶点的有穷非空集合 A}.为顶点之间的关系集合 a.dl② G1=(V,{A}) V={v1,v2,v3,v4} A={<v1,v2>,<vl,v3>,<v3,v4>,<v4,vl>} ④其中<x,y>表示从x到y的一条弧(arc),A为弧集合,x为弧 尾(tai),y为弧头(head)
7.1 图的定义和术语 • 有向图（Digragh） G=（V，{A}） 其中，V为顶点的有穷非空集合 {A}为顶点之间的关系集合 G1=（V，{A}） V={v1, v2, v3, v4} A={<v1, v2>, <v1, v3>, <v3, v4>, <v4, v1>} 其中<x, y>表示从x到y的一条弧（arc），A为弧集合，x为弧 尾（tail），y为弧头（head) ① ② ③ ④ G1
7.1图的定义和术语 无向图( Undigraph) G=(V,{E}) 其中,V同有向图,{E为顶点之间的关系集合, E为边集合 ①G2②G2=(V,{4}) V={v1,v2,v3,v4,v5} E={(v1,v2),(v1,v4),(v2,v3),(3,v4),(v2,v5),(v3,v5)} 其中,(x,y)表示x与y之间的一条连线,称为边(edge
7.1 图的定义和术语 • 无向图（Undigraph） G=(V,{E}) 其中，V同有向图，{E}为顶点之间的关系集合， E为边集合 G2=（V，{A}） V={v1, v2, v3, v4, v5} E={(v1, v2), (v1, v4), (v2, v3), (v3, v4), (v2,v5), (v3,v5)} 其中，(x, y)表示x与y之间的一条连线，称为边（edge） ① G2 ② ③ ④ ⑤
7.1图的定义和术语 设m为顶点数,c为边或弧的条数 对无向图有:0<=e<=n(m-1)2 有向图有:0<=e<=m(n-1) 证明:每个顶点至多有n-1条边与其它的n-1个顶点相 连,则m个顶点至多有n(m-1)条边。但每条边连 接2个顶点,故最多为n(n-1)/2
7.1 图的定义和术语 设n为顶点数，e为边或弧的条数 对无向图有：0<=e<=n(n-1)/2 有向图有：0<=e<=n(n-1) 证明：每个顶点至多有n-1条边与其它的n-1个顶点相 连，则n个顶点至多有n(n-1)条边。但每条边连 接2个顶点，故最多为n(n-1)/2