第7章图图的基本概念与存储

1、第第7章章 图图 2图的基本概念及基本术语图的基本概念及基本术语图的表示法图的表示法图的遍历图的遍历最小生成树最小生成树最短路径最短路径拓扑排序拓扑排序主要内容主要内容 3v线性表结构：线性关系线性表结构：线性关系v除了起始结点与终止结点外，每个结点只有一个直除了起始结点与终止结点外，每个结点只有一个直接前驱和一个直接后继接前驱和一个直接后继v树形结构：层次关系树形结构：层次关系v除了根结点外，每个结点只有一个父结点，但可以除了根结点外，每个结点只有一个父结点，但可以有多个儿子结点有多个儿子结点v图：非线性结构更加复杂图：非线性结构更加复杂v每个结点每个结点(顶点顶点)既可以有前驱结点也可以有

2、后继结既可以有前驱结点也可以有后继结点，且个数不加限制。点，且个数不加限制。基本数据结构小结基本数据结构小结 4基本概念基本概念-图图Graph=(V,R)V V是顶点的非空是顶点的非空有限集有限集R是边的有限集是边的有限集,可为空集可为空集有向图有向图无向图无向图简单分类：简单分类： 5弧弧1,2：边边弧弧弧尾弧尾弧头弧头 6有向图：有向图：G1 = V , RV(G1) = 1, 2, 3, 4 R(G1) = , , , , 无向图：无向图：G2 = V , RV(G2) = 1, 2, 3, 4, 5 R (G2)= (1,2), (1,4), (2,3), (2,5), (3,4),

3、 (3,5)有序对有序对无序对无序对 7简单图简单图:不考虑顶点到其自身的边不考虑顶点到其自身的边,即即(u,v)是图是图G的的边，则边，则uv；且，如果图中没有相同的边；且，如果图中没有相同的边,则称图为则称图为简单图简单图以下学习的皆是简单图的以下学习的皆是简单图的情况！情况！图的其它分类图的其它分类 8完全图完全图:设设|V|=n, |E|=e。对有向图对有向图G，若，若e=n(n-1)，则称，则称G为完全的有向为完全的有向图图;对无向图对无向图G，若，若e=n(n-1)/2;则称则称G为完全的无向为完全的无向图。图。 完全图具有最多的边数，完全图具有最多的边数，任一对顶点都有边相连任一

4、对顶点都有边相连有向完全图有向完全图无向完全图无向完全图 9稀疏图稀疏图:有很少条边的图（有很少条边的图（e1EdgeAEjiEjiji 29无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。01230101101001011010A.edge012000101010A.edge 30n 在有向图中在有向图中, 统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的出的出度，统计第度，统计第 j 列列 1 的个数可得顶点的个数可得顶点 j 的入度。的入度。n 在无向图中在无向图中, 统计第统计第 i 行行 (列列) 1

5、的个数可得顶点的个数可得顶点i 的的度。度。 3186312954203168532941A.edge赋权有向图的邻接矩阵表示赋权有向图的邻接矩阵表示 32typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点数组顶点数组 AdjMatrix arcs; /矩阵矩阵 int vexnum, um; /顶点数与边顶点数与边(弧弧)数数 GraphKind kind; /图的种类图的种类 MGraph; 图的邻接矩阵表示图的邻接矩阵表示 33typedef enumDG, DN, AG, ANGraphKind; /图的种类图的种类(有向图，有向网，无向

6、图，无向网有向图，有向网，无向图，无向网)图的邻接矩阵表示图的邻接矩阵表示const MAX_VERTEX_NUM=20; /最大顶点个数最大顶点个数typedef char VertexType; /顶点类型顶点类型(根据实际情况设定根据实际情况设定) 34typedef struct ArcCell VRType adj; /VRType是顶点关系类型。是顶点关系类型。 /对无权图，是对无权图，是1与与0；对带权图，为权值信息；对带权图，为权值信息 InfoType *info; /指向该弧相关信息的指针指向该弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUM

7、MAX_VERTEX_NUM;/邻接矩阵类型邻接矩阵类型图的邻接矩阵表示图的邻接矩阵表示 35图的邻接表图的邻接表 (Adjacency List)表示法表示法同一个顶点发出的边链接在同一个边链表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边每一个链结点代表一条边(边结点边结点), 结点中有结点中有另一顶点的下标另一顶点的下标 dest 和指针和指针 next。ABCDdata adjABCD0123dest nextdest next 130210无向图的邻接表无向图的邻接表 36ABCdata adjABC012dest nextdest next data adjAB

8、C012dest next102 011无向图的邻接表无向图的邻接表邻接表邻接表 (出边表出边表)逆邻接表逆邻接表 (入边表入边表) 37BACD69528data adjABCD0123 dest cost next 1 53 62 83 2(出边表出边表)(顶点表顶点表)网络网络 (带权图带权图) 的邻接表的邻接表1 9 38const MAX_VERTEX_NUM=20;typedef struct ArcNode int adjvex; /该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nexarc; /指向下一条弧的指针指向下一条弧的指针 InfoTyp

9、e *info; /指向该弧相关信息的指针指向该弧相关信息的指针ArcNode;typedef struct vNode VertexType data; /顶点信息顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧指向第一条依附该顶点的弧VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, um; /图的当前顶点数和弧数图的当前顶点数和弧数 int kind; /图的种类图的种类ALGraph; 用邻接表实现有向图用邻接表实现有向图 39BACD69528data adjABCD0123 dest cost next 1 53 62 83 21 9vertices:数组名数组名AdjListMAX_VERTEX_NUM类型类型最多容纳最多容纳20个元素个元素 40BACD69528ABCD0123 1 53 62 83 21 9vertices:数组名数组名AdjListMAX_VERTEX_NUM类型类型最多容纳最多容纳20个元素个元素datafirstarc 41BACD69528ABCD0123 1 53 62 83 21 9verti