《数据结构第7章图.ppt》由会员分享，可在线阅读，更多相关《数据结构第7章图.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章第七章 图图7.1 图的类型定义图的类型定义7.2 图的存储结构图的存储结构7.3 图的遍历图的遍历7.4 最小生成树最小生成树7.5 有向无环图及其应用有向无环图及其应用7.6 最短路径最短路径1其中：其中：V=ei|eiElemSet,i=1,2,n R=VR VR=|v,wV 且且 P(v,w)谓词谓词 P(v,w)定义了定义了 之间关系的意义或信息。之间关系的意义或信息。7.1 图的类型定义图 是由一个是由一个顶点集顶点集 V 和一个和一个关系集关系集 R构成的数据结构。构成的数据结构。Graph=(V,R)Graph=(V,R)27.2 图的存储表示图的存储表示一、图的数组一、
2、图的数组(邻接矩阵邻接矩阵)存储表示存储表示二、图的邻接表存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示3一、邻接矩阵一、邻接矩阵在存储图的结构时，至少要保存两类信息：在存储图的结构时，至少要保存两类信息：u顶点的数据顶点的数据u顶点之间的关系顶点之间的关系数组表示法：数组表示法：使用使用两个数组两个数组，其中一个用来存储，其中一个用来存储顶顶点的数据点的数据，另一个用来存储，另一个用来存储顶点之间的关系顶点之间的关系(弧弧)，表示弧的矩阵被称为表示弧的矩阵被称为邻接矩阵邻接矩阵（二维数组）。
3、（二维数组）。具有具有n个顶点的图个顶点的图G的的邻接矩阵邻接矩阵是具有如下性质的是具有如下性质的n阶矩阵阶矩阵：Aij=Aij=1 Vi邻接邻接Vj （0i，jn-1）0 Vi与与Vj不邻接不邻接4 V1V1 V2V2 V3V3 V4V4 V1 V1 V5 V5 V4 V4 V2 V2 V3 V30 1 0 1 00 1 0 1 01 10 1 0 10 1 0 12 20 1 0 1 0 1 0 1 1 13 30 1 0 00 1 0 04 40 1 1 0 0 1 1 0 0 0无向图无向图G2 的邻接矩阵的邻接矩阵有向图有向图G1 的邻接矩阵的邻接矩阵0 1 1 00 1 1 00
4、0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0v1 v2 v3 v4v1v2v3v45无向图邻接矩阵表示法特点：无向图邻接矩阵表示法特点：无向图邻接矩阵是无向图邻接矩阵是对称矩阵对称矩阵，同一条边表示了两次，同一条边表示了两次,无无向图的向图的总边数总边数为为非非0元素个数的一半元素个数的一半；顶点顶点v的度的度:等于二维数组等于二维数组对应行对应行（或列）中（或列）中1的个数；的个数；判断两顶点判断两顶点v、u是否为邻接点是否为邻接点:只需判断二维数组只需判断二维数组对应对应分量是否为分量是否为1；顶点不变，在图中顶点不变，在图中增加、删除边增加、删除边:只需
5、对二维数组只需对二维数组对应对应分量赋值分量赋值1或清或清0；设图的设图的顶点数为顶点数为 n,存储图用一维数组存储图用一维数组,数组元素有数组元素有m（m=n)个个,则则G占用存储空间：占用存储空间：m+n2；G占用存储占用存储空间只与它的空间只与它的顶点数顶点数有关，与边数无关；适用于有关，与边数无关；适用于边稠密边稠密的图；的图；6无向图的邻接矩阵为对称矩阵。无向图的邻接矩阵为对称矩阵。7有向图邻接矩阵表示法特点：有向图邻接矩阵表示法特点：有向图邻接矩阵有向图邻接矩阵不一定是对称矩阵不一定是对称矩阵；有向图的有向图的弧数是矩阵中弧数是矩阵中1的个数的个数。顶点顶点v的的出度出度：等于二维
6、数组：等于二维数组对应行对应行中中1的个数；的个数；顶点顶点v的的入度入度：等于二维数组：等于二维数组对应列对应列中中1的个数；的个数；有向图的有向图的总弧数总弧数为非为非0元素个数。元素个数。网的邻接矩阵网的邻接矩阵:132458462 5 4 65 84 26 8 2 A=Aij=Aij=wij Vi邻接邻接Vj,权值是权值是Wij（0i，jn-1）Vi与与Vj不邻接不邻接8图的数组存储表示图的数组存储表示#define INFINITY INT_MAX/最大值最大值#define MAX_VERTEX_NUM 20/最大顶点个数最大顶点个数typedef enum DG,DN,AG,AN
7、 GraphKind;/有向图有向图,有向有向网网,无向图无向图,无向无向网网typedef struct ArcCell /存储弧存储弧/边的信息，即边的信息，即邻接矩邻接矩阵阵 VRType adj;/VRType是是顶点顶点关系关系类型类型。/对对无权图无权图，用，用1或或0表示相邻否；表示相邻否；/对对带权图带权图，则为，则为权值权值类型。类型。InfoType*info;/该弧相关信息的指针该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;9图的数组存储表示图的数组存储表示typedef struct /存储数据元素信息存
8、储数据元素信息 VertexType vexsMAX_VERTEX_NUM;/存储数据元素信息，即存储数据元素信息，即顶点向量顶点向量 AdjMatrix arcs;/邻接矩阵邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧图的当前顶点数和弧(边边)数数 GraphKind kind;/图的图的种类标志种类标志 MGraph;10邻接矩阵的数据类型定义邻接矩阵的数据类型定义#define MaxV 100 /定义最大顶点数定义最大顶点数typedef structint vexesMaxV;/顶点表顶点表 int edgesMaxVMaxV;/邻接矩阵邻接矩阵 int n,e
9、;/顶点数顶点数n和边数和边数eMGraph;11二、邻接表二、邻接表邻接表是图（包括有向图和无向图）的邻接表是图（包括有向图和无向图）的链式存储链式存储结构。结构。对于图中的每个顶点对于图中的每个顶点vi，把所有，把所有邻接于邻接于vi的各个顶点的各个顶点链成一个链成一个单链表单链表，称为称为边链表边链表。u无向图中无向图中顶点顶点vi的的边链表边链表中每个结点都对应一个与中每个结点都对应一个与vi关联的边关联的边；u有向图中有向图中顶点顶点vi的的边链表边链表中每个结点都对应一个以中每个结点都对应一个以vi为始顶点为始顶点的弧，因此称为的弧，因此称为出边表出边表。12为每个为每个顶点顶点v
10、i的的边链表边链表建立一个建立一个头结点头结点，存储在，存储在一维一维数组数组中中(即即顶点表顶点表)，以便随机访问任一顶点的边链表。，以便随机访问任一顶点的边链表。因此，在邻接表中有两种结点：因此，在邻接表中有两种结点：链表结点链表结点 和和 顶点结点顶点结点邻接表是一种邻接表是一种顺序顺序+链式链式存储结构。用存储结构。用顺序表存放顶顺序表存放顶点点，为每个顶点建立一个单链表，为每个顶点建立一个单链表，单链表单链表中的结点中的结点表表示依附于该顶点的边或以该顶点为尾的弧。示依附于该顶点的边或以该顶点为尾的弧。13顶点数据结点（数组元素）由两个域组成：顶点数据结点（数组元素）由两个域组成：数
11、据域数据域（data）:存储顶点名称或其他信息。存储顶点名称或其他信息。链域链域（firstarc）:指向链表中第一个结点指向链表中第一个结点(边边)。边链表的每个结点由边链表的每个结点由3 3个域组成：个域组成：邻接点域邻接点域（adjvex）：指示与顶点）：指示与顶点 vi 邻接的顶点邻接的顶点在图中的位置。在图中的位置。链域链域（nextarc）:指示下一条边或弧的结点。指示下一条边或弧的结点。数据域数据域（info）:存储和边或弧相关的信息。存储和边或弧相关的信息。adjvex nextarc info链表结点链表结点 data firstarc数组元素结点数组元素结点14图的邻接表存
12、储表示图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode /边链表边链表结点结点int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置struct ArcNode*nextarc;/指向下一条弧的指针指向下一条弧的指针InfoType*info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;typedef struct VNode /头结点头结点VertexType data;/顶点信息顶点信息ArcNode*firstarc;/指向第一条依附该顶点的指向第一条依附该顶点的弧弧 VNode,AdjListMA
13、X_VERTEX_NUM;15图的邻接表存储表示图的邻接表存储表示 typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧图的当前顶点数和弧数数int kind;/图的图的种类标志种类标志 ALGraph;16 V0V0 V4V4 V3V3 V1V1 V2V21 13 32 21 12 20 04 41 13 32 20 04 4V0V1V2V3V401234无向图的邻接表示例无向图的邻接表示例 注意：注意：没有画出链表结点的没有画出链表结点的info域域。17无向图的邻接表的特点无向图的邻接表的特点边链表中边链表中结点总数结点
14、总数是是图中边数的图中边数的2倍倍；顶点顶点v的度的度：等于：等于v对应对应链表的长度链表的长度判定两顶点判定两顶点v，u是否邻接是否邻接：要看：要看v对应链表中有对应链表中有无对应的结点；无对应的结点；在图中在图中增减边增减边：要在：要在两个两个单链表单链表插入、删除结插入、删除结点点；设存储顶点的设存储顶点的一维数组大小为一维数组大小为m(m图的顶点数图的顶点数n),图的图的边数为边数为e，图占用存储空间为：，图占用存储空间为：m+2*e。图占用图占用存储空间存储空间与图的与图的顶点数顶点数、边数边数均有关；均有关；适用于适用于边稀疏的图。边稀疏的图。18 V0 V0 V1 V1 V2 V
15、2 V3 V3有向图的邻接表有向图的邻接表：边链表中边链表中结点总数结点总数等于图中等于图中弧数弧数；每个边链表的每个边链表的结点数结点数是相应顶点的是相应顶点的出度出度；求入度求入度需遍历边表中所有结点，或者建立需遍历边表中所有结点，或者建立逆邻接表逆邻接表。逆邻接表逆邻接表是为图中每个顶点建立一个是为图中每个顶点建立一个入边入边表表。下标下标 编号编号 next next 0 1 2 31 12 23 30 0V1V1V0V0V2V2V3V3邻接表邻接表3 30 00 02 2 0 1 2 3V1V1V0V0V2V2V3V3逆邻接表逆邻接表19有向图的邻接表有向图的邻接表A AB BC C
16、D DE E F F0 01 12 23 34 45 5data firstarcvexnum=6,arcnum=714 4 5 2 3 120有向图的有向图的逆邻接表逆邻接表A A B BC CD DE EF F0 01 12 23 34 45 5data firstarcvexnum=6,arcnum=705 3 5 1 02 单链表中的结点表示单链表中的结点表示以该顶点为以该顶点为头头的弧的弧21网的邻接表的数据类型定义：网的邻接表的数据类型定义：#define MaxV 100typedef struct node /边链表的结点类型边链表的结点类型int adjvex;/该弧所指向的
17、顶点的位置该弧所指向的顶点的位置float weight;/边的权值边的权值struct node*next;/指向下一条弧的指针指向下一条弧的指针Enode;typedef struct /表头结点类型表头结点类型 VertexType data;/顶点信息顶点信息 Enode*firste;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧 Vnode;22网的邻接表的数据类型定义：网的邻接表的数据类型定义：typedef structVnode adjlistMaxV;/邻接表邻接表int n,e;/顶点数和边数顶点数和边数ALGraph;23三、十字链表三、十字链表(有向图有向图)十字
18、链表是十字链表是有向图有向图的另一种的另一种链式链式存储结构。存储结构。将有向图的邻接表和逆邻接表结合起来的结构。将有向图的邻接表和逆邻接表结合起来的结构。在十字链表中有两种结点：在十字链表中有两种结点：u弧结点弧结点：存储：存储每一条弧每一条弧的信息，用的信息，用链表链表链接在一链接在一起。起。u顶点结点顶点结点：存储：存储每一个顶点每一个顶点的信息，使用的信息，使用一维数一维数组组来存储。来存储。顶点结点结构顶点结点结构:datafirstinfirstout弧结点结构弧结点结构:tailvex headvex hlinktlinkinfo24typedef struct ArcBox /
19、弧的结构表示弧的结构表示 int tailvex,headvex;/指示该弧的头和尾的位置指示该弧的头和尾的位置 InfoType *info;struct ArcBox *hlink,*tlink;/指向弧头链表和弧尾链表的下一个结点指向弧头链表和弧尾链表的下一个结点 VexNode;typedef struct VexNode /顶点的结构表示顶点的结构表示 VertexType data;ArcBox *firstin,*firstout;/指向以该顶点为头和指向以该顶点为头和尾尾 /的两个链表的两个链表 VexNode;25typedef struct /图结构图结构 VexNode
20、xlist20;/顶点结点向量顶点结点向量 int vexnum,arcnum;/顶点数和弧数顶点数和弧数 OLGraph;V2V4V1V30 20 12 32 03 23 13 0V1V2 V3V40123顶点结点顶点结点 弧结点弧结点26十字链表中既容易找到十字链表中既容易找到以以v vi i为尾为尾的弧，的弧，也容易找到也容易找到以以v vi i为头为头的弧，因而容易求的弧，因而容易求得顶点的得顶点的出度和入度出度和入度。27四、邻接多重表四、邻接多重表(无向图无向图)邻接多重表邻接多重表是是无向图无向图的另一种的另一种链式链式表示结构。表示结构。和十字链表类似。邻接多重表中，和十字链表
21、类似。邻接多重表中，每一条边用一每一条边用一个结点表示。个结点表示。在邻接多重表中有两种结点：在邻接多重表中有两种结点：u边结点边结点：存储：存储每一条边每一条边的信息，用的信息，用链表链表链接链接在一起。在一起。u顶点结点顶点结点：存储：存储每一个顶点每一个顶点的信息，使用的信息，使用一一维数组维数组来存储。来存储。顶点结点结构顶点结点结构:data firstedge边结点结构边结点结构:mark ivex ilink jvexjlink info28typedef struct VexBox /顶点结点顶点结点 VertexType data;EBox *firstedge;/指向第一条
22、依附该顶点的边指向第一条依附该顶点的边 VexBox;typedef struct Ebox /边结点边结点 VisitIf mark;/访问标记访问标记 int ivex,jvex;/该边依附的两个顶点的位置该边依附的两个顶点的位置 struct EBox *ilink,*jlink;/指向依附于指向依附于ivex,jvex的下一条边结点的下一条边结点 InfoType *info;EBox;29typedef struct /图结构图结构 VexBox adjmulist20;int vexnum,edgenum;AMLGraph;/邻接多重表邻接多重表0123V1V3V4V24V5 0
23、1 0 3 2 3 2 1 2 4 4 1 V1V1 V5V5 V4V4 V2V2 V3V33031练习练习1.给出下图所示无向图的邻接矩阵存储结构给出下图所示无向图的邻接矩阵存储结构32练习练习1.0111000001000110001000001101000000000100000010100000010010000010010000010000111101 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 933练习练习2.给出下图所示有向网的邻接矩阵存储结构给出下图所示有向网的邻接矩阵存储结构34练习练习2.201521030410154101 2 3 4 5 61 2 3 4 5 6 35练习练习3.给出下图所示带权无向图的邻接表存储结构给出下图所示带权无向图的邻接表存储结构36练习练习3.37