3.6图 ■361图的基本概念 36.2图的存储 36.3图的遍历 36.4图的应用
◼ 3.6.1 图的基本概念 ◼ 3.6.2 图的存储 ◼ 3.6.3 图的遍历 ◼ 3.6.4 图的应用 3.6 图
图的定义、术语 36.1图的基本概念 数据结构B=(D,R) B 图:G=(V,E) 顶点:图中的数据元素 V:表示顶点的非空有限集合。 E:表示两个顶点之间关系的集合
3.6.1 图的基本概念 A B C D 6 3 2 1 数据结构 5 B=（D，R） 图： G=（V，E） 顶点:图中的数据元素 V：表示顶点的非空有限集合。 E：表示两个顶点之间关系的集合。 图的定义、术语
图的定义、术语 有向图 图 无向图 在有向图中,<V1,V3>表示从V到V3的一条弧 V1为弧尾或初始点,V3为弧头或终端点。 在无向图中,(W1,V3)表示V1和V3之间的一条边
图 有向图 无向图 在有向图中，<V1，V3>表示从V1到V3的一条弧。 V1为弧尾或初始点，V3为弧头或终端点。 在无向图中，(V1，V3)表示V1和V3之间的一条边。 V1 V3 V2 V4 V1 V3 V2 V4 图的定义、术语
图的定义、术语 G=(V,E 顶点集合V={V 弧的集合G={<V1,V3>,<V3,V4 V1>} 顶点集合V={V1,V2,V3,V4} 边的集合E={(V,V3),(V1,V2) (V1,V4),(V2,V4)} 顶点(V1,V3)与(V3,V1)表示同一条边
V1 V3 V2 V4 V1 V3 V2 V4 顶点集合V={V1， V2 ， V3 ， V4 } 弧的集合G={<V1，V3>, <V3 ，V4>, <V2 ，V4>, <V4，V1>} 顶点集合V={V1， V2 ， V3 ， V4 } 边的集合E={(V1 , V3 ), (V1 , V2 ), (V1 , V4 ),(V2 , V4 )} G=( V, E ) 顶点(V1 , V3 )与 (V3 , V1 )表示同一条边 图的定义、术语
图的定义、术语 权:与图的边或弧相关的数。 顶点的度:依附于该顶点的边数或弧数。 出度:(仅对有向图)以该顶点为尾的弧数 入度:(仅对有向图)以该顶点为头的弧数。 路径:顶点A与顶点C之间存在一条路径。路径上边或弧的数目 称为该路径的路径长度。 连通图:无向图任意两顶点都有路径(没有孤立顶点) 强连通图:有向图任意两顶点都有路径 网:带权的图称为网 B
A B C D 6 3 2 1 5 权：与图的边或弧相关的数。 顶点的度：依附于该顶点的边数或弧数。 出度：（仅对有向图）以该顶点为尾的弧数。 入度：（仅对有向图）以该顶点为头的弧数。 路径：顶点A与顶点C之间存在一条路径。路径上边或弧的数目 称为该路径的路径长度。 连通图：无向图任意两顶点都有路径（没有孤立顶点） 强连通图：有向图任意两顶点都有路径 网：带权的图称为网 图的定义、术语