数据结构8图VIP免费

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

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

有向边也为有向图

有向边也称为弧

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

((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),(v