软件基础-8图83469.pptVIP

第三章 非线性数据结构 3.2 图结构 3.2.1 图的定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中： V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 3.2 图结构 3.2.1 图的定义和术语 有向图——有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头 3.2 图结构 3.2.1 图的定义和术语 无向图——无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 3.2 图结构 有向完全图——n个顶点的有向图最大边数是n(n-1) 无向完全图——n个顶点的无向图最大边数是n(n-1)/2 3.2 图结构 子图——如果图G(V,E)和图G’ (V’,E’),满足： V’?V E’?E 则称G’为G的子图 3.2 图结构 顶点的度 无向图中，顶点的度TD(Vi)为与Vi顶点相连的边数 有向图中，顶点的度分成入度ID(V)与出度OD(V) 入度ID(V) ：以该顶点为头的弧的数目 出度OD(V) ：以该顶点为尾的弧的数目 3.2 图结构 顶点的度 无向图中，顶点的度TD(Vi)为与Vi顶点相连的边数 有向图中，顶点的度分成入度ID(V)与出度OD(V) 入度ID(V) ：以该顶点为头的弧的数目 出度OD(V) ：以该顶点为尾的弧的数目 3.2 图结构 路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)?E 或 Vij-1,Vij?E,(1j?n) 简单路径——序列中顶点不重复出现的路径叫简单路径。 路径长度——沿路径边的数目或沿路径各边权值之和。 回路——第一个顶点和最后一个顶点相同的路径叫回路。 简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路。 连通——从顶点V到顶点W有一条路径，则说V和W是连通的。 连通图——图中任意两个顶点都是连通的叫连通图。 连通分量——非连通图的每一个连通部分叫连通分量。 强连通图——有向图中，如果对每一对Vi,Vj?V, Vi?Vj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是强连通图。 生成树——连通图G的生成树是包含G中所有顶点的一个极小连通子图，它有且仅有n-1条边。 特点： 1）任意两顶点间有且仅有一条路经 2）在生成树中添加任意一条属于G的边必定会产生回路 3）若生成树中减少任意一条边，则必然成为非连通图 3.2 图结构 3.2.2 图的存储结构 一、邻接矩阵 邻接矩阵存储结构是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点的邻接关系——表示顶点间相联关系的矩阵。 定义：设G=(V,E)是有n?1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵： 一、邻接矩阵 邻接矩阵存储结构是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点的邻接关系——表示顶点间相联关系的矩阵。 定义：设G=(V,E)是有n?1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵： 邻接矩阵的特点： 若G为无向图，则： 邻接矩阵A为对称矩阵，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2； 第ｉ行非０元素的个数为顶点Vi的度，TD(Vi) 邻接矩阵的特点： 若G为有向图，则： 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2； 顶点Vi的出度是A中第i 行元素之和； 顶点Vi的入度是A中第i 列元素之和。 邻接矩阵的特点： 若G为无向图，则： 邻接矩阵A为对称矩阵，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2； 第ｉ行非０元素的个数为顶点Vi的度，TD(Vi)。 若G为有向图，则： 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2； 顶点Vi的出度是A中第i 行元素之和； 顶点Vi的入度是A中第i 列元素之和。 二、邻接表 邻接表是一种顺序存储(顶点顺序表)与链式存储(边的单链表)结合的存储方法，类似于树的孩子链表表示法。 特点 无向图中顶点Vi的度为第i个单链表中的结点数 有向图中 顶点Vi的出度为第i个单链表中的结点个数； 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数。 特点 无向图中顶点Vi的度为第i个单链表中的结点数； 有向图中 顶点Vi的出度为第i个单链表中的结点个数； 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数。 3.2.