4.2 图的存储结构(cont.) v1 v2 v3 v4 v5 vertex= v1 v2 v3 v4 v5 v1 0 1 0 0 0 邻接矩阵 （Adjacency Matrix）表示（数组表示法） 有向图的邻接矩阵： 存储结构特点： 有向图的邻接矩阵一定不对称吗？ 问题：1.如何求顶点vi的出度？ 2. 如何判断顶点 vi和 vj 之间是否存在有向边？ 3.如何求邻接于顶点 vi的所有顶点？ 4.如何求邻接到顶点 vi的所有顶点？ v1 v2 v3 v4 v5 vertex= v1 v2 v3 v4 v5 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 v1 v2 v3 v4 v5 edge = v1 v2 v3 v4 v5 2019/7/19

4.2 图的存储结构(cont.) v1 v2 v3 v4 v5 v1 0 1 0 0 0 v2 0 0 1 0 0 v3 邻接矩阵 （Adjacency Matrix）表示（数组表示法） 存储结构定义： typedef struct { VertexData verlist [NumVertices]; //顶点表 EdgeData edge[NumVertices][NumVertices]; //邻接矩阵—边表, 可视为边之间的关系 int n, e; //图的顶点数与边数 } MTGraph; 假设图G有n个顶点e条边，则该图的存储需求为O(n+n2) = O(n2) ，与边的条数e无关。 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 v1 v2 v3 v4 v5 edge= v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 vertex 2019/7/19

4.2 图的存储结构(cont.) v1 v2 v3 v4 v5 v1 0 1 0 0 0 v2 0 0 1 0 0 v3 存储结构的建立----算法实现的步骤： 1.确定图的顶点个数n和边数e； 2.输入顶点信息存储在一维数组vertex中； 3.初始化邻接矩阵； 4.依次输入每条边存储在邻接矩阵edge中； 4.1 输入边依附的两个顶点的序号i, j； 4.2 将邻接矩阵的第i行第j列的元素值置为1； 4.3 将邻接矩阵的第j行第i列的元素值置为1。 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 v1 v2 v3 v4 v5 edge= v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 vertex 2019/7/19

4.2 图的存储结构(cont.) 存储结构的建立算法的实现： void CreateMGragh (MTGragh *G) //建立图的邻接矩阵 { int i, j, k, w; cin>>G→n>>G→e; //1.输入顶点数和边数 for (i=0; i<G→n; i++) //2.读入顶点信息，建立顶点表 G→vertlist[i]=getchar( ); for (i=0; i<G→n; i++) for (j=0;j<G→n;j++) G→edge[i][j]=0; //3.邻接矩阵初始化 for (k=0; k<G→e; k++) { //4.读入e条边建立邻接矩阵 cin>>i>>j>>w; // 输入边（i,j）上的权值w G→ edge[i][j]=w; G→ edge[j][i]=w; } } //时间复杂度：T = O( n+ n2 +e) 。当e < <n, T = O( n2 ) ？ 2019/7/19

4.2 图的存储结构(cont.) vertex firstedge adjvex next v0 v1 v2 v3 v4 1 ∧ 3 v2 邻接表（Adjacency List）表示 无向图的邻接表： 对于无向图的每个顶点vi，将所有与vi相邻的顶点链成一个单链表，称为顶点vi的边表（顶点vi的邻接表）； 再把所有边表的指针和存储顶点信息的一维数组构成顶点表。 vertex firstedge adjvex next v0 v1 v2 v3 v4 1 2 3 4 1 ∧ 3 v2 v0 v3 v4 v1 ∧ 2 4 1 ∧ 3 4 ∧ 2 ∧ 1 2 顶点表 边表 2019/7/19

4.2 图的存储结构(cont.) 1 ∧ 3 2 4 顶点表 边表 v0 v1 v2 v3 v4 v2 v0 v3 v4 v1 无向图的邻接表存储的特点: 边表中的结点表示什么? 如何求顶点 vi的度？ 如何判断顶点vi和顶点vj之间是否存在边? 如何求顶点 vi的所有邻接点? 空间需求O(n+2e) 1 ∧ 3 2 4 adjvex next vertex firstedge 顶点表 边表 v0 v1 v2 v3 v4 v2 v0 v3 v4 v1 2019/7/19

4.2 图的存储结构(cont.) v0 v1 v2 v3 v4 ∧ 1 ∧ 2 ∧ 4 3 2 4 ∧ 3 ∧ 1 顶点表 出边表 v0 邻接表（Adjacency List）表示 有向图的邻接表---正邻接表 对于有向图的每个顶点vi，将邻接于vi的所有顶点链成一个单链表，称为顶点vi的出边表； 再把所有出边表的指针和存储顶点信息的一维数组构成顶点表。 vertex firstedge v0 v1 v2 v3 v4 1 2 3 4 ∧ 1 v0 v1 v2 v3 v4 ∧ 2 adjvex next ∧ 4 3 2 4 ∧ 3 ∧ 1 顶点表 出边表 2019/7/19

4.2 图的存储结构(cont.) ∧ 1 2 4 3 顶点表 出边表 v0 v1 v2 v3 v4 v0 v1 v2 v3 v4 有向图的正邻接表的存储特点 出边表中的结点表示什么？ 如何求顶点 vi的出度？如何求顶点 vi的入度？ 如何判断顶点 vi和顶点vj之间是否存在有向边? 如何求邻接于顶点 vi的所有顶点? 如何求邻接到顶点 vi的所有顶点? 空间需求:O(n+e) ∧ 1 2 4 3 adjvex next vertex firstedge 顶点表 出边表 v0 v1 v2 v3 v4 v0 v1 v2 v3 v4 2019/7/19

4.2 图的存储结构(cont.) v0 v1 v2 v3 v4 ∧ 3 4 ∧ ∧ 1 3 2 4 ∧ 3 ∧ 2 顶点表 入边表 v0 邻接表（Adjacency List）表示 有向图的邻接表----逆邻接表 对于有向图的每个顶点vi，将邻接到vi的所有顶点链成一个单链表，称为顶点vi的入边表； 再把所有入边表的指针和存储顶点信息的一维数组构成顶点表。 vertex firstedge v0 v1 v2 v3 v4 1 2 3 4 ∧ 3 adjvex next v0 v1 v2 v3 v4 4 ∧ ∧ 1 3 2 4 ∧ 3 ∧ 2 顶点表 入边表 2019/7/19

4.2 图的存储结构(cont.) ∧ 3 1 2 4 顶点表 入边表 v0 v1 v2 v3 v4 v0 v1 v2 v3 v4 有向图的逆邻接表的存储特点 出边表中的结点表示什么？ 如何求顶点 vi的入度？如何求顶点 vi的出度？ 如何判断顶点 vi和顶点vj之间是否存在有向边? 如何求邻接到顶点 vi的所有顶点? 如何求邻接于顶点 vi的所有顶点? 空间需求:O(n+e) ∧ 3 1 2 4 adjvex next vertex firstedge 顶点表 入边表 v0 v1 v2 v3 v4 v0 v1 v2 v3 v4 2019/7/19

4.2 图的存储结构(cont.) 边表结点 adjvex cost next 顶点表结点 vertex firstedge 邻接表存储结构的定义 typedef struct node {//边表结点 int adjvex; //邻接点域（下标） EdgeData cost; //边上的权值 struct node *next; //下一边链接指针 } EdgeNode; typedef struct { //顶点表结点 VertexData vertex; //顶点数据域 EdgeNode * firstedge;//边链表头指针 } VertexNode; typedef struct { //图的邻接表 VertexNode vexlist [NumVertices]; int n, e; //顶点个数与边数 } AdjGraph; adjvex cost next 边表结点 vertex firstedge 顶点表结点 2019/7/19

4.2 图的存储结构(cont.) ∧ 1 2 4 3 顶点表 出边表 v0 v1 v2 v3 v4 v0 v1 v2 v3 v4 adjvex next vertex firstedge 顶点表 出边表 v0 v1 v2 v3 v4 2019/7/19

4.2 图的存储结构(cont.) v0 v1 v2 v3 v4 邻接表存储结构建立算法实现的步骤： 1. 确定图的顶点个数和边的个数； 2. 建立顶点表： 2.1 输入顶点信息； 2.2 初始化该顶点的边表； 3. 依次输入边的信息并存储在边表中； 3.1 输入边所依附的两个顶点的序号tail和head和权值w； 3.2 生成邻接点序号为head的边表结点p； 3.3 设置边表结点p； 3.4 将结点p插入到第tail个边表的头部； v0 v1 v2 v3 v4 2019/7/19

4.2 图的存储结构(cont.) v0 v1 v2 v3 v4 邻接表存储结构建立算法的实现： void CreateGraph (AdjGraph G) { cin >> G.n >> G.e; //1.输入顶点个数和边数 for ( int i = 0; i < G.n; i++) { //2.建立顶点表 cin >> G.vexlist[i].vertex; //2.1输入顶点信息 G.vexlist[i].firstedge = NULL; } //2.2边表置为空表 for ( i = 0; i < G.e; i++) { //3.逐条边输入,建立边表 cin >> tail >> head >> weight; //3.1输入 EdgeNode * p = new EdgeNode; //3.2建立边结点 p→adjvex = head; p→cost = weight; //3.3设置边结点 p→next = G.vexlist[tail].firstedge; //3.4链入第 tail 号链表的前端 G.vexlist[tail].firstedge = p; p = new EdgeNode; p→adjvex = tail; p→cost = weight; p→next = G.vexlist[head].firstedge; //链入第 head 号链表的前端 G.vexlist[head].firstedge = p; } } //时间复杂度：O(2e+n) v0 v1 v2 v3 v4 2019/7/19

4.2 图的存储结构(cont.) 空间性能 时间性能 适用范围 唯一性 邻 接 矩 阵 表 O（n2） O（n2） O（n+e） 稠密图 图的存储结构的比较——邻接矩阵和邻接表 空间性能 时间性能 适用范围 唯一性 邻 接 矩 阵 表 O（n2） O（n2） O（n+e） 稠密图 稀疏图 唯一？ 不唯一？ O（n+e） 2019/7/19

ivex jvex jlink ilink info data firstin firstout 十字链表(有向图) 十字链表是有向图的另一种链式存储结构。 将有向图的邻接表和逆邻接表结合起来的结构。 在十字链表中有两种结点： 弧结点：存储每一条弧的信息，用链表链接在一起。 顶点结点：存储每一个顶点的信息，使用一维数组来存储。 弧结点结构: ivex jvex jlink ilink info 顶点结点结构: data firstin firstout 2019/7/19

V2 V4 V1 V3 ^ 0 2 0 1 2 3 2 0 3 2 3 1 3 0 V1 V2 V3 V4 1 2 3 顶点结点 弧结点 2019/7/19

十字链表中既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度。 2019/7/19

mark ivex ilink jvex jlink info data firstedge 邻接多重表(无向图) 邻接多重表是无向图的另一种链式表示结构。 和十字链表类似。邻接多重表中，每一条边用一个结点表示。 在邻接多重表中有两种结点： 边结点：存储每一条边的信息，用链表链接在一起。 顶点结点：存储每一个顶点的信息，使用一维数组来存储。 边结点结构: mark ivex ilink jvex jlink info 顶点结点结构: data firstedge 2019/7/19

V1 V5 V4 V2 V3 1 2 3 V1 V3 V4 V2 4 V5 0 1 0 3 2 3 2 1 2 4 4 1 ^ 2019/7/19

2019/7/19