数据结构 教学课件作者 戴敏7

数数 据据 结结 构构第第7章章b图图本章目标本章目标7.1 图的定义和基本术语图的定义和基本术语7.2 图的存储结构图的存储结构7.3 图的遍历图的遍历7.4 图的生成树和最小生成树图的生成树和最小生成树 7.5 拓扑排序及其应用拓扑排序及其应用7.6 最短路径最短路径3 37.1 图的定义图的定义和基本术语和基本术语图图(graph)的定义的定义b图是由顶点图是由顶点(vertex)集合及顶点间的关系集集合及顶点间的关系集合组成的一种数据结构合组成的一种数据结构 Graph(V,E)其中其中V=x|x 某个数据对象某个数据对象是顶点的有是顶点的有限非空集合；限非空集合；E=(x,y)|x,y V 是顶点是顶点之间关系的有限集合，也叫做边之间关系的有限集合，也叫做边(edge)集集5 5图的图的ADT描述描述6 6图的术语图的术语b有向图和无向图有向图和无向图 在图中，若用箭头标明了边是有方在图中，若用箭头标明了边是有方向的，则称这样的图为有向图，否则称为无向图。如向的，则称这样的图为有向图，否则称为无向图。如下图中，下图中，G1为无向图，为无向图，G2为有向图为有向图d cba 2 13(a)无向图无向图G1(b)有向图有向图G2b在无向图中，边在无向图中，边(x,y)与与(y,x)相同，用相同，用()表示表示b在有向图中，边在有向图中，边与与不同，用不同，用表示。表示。表示从顶点表示从顶点x发向顶点发向顶点y的边，的边，x为始点，为始点，y为终点。为终点。有向边也称为弧有向边也称为弧(arc)，x为弧尾为弧尾(tail)，y为弧头为弧头(head)。表示一条弧，表示一条弧，表示另一条弧，表示另一条弧，y为为弧尾，弧尾，x为弧头为弧头7 7图的术语图的术语b完全图完全图 具有具有n个顶点，个顶点，n(n-1)/2条边的无向图，称为完全条边的无向图，称为完全无向图；具有无向图；具有n个顶点，个顶点，n(n-1)条弧的有向图，称为完全有条弧的有向图，称为完全有向图。完全无向图和完全有向图统称为完全图向图。完全无向图和完全有向图统称为完全图b稠密图与稀疏图稠密图与稀疏图 当一个图接近完全图时，称它为稠密图。当一个图接近完全图时，称它为稠密图。相反，当一个图中含有较少的边或弧时，称它为稀疏图相反，当一个图中含有较少的边或弧时，称它为稀疏图b权权 在图的边或弧上给出相关的数，称为权。权可以代表在图的边或弧上给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距离、开销等，带权图一般又称一个顶点到另一个顶点的距离、开销等，带权图一般又称为为网络网络(network)(a)无向网络无向网络(b)有向网络有向网络5312441672358ABC215348 8图的术语图的术语b子图子图(subgraph)若有两个图若有两个图G1和和G2，G1=(V1,E1)，G2=(V2,E2)，满足如下条件：满足如下条件：V2 V1，E2 E1，即即V2为为V1的子的子集，集，E2为为E1的子集，称图的子集，称图G2是图是图G1的子图的子图b邻接点邻接点 若若(vi,vj)是一条无向边，则称顶点是一条无向边，则称顶点vi和和vj互为互为邻接点，或称邻接点，或称vi和和vj相邻接，并称边相邻接，并称边(vi,vj)与顶点与顶点vi和和vj相关联相关联9 9图的术语图的术语b度、入度、出度度、入度、出度 在无向图中，一个顶点依附的边的数目，在无向图中，一个顶点依附的边的数目，称为该顶点的度。在有向图中，指向顶点的弧的数目称为称为该顶点的度。在有向图中，指向顶点的弧的数目称为该顶点的入度该顶点的入度(这种弧也叫入弧这种弧也叫入弧)。从顶点发出的弧的数目。从顶点发出的弧的数目称为该顶点的出度称为该顶点的出度(这种弧也叫出弧这种弧也叫出弧)，有向图的某个顶点，有向图的某个顶点的入度和出度之和称为该顶点的度的入度和出度之和称为该顶点的度若图若图(无向图或有向图无向图或有向图)中有中有n个顶点，个顶点，e条边条边或弧，则有或弧，则有e=(di为顶点为顶点i 的度的度)b路径路径(path)、环环 在图在图G(V,E)中中,若存在一个顶点序列若存在一个顶点序列vp1,vp2,vpm，使得使得(vi,vp1),(vp1,vp2),(vpm,vj)均属于均属于E，则称顶点则称顶点vi到到vj存在一条路径。若一条路径上除了存在一条路径。若一条路径上除了vi和和vj可以相同外，其余顶点均不相同，则称此路径是一条简单可以相同外，其余顶点均不相同，则称此路径是一条简单路径，否则称为非简单路径。起点和终点相同的路径称为路径，否则称为非简单路径。起点和终点相同的路径称为回路或环回路或环(又可分为无向环和有向环又可分为无向环和有向环)1010图的术语图的术语b无向图的连通性无向图的连通性 在无向图在无向图G中，若两个顶点中，若两个顶点vi和和vj之之间有路径存在，则称间有路径存在，则称vi和和vj是连通的。若是连通的。若G中任意两个中任意两个顶点都是连通的，则称顶点都是连通的，则称G为为连通图连通图。否则称为非连通。否则称为非连通图。无向图的极大连通子图称为图。无向图的极大连通子图称为连通分量连通分量(connected components)。显然，任何连通图的连通分量只有一个，显然，任何连通图的连通分量只有一个，就是它本身，而非连通图有多个连通分量就是它本身，而非连通图有多个连通分量1111图的术语图的术语b有向图的连通性有向图的连通性 在有向图中，若对于每一对顶点在有向图中，若对于每一对顶点vi和和vj，都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径，则的路径，则称此有向图为称此有向图为强连通图强连通图。有向图的极大强连通子。有向图的极大强连通子图叫做图叫做强连通分量强连通分量。显然，任何强连通图的强连。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图则有通分量只有一个，即它本身，而非强连通图则有多个强连通分量多个强连通分量312412345（a）连通图连通图 (b)非连通图非连通图12345图图(b)的两个连通分量的两个连通分量1212图的术语图的术语ABDC126543(a)强连通图强连通图 (b)非强连通图非强连通图635图图(b)的三个强连通分量的三个强连通分量2141313图的术语图的术语b生成树生成树(支撑树支撑树spanning tree)无向连通图的生成无向连通图的生成树是它的极小连通子图，它包含图中全部树是它的极小连通子图，它包含图中全部n个顶点个顶点和和n-1条条不构成回路不构成回路的边。非连通图的所有连通分的边。非连通图的所有连通分 量的生成树组成一个生成森林量的生成树组成一个生成森林(spanning forest)。123456生成树生成树1123456连通图连通图123456生成树生成树214147.2 图的存储结构图的存储结构7.2.1 图的顺序存储结构图的顺序存储结构邻接矩阵邻接矩阵b图的邻接矩阵表示法图的邻接矩阵表示法在图的邻接矩阵在图的邻接矩阵(adjacent matrix)表示中，除表示中，除存放顶点本身的信息外，还用一个矩阵表示各存放顶点本身的信息外，还用一个矩阵表示各个顶点之间的关系。若个顶点之间的关系。若(i,j)E或或 E，则矩阵中第则矩阵中第i行第行第j列元素值为列元素值为1，否则为，否则为0b图的邻接矩阵定义为：图的邻接矩阵定义为：1 若若(i,j)E或或EAij=0 其它情形其它情形1616图的邻接矩阵表示法图的邻接矩阵表示法3 12(b)有向图有向图G2(a)无向图无向图 G1 1 2 43 001100110(b)G2的邻接矩阵的邻接矩阵0111101011011010(a)G1的邻接矩阵的邻接矩阵1717图的邻接矩阵的特点图的邻接矩阵的特点b无向图的邻接矩阵的特点无向图的邻接矩阵的特点矩阵是对称的矩阵是对称的第第i行或第行或第i列中列中1的个数为顶点的个数为顶点i的度的度矩阵中矩阵中1的个数的一半为图中边的数目的个数的一半为图中边的数目很容易判断顶点很容易判断顶点i和顶点和顶点j之间是否有边相连之间是否有边相连(看矩阵中第看矩阵中第i行第行第j列值是否为列值是否为1)b有向图的邻接矩阵的特点有向图的邻接矩阵的特点矩阵不是对称的矩阵不是对称的第第i行中行中1的个数为顶点的个数为顶点i的出度的出度第第i列中列中1的个数为顶点的个数为顶点i的入度的入度矩阵中矩阵中1的个数为图中弧的数目的个数为图中弧的数目很容易判断顶点很容易判断顶点i和顶点和顶点j是否有弧相连是否有弧相连(看矩阵中第看矩阵中第i行行第第j列值是否为列值是否为1)1818网络的邻接矩阵表示法网络的邻接矩阵表示法b类似地可以定义网络的邻接矩阵：类似地可以定义网络的邻接矩阵：wij 若若(i,j)E或或EAij=其它情形其它情形(包括主对角线包括主对角线)1919网络的邻接矩阵的特点网络的邻接矩阵的特点b无向网络的邻接矩阵的特点无向网络的邻接矩阵的特点矩阵是对称的矩阵是对称的第第i行或第行或第i列中非列中非元素的个数为顶点元素的个数为顶点i的度的度矩阵中非矩阵中非元素的个数的一半为网络中边的数目元素的个数的一半为网络中边的数目很容易判断顶点很容易判断顶点i和顶点和顶点j之间是否有边相连之间是否有边相连(看矩阵中第看矩阵中第i行第行第j列值是否为非列值是否为非元素元素)b有向网络的邻接矩阵的特点有向网络的邻接矩阵的特点矩阵不是对称的矩阵不是对称的第第i行中非行中非元素的个数为顶点元素的个数为顶点i的出度的出度第第i列中非列中非元素的个数为顶点元素的个数为顶点i的入度的入度矩阵中非矩阵中非元素的个数为网络中弧的数目元素的个数为网络中弧的数目很容易判断顶点很容易判断顶点i和顶点和顶点j是否有弧相连是否有弧相连(看矩阵中第看矩阵中第i行行第第j列值是否为非列值是否为非元素元素)2020图的邻接矩阵存储结构图的邻接矩阵存储结构1#define INFINITY INT_MAX /最大值最大值2#define MAX_VERTEX_NUM 20/最大顶点数最大顶点数3typedef enum DG,DN,AG,AN GraphKind;4/有向图有向图,有向网有向网,无向图无向图,无向网无向网5typedef struct Arc 6 VRType adj;/VRType是顶点关系类型。对图而言，是是顶点关系类型。对图而言，是int型，型，7 /用用1或或0表示是否相邻；对网络而言，则为权值的类型表示是否相邻；对网络而言，则为权值的类型8 InfoType*info;/指向边或弧所代表的信息的指针指向边或弧所代表的信息的指针9 Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;10typedef struct 11 VertexType vertexMAX_VERTEX_NUM;/顶点数组，顶点数组，12 /VertexType为顶点类型为顶点类型13 AdjMatrix arcs;/邻接矩阵邻接矩阵14 int vexnum,arcnum;/顶点数、弧顶点数、弧(边边)数数15 GraphKind kind;/图的种类图的种类16 Graph;2121无向图的邻接矩阵存储结构无向图的邻接矩阵存储结构BADCE=0010100011100010100111110arcs=EDCBAvertex56AGGraphadjinfovexnum=arcnum=kind=2222有向图的邻接矩阵存储结构有向图的邻接矩阵存储结构BADCE=0000000010100000000011110arcs=EDCBAvertex56DGGraphadjinfovexnum=arcnum=kind=2323有向网络的邻接矩阵存储结构有向网络的邻接矩阵存储结构BAECDF203050407080A=EDCBvertex=807050403020arcs66DNadjinfoGraphFvexnum=arcnum=kin