《数据结构第讲图的定义与存储结构精.ppt》由会员分享，可在线阅读，更多相关《数据结构第讲图的定义与存储结构精.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构第讲图的定义与存储结构第1页，本讲稿共45页课程先后关系如图：课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11第2页，本讲稿共45页第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用7.6 7.6 最短路径最短路径第3页，本讲稿共45页7.1 7.1 图的定义和术语图的定义和术语1.1.基本术语基本术语(1)(1)顶点顶点 图中的
2、数据元素通常称为顶点。图中的数据元素通常称为顶点。V V是顶点的有穷非空是顶点的有穷非空集合；集合；VRVR是两个顶点之间的关系的集合。是两个顶点之间的关系的集合。(2)(2)有向图有向图 若称若称 VR VR表示从表示从v v到到w w的一条的一条弧，弧，且称且称v v为弧为弧尾或初始点，称尾或初始点，称w w为弧头或终端结点，则该图称为有为弧头或终端结点，则该图称为有向图。向图。第4页，本讲稿共45页(3)(3)无向图无向图 若若VRVR，必有，必有VRVR，即，即VRVR是对称的，是对称的，则以无序对则以无序对（v,wv,w)代替这两个有序对，表示代替这两个有序对，表示v v和和w w之
3、间之间的一条的一条边边，则该图称为无向图。，则该图称为无向图。第5页，本讲稿共45页(4)(4)权权/网网 有时图的边或弧具有与它相关的数，这些数称有时图的边或弧具有与它相关的数，这些数称为权值（通常表示顶点间的距离或耗费），则带权为权值（通常表示顶点间的距离或耗费），则带权值的图称为网。值的图称为网。(5)(5)子图子图 假设有两个图假设有两个图 G=G=（V V，VR VR）和）和 G G=（V V，VRVR ），若），若 V V 是是 V V 的子集，且的子集，且 VRVR 是是 VR VR 的子集，的子集，则称则称 G G 为为 G G 的子图。的子图。第6页，本讲稿共45页G1G1的
4、的子图子图G2G2的的子图子图第7页，本讲稿共45页(6)(6)完全图完全图 假设用假设用 n n 表示图中顶点的数目，用表示图中顶点的数目，用 e e 表示边或表示边或弧的数目。忽略自身弧弧的数目。忽略自身弧/边，即若边，即若v vi i,v,vj j VR VR，则，则 v vi ivvj j。对于无向图，有对于无向图，有 (n(n-1)/2(n(n-1)/2 条边的无向图称条边的无向图称为完全图。对于有向图，有为完全图。对于有向图，有 n(n-1)n(n-1)条弧的有向图称条弧的有向图称为有向完全图。为有向完全图。(7)(7)稀疏图稀疏图/稠密图稠密图 边或弧很少（如边或弧很少（如e e
5、nlognnlogn）的图称稀疏图，反）的图称稀疏图，反之称稠密图。之称稠密图。第8页，本讲稿共45页(8)(8)邻接点邻接点 对于对于无向图无向图G=(V,E)G=(V,E)，若边，若边(v,v(v,v)E)E，则称顶，则称顶点点 v v 和和 v v 互为互为邻接点邻接点，即，即 v v 和和 v v 相邻接。或称相邻接。或称边（边（v,vv,v）依附于依附于顶点顶点v v 和和 v v，或称（，或称（v,vv,v）和）和顶点顶点 v v 和和 v v 相关联相关联。对于对于有向图有向图G=(VG=(V，E)E)，若弧，若弧v E E，则称，则称顶点顶点 v v 邻接邻接到到顶点顶点 v
6、v，或称顶点，或称顶点 v v 邻接邻接自自顶点顶点 v v，或弧，或弧v 和顶点和顶点 v v，v v 相关联相关联。(a)(b)第9页，本讲稿共45页顶点的入度顶点的入度/出度出度 以顶点以顶点 v v 为头的弧的数目称为头的弧的数目称 v v 的入度，记为的入度，记为ID(v)ID(v)；以顶点；以顶点 v v 为尾的弧的数目称为尾的弧的数目称 v v 的出度，记的出度，记为为 OD(v)OD(v)。顶点顶点 v v 的度的度 TDTD（v v）=ID=ID（v v）ODOD（v v）(9)(9)顶点顶点v v的度的度(Degree)(Degree)是和是和v v相关联的边的数目，记为相
7、关联的边的数目，记为 TDTD（v v）。）。(a)(b)第10页，本讲稿共45页(10)(10)路径路径(Path)(Path)无向图无向图G=G=(V,E)V,E)中，从顶点中，从顶点v v到到v v的路径是顶点序列的路径是顶点序列(v=v(v=vi i0 0,v,vi i1 1,v,vi im m=v=v)，其中，其中(v(vi ij-1 j-1,v,vi ij j)E)E，1jm1jm。若若G G是有向图，则路径也是有向的，顶点序列应满足：是有向图，则路径也是有向的，顶点序列应满足：vE E，1jm1jm。路径的长度是路径上的边或弧的数目路径的长度是路径上的边或弧的数目。第11页，本讲
8、稿共45页(11)(11)回路回路/环环/简单路径简单路径 第一个顶点和最后一个顶点相同的路径称为第一个顶点和最后一个顶点相同的路径称为回路回路/环环。序列中顶点不重复出现的路径称为序列中顶点不重复出现的路径称为简单路径简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为重复出现的回路，称为简单回路或简单环简单回路或简单环。第12页，本讲稿共45页(12)(12)连通图连通图/连通分量连通分量 在在无向图无向图G G中，如果从顶点中，如果从顶点 V V 到顶点到顶点 V V 有路径，有路径，则称则称 V V 和和 V V 是连通
9、的。是连通的。若图中任意两个顶点若图中任意两个顶点 v vi i、v vj jVV，v vi i 和和 v vj j 都是连都是连通的，则称通的，则称 G G 是是连通图连通图。无向图中的无向图中的极大连通子图极大连通子图称之为称之为连通分量连通分量。第13页，本讲稿共45页左图：连通图左图：连通图下图：非连通图，但有下图：非连通图，但有 三个连通分量三个连通分量第14页，本讲稿共45页(13)(13)强连通图强连通图/强连通分量强连通分量 在在有向图有向图 G G 中，若对于每一对中，若对于每一对v vi i、v vj jVV，v vi ivvj j，从，从 v vi i 到到 v vj j
10、 和从和从 v vj j 到到 v vi i 都存在路径，则都存在路径，则称称 G G 是是强连通图强连通图。有向图中的有向图中的极大强连通子图极大强连通子图称作称作有向图的强连通分有向图的强连通分量量。第15页，本讲稿共45页非强连通图非强连通图 两个强连通分量两个强连通分量第16页，本讲稿共45页 一个连通图的生成树是一个极小连通子图，它含有一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的图中全部顶点，但只有足以构成一棵树的n-1n-1条边。条边。如果在一棵生成树上添加一条边，必定构成一个如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那
11、两个顶点之间有了第环，因为这条边使得它依附的那两个顶点之间有了第二条路径。二条路径。(14)(14)生成树生成树第17页，本讲稿共45页 如果一个有向图恰有一个顶点的入度为如果一个有向图恰有一个顶点的入度为 0 0，其余，其余顶点的入度均为顶点的入度均为 1 1，则是一棵有向树。一个有向图的生，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。有足以构成若干棵不相交的有向树的弧。(15)(15)生成森林生成森林第18页，本讲稿共45页2.2.图的抽象类型定义图的抽象类型定义ADT G
12、raph ADT Graph 数据对象数据对象V V：V V是具有相同特性的数据元素的集是具有相同特性的数据元素的集 合，称为顶点集。合，称为顶点集。数据关系数据关系R R：R=VR R=VR VR=|v,wV VR=|v,wV且且P(v,w)P(v,w)，表示从表示从v v到到w w的弧，谓词的弧，谓词P(v,w)P(v,w)定义了定义了 弧弧的意义或信息的意义或信息 基本操作基本操作P P：ADT GraphADT Graph第19页，本讲稿共45页基本操作基本操作CreateGraph(&G,V,VR);/CreateGraph(&G,V,VR);/按按V V和和VRVR的定义构造图的定
13、义构造图G GDestroyGraph(&G);/DestroyGraph(&G);/销毁图销毁图G GLocateVex(G,u);/LocateVex(G,u);/若若G G中存在顶点中存在顶点u u，则返回该顶点，则返回该顶点 /在图中位置；否则返回其它信息在图中位置；否则返回其它信息GetVex(G,v);/GetVex(G,v);/返回返回 v v 的值的值PutVex(&G,v,value);/PutVex(&G,v,value);/对对 v v 赋值赋值valuevalueFirstAdjVex(G,v);/FirstAdjVex(G,v);/返回返回v v的第一个邻接点。的第一
14、个邻接点。/若若v v在在G G中没有邻接点，则返回中没有邻接点，则返回“空空”第20页，本讲稿共45页NextAdjVex(G,v,w);/NextAdjVex(G,v,w);/返回返回v v的的(相对于相对于w w的的)下一下一 /个邻接点。若个邻接点。若w w是是v v的最后一个邻接点，则的最后一个邻接点，则“空空”InsertVex(&G,v);/InsertVex(&G,v);/在图在图G G中增添新顶点中增添新顶点v v。DeleteVex(&G,v);/DeleteVex(&G,v);/删除删除G G中顶点中顶点v v及其相关的弧及其相关的弧InsertArc(&G,v,w);/
15、InsertArc(&G,v,w);/在在G G中增添弧中增添弧，若，若G G /是无向的，则还增添对称弧是无向的，则还增添对称弧DeleteArc(&G,v,w);/DeleteArc(&G,v,w);/在在G G中删除弧中删除弧，若，若G G /是无向的，则还删除对称弧是无向的，则还删除对称弧第21页，本讲稿共45页DFSTraverse(G,v,Visit();DFSTraverse(G,v,Visit();/从顶点从顶点v v起深度优先遍历图起深度优先遍历图G G，并对每个顶点调用，并对每个顶点调用/函数函数 VisitVisit一次且仅一次。一次且仅一次。BFSTraverse(G,
16、v,Visit();BFSTraverse(G,v,Visit();/从顶点从顶点v v起广度优先遍历图起广度优先遍历图G G，并对每个顶点调用，并对每个顶点调用/函数函数 VisitVisit一次且仅一次。一次且仅一次。第22页，本讲稿共45页第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用7.6 7.6 最短路径最短路径第23页，本讲稿共45页7.2 7.2 图的存储结构图的存储结构n图的数组图的数组(邻接矩
17、阵邻接矩阵)存储表示存储表示n图的邻接表存储表示图的邻接表存储表示n有向图的十字链表存储表示有向图的十字链表存储表示n无向图的邻接多重表存储表示无向图的邻接多重表存储表示第24页，本讲稿共45页1.1.图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示 邻接矩阵邻接矩阵是用于描述图中顶点之间关系是用于描述图中顶点之间关系(即弧或边即弧或边的权的权)的矩阵。的矩阵。假设图中顶点数为假设图中顶点数为n n，则邻接矩阵，则邻接矩阵A Annnn：1 1 若若ViVi和和VjVj之间有弧或边之间有弧或边 Aij=Aij=0 0 反之反之第25页，本讲稿共45页 C CA AD DB B C CA A
18、B BDCBAA=0111101111011110A B C DA B C CBAB=010100110第26页，本讲稿共45页注意：注意：1)1)图中无邻接到自身的弧，因此邻接矩阵主对角线图中无邻接到自身的弧，因此邻接矩阵主对角线为全零。为全零。2)2)无向图的邻接矩阵必然是对称矩阵。无向图的邻接矩阵必然是对称矩阵。3)3)无向图中，顶点的度是邻接矩阵对应行（或列）的无向图中，顶点的度是邻接矩阵对应行（或列）的非零元素之和；有向图中，对应行的非零元素之和非零元素之和；有向图中，对应行的非零元素之和是该顶点的出度；对应列的非零元素之和是该顶点是该顶点的出度；对应列的非零元素之和是该顶点的入度；
19、则该顶点的度是对应行和对应列的非零元的入度；则该顶点的度是对应行和对应列的非零元素之和。素之和。第27页，本讲稿共45页V1V2V3V4V5V65485931567网的邻接矩阵网的邻接矩阵 反之反之权值权值 若若V Vi i和和V Vj j之间有弧或边之间有弧或边Aij=Aij=第28页，本讲稿共45页图的数组（邻接矩阵）存储表示图的数组（邻接矩阵）存储表示#define INFINITY INT_MAX /#define INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /#define MAX_VERTEX_NUM 20 /最大顶点个数最大
20、顶点个数typedef enum DG,DN,typedef enum DG,DN,UDUDG,G,UDUDN GraphKind;N GraphKind;/图类型（有向图图类型（有向图/网网,无向图无向图/网）网）typedef struct ArcCell typedef struct ArcCell VRType adj;/VRType VRType adj;/VRType是顶点关系类型。对无权图，用是顶点关系类型。对无权图，用1 1或或0 0 表示相邻否；表示相邻否；对带权图，则为权值类型。对带权图，则为权值类型。InfoType*info;/InfoType*info;/指向该弧相关
21、信息的指针指向该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct typedef struct VertexType vexsMAX_VERTEX_NUM;/VertexType vexsMAX_VERTEX_NUM;/描述顶点的数组描述顶点的数组 AdjMatrix arcs;/AdjMatrix arcs;/邻接矩阵邻接矩阵 int vexnum,arcnum;/int vexnum,arcnum;/图的当前顶
22、点数和弧图的当前顶点数和弧(边边)数数 GraphKind kind;/GraphKind kind;/图的种类标志图的种类标志 MGraph;MGraph;第29页，本讲稿共45页构造图的算法构造图的算法 Status CreateGraph(Mgraph&G)Status CreateGraph(Mgraph&G)/采用数组采用数组(邻接矩阵邻接矩阵)表示法，构造图表示法，构造图G G。scanf(&G.kind)scanf(&G.kind)；switch(G.kind)switch(G.kind)case DGcase DG：return CreateDG(G)return Create
23、DG(G)；/构造有向图构造有向图G G case DNcase DN：return CreateDN(G)return CreateDN(G)；/构造有向网构造有向网G G case UDGcase UDG：return CreateUDG(G)return CreateUDG(G)；/构造无向图构造无向图G Gcase UDNcase UDN：return CreateUDN(G)return CreateUDN(G)；/构造无向网构造无向网G Gdefaultdefault：return ERRORreturn ERROR；/CreateGraph/CreateGraph第30页，本讲稿
24、共45页采用数组表示法，构造无向网采用数组表示法，构造无向网G GStatus CreateUDN(MGraph&G)Status CreateUDN(MGraph&G)sacnf(&G.vexnum,&G.arcnum,&IncInfo);sacnf(&G.vexnum,&G.arcnum,&IncInfo);for(i=0;iG.vexnum;+i)scanf(&G.vexsi);for(i=0;iG.vexnum;+i)scanf(&G.vexsi);/构造顶点向量构造顶点向量for(i=0for(i=0；iG.vexnumiG.vexnum；+i)+i)/初始化邻接矩阵初始化邻接矩阵
25、for(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;for(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;/adj,info /adj,infofor(k=0for(k=0；kG.arcnumkG.arcnum；+k)+k)/构造邻接矩阵构造邻接矩阵 scanf(&v1scanf(&v1，&v2&v2，&w)&w)；/输入一条边依附的顶点及权值输入一条边依附的顶点及权值 i=LocateVex(G,v1);j=LocateVex(G,v2);i=LocateVex(G,v1);j=LocateVex(G,v2);/v1/v1
26、和和v2v2在在G G中位置中位置 G.arcsij.adj=wG.arcsij.adj=w；/弧弧v1v2的权值的权值 if(IncInfo)Input(*G.arcsij.info);if(IncInfo)Input(*G.arcsij.info);G.arcsji=G.arcsij;G.arcsji=G.arcsij;/置置的对称弧的对称弧 return OK;return OK;/CreateUDN/CreateUDN 第31页，本讲稿共45页2.2.图的邻接表存储表示图的邻接表存储表示 类似树的孩子链表。即对图中的每个顶点类似树的孩子链表。即对图中的每个顶点v vi i建立一个单链表
27、，建立一个单链表，表中结点表示依附于该顶点表中结点表示依附于该顶点v vi i的边或弧。的边或弧。邻接点域链域数据域指示与顶点vi邻接的点在图中的位置指示下一条边或弧的结点存储和边或弧相关的信息数据域链域指向链表第一个结点存储顶点vi和其他有关信息表结点表头结点第32页，本讲稿共45页V1V3V2V4V1V3V2V4例如：例如：13443214432121113442第33页，本讲稿共45页注意：注意：在无向图的邻接表中，在无向图的邻接表中，1 1）第）第i i个链表中结点数目为顶点个链表中结点数目为顶点i i的度；的度；2 2）所有链表中结点数目的一半为图中边数；）所有链表中结点数目的一半为
28、图中边数；3 3）占用的存储单元数目为）占用的存储单元数目为n+2en+2e。在有向图的邻接表中，在有向图的邻接表中，1 1）第）第i i个链表中结点数目为顶点个链表中结点数目为顶点i i的出度；的出度；2 2）所有链表中结点数目为图中弧数；）所有链表中结点数目为图中弧数；3 3）占用的存储单元数目为）占用的存储单元数目为n+en+e。第34页，本讲稿共45页 为求出每一个顶点的入度，必须另外建立有向图为求出每一个顶点的入度，必须另外建立有向图的逆邻接表。有向图的逆邻接表与邻接表类似，只是的逆邻接表。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。它是从入度考虑结点
29、，而不是从出度考虑结点。2443211逆邻接表逆邻接表3V1V3V2V4第35页，本讲稿共45页图的邻接表存储表示图的邻接表存储表示#define MAX_VERTEX_NUM 20#define MAX_VERTEX_NUM 20typedef struct ArcNode typedef struct ArcNode int adjvex;/int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode*nextarc;/struct ArcNode*nextarc;/指向下一条弧的指针指向下一条弧的指针 InfoType*info;/InfoType*
30、info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;ArcNode;typedef struct VNode typedef struct VNode VertexType data;/VertexType data;/顶点信息顶点信息 ArcNode*firstarc;/ArcNode*firstarc;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;VNode,AdjListMAX_VERTEX_NUM;typedef struct typedef struct AdjList vertices;AdjList ve
31、rtices;int vexnum,arcnum;/int vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数 int kind;/int kind;/图的种类标志图的种类标志 ALGraph;ALGraph;第36页，本讲稿共45页3.3.有向图的十字链表存储表示有向图的十字链表存储表示 十字链表是有向图的另一种链式存储结构。可以理十字链表是有向图的另一种链式存储结构。可以理解成解成有向图的邻接表和逆邻接表的结合有向图的邻接表和逆邻接表的结合，在十字链表，在十字链表中，有两种结点结构：中，有两种结点结构：尾域tailvex头域headvex链域hlink链域tlink信息
32、域info数据域data链域firstin链域firstout顶点结点顶点结点弧结点弧结点第37页，本讲稿共45页尾域尾域tv tv 指示弧尾顶点在图中的位置指示弧尾顶点在图中的位置头域头域hv hv 指示弧头顶点在图中的位置指示弧头顶点在图中的位置链域链域h h 指向弧头相同的下一条弧指向弧头相同的下一条弧链域链域t t 指向弧尾相同的下一条弧指向弧尾相同的下一条弧信息域信息域 指向该弧的相关信息指向该弧的相关信息尾域tailvex头域headvex链域hlink链域tlink信息域info数据域data链域firstin链域firstout数据域数据域 存储和顶点相关信息存储和顶点相关信息
33、链域链域fin fin 指向以该顶点为弧头的第一个弧结点指向以该顶点为弧头的第一个弧结点链域链域fout fout 指向以该顶点为弧尾的第一个弧结点指向以该顶点为弧尾的第一个弧结点第38页，本讲稿共45页v v1 1v v2 2v v3 3v v4 4 0 1 2 3 10/20v3v1v4v2/03/13/2302/32例：例：datafirstinfirstouttailvexheadvex hlinktlink/第39页，本讲稿共45页有向图的十字链表存储表示有向图的十字链表存储表示#define MAX_VERTEX_NUM 20#define MAX_VERTEX_NUM 20typ
34、edef struct ArcBox typedef struct ArcBox int tailvex,headvex;/int tailvex,headvex;/该弧的尾和头顶点的位置该弧的尾和头顶点的位置 struct ArcBox*hlink,*tlink;/struct ArcBox*hlink,*tlink;/分别指向下一个弧头相同分别指向下一个弧头相同 和弧尾相同的弧的指针域和弧尾相同的弧的指针域 InfoType*info;/InfoType*info;/该弧相关信息的指针该弧相关信息的指针 ArcBoxArcBox;typedef struct VexNode typedef
35、 struct VexNode VertexType data;VertexType data;ArcBox*firstin,*firstout;/ArcBox*firstin,*firstout;/分别指向该顶点第一条入弧分别指向该顶点第一条入弧 和出弧和出弧 VexNodeVexNode;typedef struct typedef struct VexNode xlistMAX_VERTEX_NUM;/VexNode xlistMAX_VERTEX_NUM;/表头向量表头向量 int vexnum,arcnum;/int vexnum,arcnum;/有向图的当前顶点数和弧数有向图的当前
36、顶点数和弧数 OLGraph;OLGraph;第40页，本讲稿共45页4.4.无向图的邻接多重表存储表示无向图的邻接多重表存储表示 在无向图的邻接表中，每条边（在无向图的邻接表中，每条边（V Vi i，V Vj j）由两个结点）由两个结点表示，一个结点在第表示，一个结点在第 i i 个链表中，另一个结点在第个链表中，另一个结点在第 j j 个链表中，当需要对边进行操作时，就需找到表示同个链表中，当需要对边进行操作时，就需找到表示同一条边的两个结点，这给操作带来不便，在这种情况一条边的两个结点，这给操作带来不便，在这种情况下采用下采用邻接多重表邻接多重表较方便。较方便。邻接多重表中结点分为：邻接
37、多重表中结点分为：边结点和顶点结点边结点和顶点结点第41页，本讲稿共45页标志域标志域 用于标记该边是否被搜索过用于标记该边是否被搜索过边顶点边顶点i i 该边依附的顶点该边依附的顶点v vi i在图中的位置在图中的位置边顶点边顶点j j 该边依附的顶点该边依附的顶点v vj j在图中的位置在图中的位置链域链域i i 指向下一条依附于顶点指向下一条依附于顶点v vi i的边的边链域链域j j 指向下一条依附于顶点指向下一条依附于顶点v vj j的边的边信息域指向和边相关的各种信息的指针域信息域指向和边相关的各种信息的指针域数据域数据域 存储和该顶点相关的信息存储和该顶点相关的信息边链域指示第一
38、条依附于该顶点的边边链域指示第一条依附于该顶点的边标志域边顶点i边顶点j链域i 链域j 信息域数据域边链域第42页，本讲稿共45页1 3 4 2 例例1234121324第43页，本讲稿共45页无向图的邻接多重表存储表示无向图的邻接多重表存储表示#define MAX_VERTEX_NUM 20#define MAX_VERTEX_NUM 20typedef emnu unvisited,visited VisitIf;typedef emnu unvisited,visited VisitIf;typedef struct Ebox typedef struct Ebox VisitIf m
39、ark;/VisitIf mark;/访问标记访问标记 int ivex,jvex;/int ivex,jvex;/该边依附的两个顶点的位置该边依附的两个顶点的位置 struct EBox*ilink,*jlink;/struct EBox*ilink,*jlink;/分别指向依附这两个顶点的分别指向依附这两个顶点的 下一条边下一条边 InfoType*info;/InfoType*info;/该边信息指该边信息指针针 EBoxEBox;typedef struct VexBox typedef struct VexBox VertexType data;VertexType data;EBo
40、x*firstedge;/EBox*firstedge;/指向第一条依附该顶点的边指向第一条依附该顶点的边 VexBoxVexBoxtypedef struct typedef struct VexBox adjmulistMAX_VERTEX_NUM;VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;/int vexnum,edgenum;/无向图的当前顶点数和边数无向图的当前顶点数和边数 AMLGraph;AMLGraph;第44页，本讲稿共45页1.1.理解图的定义，掌握图的常用术语；理解图的定义，掌握图的常用术语；2.2.掌握常见的图的存储结构，以及各种存储结构掌握常见的图的存储结构，以及各种存储结构的特点，在应用时可以根据对图的操作需要加以的特点，在应用时可以根据对图的操作需要加以选取。选取。作业作业P47P47：7.17.1、7.157.15小结小结第45页，本讲稿共45页