数据结构第7章VIP免费

图的基本概念图的基本概念图的存储结构图的存储结构图的遍历图的遍历最小生成树最小生成树7

1图的基本概念图的基本概念图定义图定义图是由顶点集合图是由顶点集合(vertex)及顶点间的关系及顶点间的关系边（或者弧边（或者弧))集合组成的一种数据结构集合组成的一种数据结构：GraphGraph＝＝((VV,,EE))其中其中VV={={xx||xx某个数据对象某个数据对象}}是顶点的有是顶点的有穷穷非空集合；非空集合；EE={={或或(v,w)|(v,w)|vv,,wwVV}}是顶点之间关系的有穷集合，谓词是顶点之间关系的有穷集合，谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意义或信息,,谓词是用来刻划个体词的性质谓词是用来刻划个体词的性质或事物之间关系的词或事物之间关系的词

有向图与无向图有向图与无向图若图G中的每条边都是有方向的，则称G为有向图

有向边也称为弧

若图G中的每条边都是没有方向((xx,,yy))的，则称G为无向图

((xx,,yy))称为边

V1V1V3V3V4V4V5V5V2V2V4V4V3V3V2V2V1V1无向图无向图G1G1有向图有向图G2G2G2=(V2,E2)G2=(V2,E2)V2={v1,v2,v3,v4}V2={v1,v2,v3,v4}E2={,,,}E2={,,,}G1=G1=((VV,,EE))集合集合VV＝＝{v1,v2,v3,v4,v5}{v1,v2,v3,v4,v5}集合集合EE＝＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}

2002-11-12mmmm4权权某些图的边具有与它相关的数,称之为权

在实际应用中，权值可以有某种含义