数据结构第六章图-高职高专(第四版)课件

第6章图第6章图第6章图学习目的要求:掌握图的基本概念。熟练掌握图的存储结构。熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。掌握最小生成树的普里姆和克鲁斯卡尔算法。掌握最短路径的两个经典算法:迪杰斯特拉和弗洛伊德算法。掌握拓扑排序的概念，会求拓扑序列。了解关键路径。第6章图学习目的要求:掌握图的基本概念。本章内容6.1图的基本术语6.2图的存储结构6.3图的遍历6.4最小生成树6.5最短路径6.6拓扑排序6.7关键路径图(Graph)是一种典型的非线性结构，它较线性结构与树形结构更复杂。在线性表中，数据元素满足唯一的线性关系，每一个元素(第一个和最后一个除外)有且仅有一个直接前驱和直接后继；在树形结构中，数据元素有明显的层次关系，即每个元素只有一个直接前驱，但可以有多个直接后继；在图形结构中，数据元素之间的关系是任意的，每个元素即可以有多个直接前驱，也可以有多个直接后继。图的最早应用可追溯到18世纪，伟大的数学家欧拉(Euler)利用图解决了著名的哥尼斯堡七桥问题，这一创举为图在现代科学技术领域的应用奠定了基础。图的应用十分广泛，已渗透到诸如电子线路分析、系统工程、人工智能和计算机科学领域。本章内容6.1图的基本术语6.5最短路径图(Graph)6.1图的基本术语6.1.1图的定义1.图(Graph)图是一种数据结构，图中的数据元素通常称作顶点(Vertex)，V是顶点的有穷非空集合；VR是两个顶点间关系的集合。若<v,w>∈VR，则<v,w>表示从V到W的一条弧(Arc)，且称v为弧尾(Tail)或初始点(Initialnode)，称w为弧头(Head)或终端点(Terminalnode)，此时的图称为有向图(Digraph)。若<v,w>∈VR必有<w,v>∈VR，即VR是对称的，则以无序偶对(v,w)代替这两个有序偶对，此无序偶对(v,w)表示v和w之间的一条边(Edge)，此时的图称为无向图(Undigraph)。若图G中只有顶点而没有边，称为零图。对如下的无向图G1和有向图G2可表示为：6.1图的基本术语6.1.1图的定义1.图(Graph6.1图的基本术语G1=（V1，{A1}）其中：V1={v0,v1,v2,v3}A1={(v0,v1),(v0,v2),(v3,v1),(v3,v2)}G2=（V2，{E2}）其中：V2={v0,v1,v2}E2={<v0,v1>,<v0,v2>,<v1,v2>}6.1.2图的基本术语1.完全图（CompletedGraph）无向完全图:若一个无向图有n个顶点，且每一个顶点与其他n-1个顶点之间都有边，这样的图称为无向完全图。对于一个具有n个顶点的无向完全图，它共有n(n-1)/2条边。有向完全图:

若一个有向图有n个顶点，且每一个顶点与其他

n-1个顶点之间都有一条以该顶点为起点的弧，这样的图称为有向完全图。对于一个具有n个顶点的有向完全图，它共有n(n-1)条弧。6.1图的基本术语G1=（V1，{A1}）6.1.2图的6.1图的基本术语2.子图（Subgraph）设有两个图A和B且满足条件:V(B)是V(A)的子集，E(B)是E(A)的子集或A(B)是A(A)的子集，则称图B是图A的子图。6.1图的基本术语2.子图（Subgraph）6.1图的基本术语3.路径(Path)在无向图G=(V,{E})中，从顶点Vp到Vq的一条路径是顶点序列(Vp,Vi1,Vi2,…，Vin,Vq)且(Vp,Vi1),(Vi1,Vi2),…,(Vin,Vq)是E(G)中的边。对于有向图G=(V,{A})，从顶点Vp到Vq的一条路径是顶点序列(Vp,Vi1,Vi2,…，Vin,Vq)应满足<Vp,Vi1>,<Vi1,Vi2>,…,<Vin,Vq>是A中的弧，其路径也是有向的。路径上边或弧的数目称为路径长度。4.简单路径序列中顶点不重复出现的路径称为简单路径。5.回路（Cycle）和简单回路在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或环。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。6.1图的基本术语3.路径(Path)6.1图的基本术语6.连通图(ConnectedGraph)和强连通图在无向图G中，若从Vi到Vj有路径，则称Vi和Vj是连通的。若G中任意两顶点都是连通的，则称G是连通图。对于有向图而言，若有向图G中每一对不同顶点Vi和Vj之间有从Vi到Vj和从Vj到Vi的路径，则称G为强连通图。6.1图的基本术语6.连通图(ConnectedGr6.1图的基本术语7.连通分量和强连通分量连通分量指的是无向图G中的极大连通子图。强连通分量指的是有向图G中的极大强连通子图。注意:这里是极大而不是最大。8.邻接点（Adjacent）和相关边对于无向图G=(V,E)，若(Vi,Vj)是E(G)中的一条边，则称顶点Vi和Vj互为邻接点，即Vi和Vj相邻接，边(V0,V2)是与顶点V0与V2相关联的边。对于有向图G=(V,A)，若<Vi,Vj>是A(G)中的一条弧，则称顶点Vi邻接到顶点Vj，顶点Vj邻接于顶点Vi，而弧<Vi,Vj>则是与顶点Vi和Vj相关联的弧。6.1图的基本术语7.连通分量和强连通分量8.邻接点（6.1图的基本术语

9.度(Degree)、入度(Indegree)和出度(Outdegree)所谓顶点的度，就是指和该顶点相关联的边或弧的数目。在有向图中，以终止于该顶点的弧的数目称为该顶点的入度;以起始于该顶点的弧的数目称为该顶点的出度;某顶点的入度和出度之和称为该顶点的度。顶点V0的度为3；顶点V1的度为2。顶点V0的入度为1，出度为2，度为3；顶点V1的入度为2，出度为1，度为3；顶点V2的入度为1，出度为1，度为2。6.1图的基本术语9.度(Degree)、入度(Ind6.1图的基本术语10.权和网(Net)在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权。边上带权的图称为带权图，也称为网。6.1图的基本术语10.权和网(Net)6.2图的存储结构6.2.1邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵，可以用一个二维数组来表示。设G=(V,E)

是具有n个顶点的图，顶点序号依次为0，1，2，…，n-1，则G的邻接矩阵是如下定义的n阶方阵:a[i][j]={1对于无向图，(Vi,Vj)∈E(G)；对于有向图，<Vi,Vj>∈E(G)0其他对于带权图(网)的邻接矩阵可以定义为:a[i][j]=Wi对于无向图，(Vi,Vj)∈E(G)；对于有向图，<Vi,Vj>∈E(G)；Wi为权∞其他{图的存储结构有多种，存储结构的选择取决于具体的应用和需要进行的运算。下面给出三种常用的存储结构：邻接矩阵、邻接表和边集数组。6.2图的存储结构6.2.1邻接矩阵邻接矩阵是表示顶点之6.2图的存储结构在图的邻接矩阵中，无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。并且从邻接矩阵很容易判定任意两个顶点之间是否有边存在，并易于求得各个顶点的度。对于无向图，顶点Vi的度是邻接矩阵中第i行（或第i列）的非零元素的个数。对于有向图，顶点Vi的度是邻接矩阵中第i行和第i列的非零元素的个数之和;顶点Vi的出度是邻接矩阵中第i行的非零元素的个数;顶点Vi的入度是邻接矩阵中第i列的非零元素的个数。G1和G2的邻接矩阵分别是矩阵A1、A2有向带权图和无向带权图的邻接矩阵分别是A3、A46.2图的存储结构在图的邻接矩阵中，无向图的邻接矩阵是对称6.2图的存储结构在C语言中，图的邻接矩阵的存储表示如下：#defineMAX_VERTEX_NUM66#defineINFINITY1e6typedefintVRType;//顶点间关系类型typedefintVertexType;//顶点类型enumGraphKind{DG=0,DN=1,UDG=2,UDN=3};//图的种类typedefstructArcCell{//矩阵元素类型

VRTypeadj;//VRType是顶点关系类型。对无权图，用0或1表示相邻与否；对带权图，则为权值类型

InfoType*info;//该弧相关信息指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{

VertexTypevexs[MAX_VERTEX_NUM];//顶点数组

AdjMatrixarcs;//邻接矩阵

intvexnum,arcnum;//图的顶点数和弧数

GraphKindkind;//图的种类}MGraph;6.2图的存储结构在C语言中，图的邻接矩阵的存储表示如下：6.2图的存储结构根据邻接矩阵的定义，可以得出建立图的邻接矩阵的C++算法如下：6.2.2邻接表邻接表(AdjacencyList)是图的一种链式存储结构。在邻接表中，对图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为起点的弧)。每个结点由三个域组成，其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextard)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了设有链域(firstarc)指向链表中的第一个结点外，还设有存储顶点vi的名称或其它有关信息的数据域(data)。这些表头结点通常以顺序结构的形式存储，以便随机地访问任一顶点的链表。图G1和图G2的邻接表如下图所示。一个图的邻接表存储结构可形式地说明如下。6.2图的存储结构根据邻接矩阵的定义，可以得出建立图的邻接6.2图的存储结构typedefintInfoType;typedefintVertexType;typedefstructArcNode{//边或弧结点类型

intadjvex;//与该边或弧所关联的顶点在图中的位置(即在顶点数组中的下标)

structArcNode*nextarc;//指向下一个边或弧结点的指针

InfoType*info;//该边或弧相关信息的指针}ArcNode;typedefstructVNode{//表头结点类型

VertexTypedata;//顶点信息

ArcNode*firstarc;//指向依附于该顶点的第一条边或弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{//以邻接表表示的图的存储结构

AdjListvertices;//表头数组

intvexnum,arcnum;//顶点数和边或弧的条数

GraphKindkind;//图的种类}ALGraph;6.2图的存储结构typedefintInfoType6.2图的存储结构若无向图中有n个顶点、e条边，则它的邻接表需要n个头结点和2e个边结点。显然，在边稀疏的情况下，用邻接表比用邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。在无向图的邻接表中，顶点vi的度恰为第i个链表中结点的个数；而在有向图中，第i个链表中的结点数只是顶点vi的出度，为求入度必须遍历整个邻接表。在整个邻接表中其邻接点域的值为i的结点个数是顶点vi的入度。有时，为了便于确定顶点的入度或以顶点vi为终点的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi建立一个链接以vi为终点的弧的表。6.2图的存储结构若无向图中有n个顶点、e条边，则它的邻接6.2图的存储结构建立图的邻接表的C++程序见Graph2.cpp6.2图的存储结构建立图的邻接表的C++程序见Graph26.2图的存储结构6.2.3边集数组带权图(网)的另一种存储结构是边集数组，它适用于一些以边为主的操作。用边集数组表示带权图时，列出每条边所依附的两个顶点及边上的权，即每个数组元素代表一条边的信息。例如，下图的边集数组是：016133346422205501515536544525在这个边集数组中第一列是边的起点，第二列是边的终点，第三列是边的权值。每一行表示一条边。6.2图的存储结构6.2.3边集数组016在这个边集6.2图的存储结构6.2.4十字链表十字链表是有向图的另一种链式存储结构。可以看成将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中的每一条弧有一个结点，对应于每一个顶点也有一个结点。这些结点的结构如下所示：在弧结点中有5个域：其中尾域(tailvex)和头域(headvex)分别指示弧尾和弧头这两个顶点在图中的位置(即在顶点数组中的下标)，链域(hlink)指向弧头相同的下一条弧，而链域(tlink)指向弧尾相同的下一条弧，info域指向该弧的相关信息。弧头相同的弧在同一个链表上，弧尾相同的弧也在同一个链表上。它们的头结点就是顶点结点，它由三个域组成：其中data域存储和顶点相关的信息，如顶点的名称等；firstin和firstout是两个链域，分别指向以该顶点为弧头或弧尾的第一个弧结点。下图给出了一个有向图及其十字链表。6.2图的存储结构6.2.4十字链表十字链表是有向图的另6.2图的存储结构有向图的十字链表存储表示的形式说明如下所示：#defineMAX_VERTEX_NUM36typedefintInfoType;typedefstructArcBox{

inttailvex,headvex;

structArcBox*hlink,*tlink;

InfoTypeinfo;//弧的权值}ArcBox;//弧结点类型6.2图的存储结构有向图的十字链表存储表示的形式说明如下所6.2图的存储结构typedefstructVexNode{

VertexTypedata;//顶点名称

ArcBox*firstin,*firstout;}VexNode;//顶点结点类型typedefstruct{

VexNodexlist[MAX_VERTEX_NUM];//顶点数组

intvexnum,arcnum;//图中的顶点数和弧数}OLGraph;//图的十字链表存储结构类型只要输入n个顶点和e条弧的信息，便可建立该有向图的十字链表，其算法请见程序Graph3.cpp。6.2图的存储结构typedefstructVexNo6.2图的存储结构6.2图的存储结构6.2图的存储结构6.2图的存储结构第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图第6章图学习目的要求:掌握图的基本概念。熟练掌握图的存储结构。熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。掌握最小生成树的普里姆和克鲁斯卡尔算法。掌握最短路径的两个经典算法:迪杰斯特拉和弗洛伊德算法。掌握拓扑排序的概念，会求拓扑序列。了解关键路径。第6章图学习目的要求:掌握图的基本概念。本章内容6.1图的基本术语6.2图的存储结构6.3图的遍历6.4最小生成树6.5最短路径6.6拓扑排序6.7关键路径图(Graph)是一种典型的非线性结构，它较线性结构与树形结构更复杂。在线性表中，数据元素满足唯一的线性关系，每一个元素(第一个和最后一个除外)有且仅有一个直接前驱和直接后继；在树形结构中，数据元素有明显的层次关系，即每个元素只有一个直接前驱，但可以有多个直接后继；在图形结构中，数据元素之间的关系是任意的，每个元素即可以有多个直接前驱，也可以有多个直接后继。图的最早应用可追溯到18世纪，伟大的数学家欧拉(Euler)利用图解决了著名的哥尼斯堡七桥问题，这一创举为图在现代科学技术领域的应用奠定了基础。图的应用十分广泛，已渗透到诸如电子线路分析、系统工程、人工智能和计算机科学领域。本章内容6.1图的基本术语6.5最短路径图(Graph)6.1图的基本术语6.1.1图的定义1.图(Graph)图是一种数据结构，图中的数据元素通常称作顶点(Vertex)，V是顶点的有穷非空集合；VR是两个顶点间关系的集合。若<v,w>∈VR，则<v,w>表示从V到W的一条弧(Arc)，且称v为弧尾(Tail)或初始点(Initialnode)，称w为弧头(Head)或终端点(Terminalnode)，此时的图称为有向图(Digraph)。若<v,w>∈VR必有<w,v>∈VR，即VR是对称的，则以无序偶对(v,w)代替这两个有序偶对，此无序偶对(v,w)表示v和w之间的一条边(Edge)，此时的图称为无向图(Undigraph)。若图G中只有顶点而没有边，称为零图。对如下的无向图G1和有向图G2可表示为：6.1图的基本术语6.1.1图的定义1.图(Graph6.1图的基本术语G1=（V1，{A1}）其中：V1={v0,v1,v2,v3}A1={(v0,v1),(v0,v2),(v3,v1),(v3,v2)}G2=（V2，{E2}）其中：V2={v0,v1,v2}E2={<v0,v1>,<v0,v2>,<v1,v2>}6.1.2图的基本术语1.完全图（CompletedGraph）无向完全图:若一个无向图有n个顶点，且每一个顶点与其他n-1个顶点之间都有边，这样的图称为无向完全图。对于一个具有n个顶点的无向完全图，它共有n(n-1)/2条边。有向完全图:

若一个有向图有n个顶点，且每一个顶点与其他

n-1个顶点之间都有一条以该顶点为起点的弧，这样的图称为有向完全图。对于一个具有n个顶点的有向完全图，它共有n(n-1)条弧。6.1图的基本术语G1=（V1，{A1}）6.1.2图的6.1图的基本术语2.子图（Subgraph）设有两个图A和B且满足条件:V(B)是V(A)的子集，E(B)是E(A)的子集或A(B)是A(A)的子集，则称图B是图A的子图。6.1图的基本术语2.子图（Subgraph）6.1图的基本术语3.路径(Path)在无向图G=(V,{E})中，从顶点Vp到Vq的一条路径是顶点序列(Vp,Vi1,Vi2,…，Vin,Vq)且(Vp,Vi1),(Vi1,Vi2),…,(Vin,Vq)是E(G)中的边。对于有向图G=(V,{A})，从顶点Vp到Vq的一条路径是顶点序列(Vp,Vi1,Vi2,…，Vin,Vq)应满足<Vp,Vi1>,<Vi1,Vi2>,…,<Vin,Vq>是A中的弧，其路径也是有向的。路径上边或弧的数目称为路径长度。4.简单路径序列中顶点不重复出现的路径称为简单路径。5.回路（Cycle）和简单回路在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或环。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。6.1图的基本术语3.路径(Path)6.1图的基本术语6.连通图(ConnectedGraph)和强连通图在无向图G中，若从Vi到Vj有路径，则称Vi和Vj是连通的。若G中任意两顶点都是连通的，则称G是连通图。对于有向图而言，若有向图G中每一对不同顶点Vi和Vj之间有从Vi到Vj和从Vj到Vi的路径，则称G为强连通图。6.1图的基本术语6.连通图(ConnectedGr6.1图的基本术语7.连通分量和强连通分量连通分量指的是无向图G中的极大连通子图。强连通分量指的是有向图G中的极大强连通子图。注意:这里是极大而不是最大。8.邻接点（Adjacent）和相关边对于无向图G=(V,E)，若(Vi,Vj)是E(G)中的一条边，则称顶点Vi和Vj互为邻接点，即Vi和Vj相邻接，边(V0,V2)是与顶点V0与V2相关联的边。对于有向图G=(V,A)，若<Vi,Vj>是A(G)中的一条弧，则称顶点Vi邻接到顶点Vj，顶点Vj邻接于顶点Vi，而弧<Vi,Vj>则是与顶点Vi和Vj相关联的弧。6.1图的基本术语7.连通分量和强连通分量8.邻接点（6.1图的基本术语

9.度(Degree)、入度(Indegree)和出度(Outdegree)所谓顶点的度，就是指和该顶点相关联的边或弧的数目。在有向图中，以终止于该顶点的弧的数目称为该顶点的入度;以起始于该顶点的弧的数目称为该顶点的出度;某顶点的入度和出度之和称为该顶点的度。顶点V0的度为3；顶点V1的度为2。顶点V0的入度为1，出度为2，度为3；顶点V1的入度为2，出度为1，度为3；顶点V2的入度为1，出度为1，度为2。6.1图的基本术语9.度(Degree)、入度(Ind6.1图的基本术语10.权和网(Net)在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权。边上带权的图称为带权图，也称为网。6.1图的基本术语10.权和网(Net)6.2图的存储结构6.2.1邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵，可以用一个二维数组来表示。设G=(V,E)

是具有n个顶点的图，顶点序号依次为0，1，2，…，n-1，则G的邻接矩阵是如下定义的n阶方阵:a[i][j]={1对于无向图，(Vi,Vj)∈E(G)；对于有向图，<Vi,Vj>∈E(G)0其他对于带权图(网)的邻接矩阵可以定义为:a[i][j]=Wi对于无向图，(Vi,Vj)∈E(G)；对于有向图，<Vi,Vj>∈E(G)；Wi为权∞其他{图的存储结构有多种，存储结构的选择取决于具体的应用和需要进行的运算。下面给出三种常用的存储结构：邻接矩阵、邻接表和边集数组。6.2图的存储结构6.2.1邻接矩阵邻接矩阵是表示顶点之6.2图的存储结构在图的邻接矩阵中，无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。并且从邻接矩阵很容易判定任意两个顶点之间是否有边存在，并易于求得各个顶点的度。对于无向图，顶点Vi的度是邻接矩阵中第i行（或第i列）的非零元素的个数。对于有向图，顶点Vi的度是邻接矩阵中第i行和第i列的非零元素的个数之和;顶点Vi的出度是邻接矩阵中第i行的非零元素的个数;顶点Vi的入度是邻接矩阵中第i列的非零元素的个数。G1和G2的邻接矩阵分别是矩阵A1、A2有向带权图和无向带权图的邻接矩阵分别是A3、A46.2图的存储结构在图的邻接矩阵中，无向图的邻接矩阵是对称6.2图的存储结构在C语言中，图的邻接矩阵的存储表示如下：#defineMAX_VERTEX_NUM66#defineINFINITY1e6typedefintVRType;//顶点间关系类型typedefintVertexType;//顶点类型enumGraphKind{DG=0,DN=1,UDG=2,UDN=3};//图的种类typedefstructArcCell{//矩阵元素类型

VRTypeadj;//VRType是顶点关系类型。对无权图，用0或1表示相邻与否；对带权图，则为权值类型

InfoType*info;//该弧相关信息指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{

VertexTypevexs[MAX_VERTEX_NUM];//顶点数组

AdjMatrixarcs;//邻接矩阵

intvexnum,arcnum;//图的顶点数和弧数

GraphKindkind;//图的种类}MGraph;6.2图的存储结构在C语言中，图的邻接矩阵的存储表示如下：6.2图的存储结构根据邻接矩阵的定义，可以得出建立图的邻接矩阵的C++算法如下：6.2.2邻接表邻接表(AdjacencyList)是图的一种链式存储结构。在邻接表中，对图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为起点的弧)。每个结点由三个域组成，其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextard)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了设有链域(firstarc)指向链表中的第一个结点外，还设有存储顶点vi的名称或其它有关信息的数据域(data)。这些表头结点通常以顺序结构的形式存储，以便随机地访问任一顶点的链表。图G1和图G2的邻接表如下图所示。一个图的邻接表存储结构可形式地说明如下。6.2图的存储结构根据邻接矩阵的定义，可以得出建立图的邻接6.2图的存储结构typedefintInfoType;typedefintVertexType;typedefstructArcNode{//边或弧结点类型

intadjvex;//与该边或弧所关联的顶点在图中的位置(即在顶点数组中的下标)

structArcNode*nextarc;//指向下一个边或弧结点的指针

InfoType*info;//该边或弧相关信息的指针}ArcNode;typedefstructVNode{//表头结点类型

VertexTypedata;//顶点信息

ArcNode*firstarc;//指向依附于该顶点的第一条边或弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{//以邻接表表示的图的存储结构

AdjListvertices;//表头数组

intvexnum,arcnum;//顶点数和边或弧的条数

GraphKindkind;//图的种类}ALGraph;6.2图的存储结构typedefintInfoType6.2图的存储结构若无向图中有n个顶点、e条边，则它的邻接表需要n个头结点和2e个边结点。显然，在边稀疏的情况下，用邻接表比用邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。在无向图的邻接表中，顶点vi的度恰为第i个链表中结点的个数；而在有向图中，第i个链表中的结点数只是顶点vi的出度，为求入度必须遍历整个邻接表。在整个邻接表中其邻接点域的值为i的结点个数是顶点vi的入度。有时，为了便于确定顶点的入度或以顶点vi为终点的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi建立一个链接以vi为终点的弧的表。6.2图的存储结构若无向图中有n个顶点、e条边，则它的邻接6.2图的存储结构建立图的邻接表的C++程序见Graph2.cpp6.2图的存储结构建立图的邻接表的C++程序见Graph26.2图的存储结构6.2.3边集数组带权图(网)的另一种存储结构是边集数组，它适用于一些以边为主的操作。用边集数组表示带权图时，列出每条边所依附的两个顶点及边上的权，即每个数组元素代表一条边的信息。例如，下图的边集数组是：016133346422205501515536544525在这个边集数组中第一列是边的起点，第二列是边的终点，第三列是边的权值。每一行表示一条边。6.2图的存储结构6.2.3边集数组016在这个边集6.2图的存储结构6.2.4十字链表十字链表是有向图的另一种链式存储结构。