电子斜技大学 软件技术基础 3.6.1图的基本概念 主讲教师：刘民岷 航空航天学院 a口2 软件技术基础课程组
软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
图是一种对结点的前趋和后趋个数不加限制的数据结构， 在图结构中，结点之间的联系是任意的，每个结点都可以 与其它结点相联系。 有关图的理论，在“离散数学”的图论中有详细论述和证 明。在数据结构中，只讨论图在计算机中的实现和操作。 ·现实生活中，图的应用范围很广泛，涉及： 电讯工程、电网调度、集成电路设计 交通管理、工程管理、系统工程等领域 电子科技大学刘民岷 图 2
电子科技大学 刘民岷 图 2 • 图是一种对结点的前趋和后趋个数不加限制的数据结构， 在图结构中，结点之间的联系是任意的，每个结点都可以 与其它结点相联系。 • 有关图的理论，在“离散数学”的图论中有详细论述和证 明。在数据结构中，只讨论图在计算机中的实现和操作。 • 现实生活中，图的应用范围很广泛，涉及： – 电讯工程、电网调度、集成电路设计 – 交通管理、工程管理、系统工程等领域
1、图的逻辑特征 图G由两个集合V和E组成，记为G=(V,E),其中V是顶点 的有穷非空集合，E是V中顶点偶对（称为边的有穷集。通 常也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可 以是空集，若E(G)为空集，则图G只有顶点而没有边。 图结构示例如下： 5 2 2 3 4 3 6 a.无向图G b.有向图G2 电子科技大学刘民岷 图 3
电子科技大学 刘民岷 图 3 • 图G由两个集合V和E组成，记为G＝(V,E)，其中V是顶点 的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。通 常也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可 以是空集，若E(G)为空集，则图G只有顶点而没有边。 • 图结构示例如下： 1 2 3 4 5 a.无向图G 1 6 2 3 4 5 b.有向图G2
1、图的逻辑特征（续） 无▣图Undigraph) 图G中顶点的偶对若是无向的，形成的图称为无向图，其偶对用(Vx, Vv)表示，如图G所示。 G=(V,E); V(G1)={1,2,3,4,5} E(G1={(1,2),(1,3),(2,3),(3,4),(4,5)} 有向图Digraph) a.无向图G 图G中顶点的偶对若是有向的，形成的图称有向图。如图G,所示。为示 区别，其偶对用表示。 G2(V,E): V(G2)={1,2,3,4,5,6} E(G2)={,,,,,,} b.有向图G2 电子科技大学刘民岷 图 4
电子科技大学 刘民岷 图 4 •无向图(Undigraph) 图G中顶点的偶对若是无向的，形成的图称为无向图，其偶对用（vx， vy）表示，如图G1所示。 G1=(V,E); V(G1 )={1,2,3,4,5} E(G1 )={(1,2),(1,3),(2,3),(3,4),(4,5)} •有向图(Digraph) 图G中顶点的偶对若是有向的，形成的图称有向图。如图G2所示。为示 区别，其偶对用表示。 G2=(V,E); V(G2 )={1,2,3,4,5,6} E(G2 )={,,,,,,} 1 2 3 4 5 a.无向图G 1 6 2 3 4 5 b.有向图G2
1、图的逻辑特征（续） 有关图结构的重要术语和概念 (I)邻接点：对于无向图，如果边(v,u)∈E,则v和u互为邻点，亦即u是v的邻 接点，v也是u的邻接点。 对于有向图，如果弧(v,u)∈E,则u是v的邻接点。 (2)顶点的度：常用D(V)表示，在无向图中，顶点的度就是以该顶点为一 个端点的边的条数。 在有向图中，以某顶点为弧头的弧的数目，称为此顶点的入度，常用 ID(V)表示；以某顶点为弧尾的弧的数目，常用OD(V)表示。有向图顶点 的度是此顶点的入度与出度之和，即D(V)=D(V)+OD(V)。 无论是有向图，还是无向图，顶点数n、边数e和度数之 间有如下关系： e=2) 电子科技大学刘民岷 图 5
电子科技大学 刘民岷 图 5 • 有关图结构的重要术语和概念 (1)邻接点：对于无向图,如果边(v,u)∈E,则v和u互为邻点, 亦即u是v的邻 接点，v也是u的邻接点。 对于有向图，如果弧(v,u)∈E，则u是v的邻接点。 (2)顶点的度：常用D(V)表示，在无向图中，顶点的度就是以该顶点为一 个端点的边的条数。 在有向图中，以某顶点为弧头的弧的数目，称为此顶点的入度，常用 ID(V)表示；以某顶点为弧尾的弧的数目，常用OD(V)表示。有向图顶点 的度是此顶点的入度与出度之和，即D(V)＝ID(V)＋OD(V)。 无论是有向图，还是无向图，顶点数n、边数e和度数之 间有如下关系： = = n i D Vi e 1 ( ) 2 1
图的逻辑特征（续） 有关图结构的重要术语和概念 (3)路径：在图G中，从顶点v至顶点u的一条路径是顶点的序列 (W,vl,v2,.vi,u),并且(，vl),(l,2),.(vi,u)(无向图)或, ,(有向图)都属于集合E。路径上弧的数目称为该路径 的长度。 (4)连通图：在无向图中，若每一对顶点之间都有路径， 则称此图为连通 图。 在有向图中，若每一对顶点u和v之间都存在从v到u及从u到v的路径， 则称此图为强连通图。 连通图 强连通图 电子科技大学刘民岷 图 6
电子科技大学 刘民岷 图 6 • 有关图结构的重要术语和概念 (3)路 径：在图 G中 ，从顶点v至顶点 u的一条路径是顶点的序列 (v,v1,v2,…vi,u) ， 并 且 (v,v1),(v1,v2),…(vi,u)( 无 向 图 ) 或 ﹤ v,v1﹥, ﹤v1,v2﹥,…﹤vi,u﹥(有向图)都属于集合E。路径上弧的数目称为该路径 的长度。 (4)连通图：在无向图中，若每一对顶点之间都有路径，则称此图为连通 图。 在有向图中，若每一对顶点u和v之间都存在从v到u及从u到v的路径， 则称此图为强连通图。 强连通图 1 2 3 4 5 1 2 3 4 5 连通图
1、图的逻辑特征 (续) 有关图结构的重要术语和概念 (⑤)网经：如果图G(V,E)中每条边都赋有反映这条边的某种特性的数据， 则称此图是一个网络，其中与边相关的数据称为该边的权。 5 3 V4 7 电子科技大学刘民岷 图 7
电子科技大学 刘民岷 图 7 • 有关图结构的重要术语和概念 (5)网络：如果图G(V,E)中每条边都赋有反映这条边的某种特性的数据， 则称此图是一个网络，其中与边相关的数据称为该边的权。 V1 V2 V3 V4 2 3 5 7