数据结构图的存储本

第七章图的存储本讲内容1.图的邻接矩阵2.图的邻接表3.图的十字链表4.图的邻接多重表由于图的结构比较复杂，任意两个顶点之间都有可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系。图没有顺序存储结构，但可以借助于二维数组来表示元素之间的关系，即邻接矩阵表示法。另一方面，由于图的任意两个顶点间都可能存在关系，因此，用链式存储表示图是很自然的事，图的链式存储有多种，如邻接表、逆邻接表、十字链表和邻接多重表，应该根据实际需要的不同选择不同的存储结构。图的邻接矩阵矩阵的元素为A[i][j]={0<i,j>或(i,j)VR1<i,j>或(i,j)VR定义图的邻接矩阵是表示顶点之间相邻关系的矩阵。设G(V,VR)是具有n个顶点的图，用邻接矩阵表示法表示图，除了用二维数组存储图中各顶点间的关系VR外，还需要用一维数组存储图中的顶点V。图的邻接矩阵举例BACDFE010010100011000101001001110000011100无向图的邻接矩阵一定是对称矩阵，在具体存放时只需存放上（下）三角阵的元素。第i行（列）非0元素的个数是第i个顶点的度。有向图的邻接矩阵为非对称矩阵ABECD第i行（列）非0元素的个数是第i个顶点的出度（入度）。邻接矩阵的C描述constintMAX_VERTEX=最大顶点个数;typedefcharVertexType;typedefint

ArcType;typedefstructGraph{//图的定义

VertexTypevexs[MAX_VERTEX];//顶点ArcTypearcs[MAX_VERTEX][MAX_VERTEX];//弧(邻接矩阵)intvexnum,arcnum;//顶点数，弧数

}Graph;图的邻接矩阵通过前面给出的图的邻接矩阵的C描述知：对于图来说，有边（弧）时邻接矩阵arcs中的元素为1，否则为0。对于网来说，有边（弧）时邻接矩阵arcs中的元素为其上的权值，否则为∞。其中，∞表示计算机允许的、大于所有边上权值的数。邻接矩阵的存储空间个数为n2，与边数无关。采用邻接矩阵创建无向网已知一个图的点和边，使用邻接矩阵表示法来创建此图的方法比较简单。下面以一个无向网为例来说明创建图的算法。步骤1：输入总顶点数和总边数。步骤2：依次输入点的信息存入顶点表中。步骤3：初始化邻接矩阵，使每个权值初始化为极大值∞

。步骤4：构造邻接矩阵。依次输入每条边依附的顶点和其权值，确定两个顶点在图中的位置后，使相应边赋予相应的权值，同时使其对称边赋予相同的权值。voidCreateUDN(Graph&G){ scanf(G.vexnum);scanf(G.arcnum);

for(i=0;i<G.vexnum;i++)//输入顶点的信息

scanf(G.vexs[i]);

for(i=0;i<G.vexnum;i++)//初始化邻接矩阵，边上的权值为极大值MaxInt

for(j=0;j<G.vexnum;j++) G.arcs[i][j]=MaxInt; //∞

for(k=0;k<G.arcnum;k++){//构造邻接矩阵

scanf(v1);scanf(v2);scanf(w); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j]=w; G.arcs[j][i]=G.arcs[i][j]; }}算法分析算法时间复杂度为O(n2)。若要建立无向图，只需对上述算法做两处小小的改动：一是初始化邻接矩阵时，将边的权值均初始化为0；二是构造邻接矩阵时，将权值w改为常量1即可。同样，将该算法稍作修改即可建立一个有向网或有向图。邻接矩阵表示法的优缺点优点1.便于判断两个顶点之间是否有边，即根据A[i][j]来判断。2.便于计算各个顶点的度。缺点1.不便于增加和删除顶点。2.不便于统计边的数目，时间复杂度为O(n2)。3.空间复杂度高。如果是有向图，n个顶点需要n2个单元存储边。如果是有向图，邻接矩阵是对称的，所以规模较大的邻接矩阵可以采用压缩存储的方法，仅存储下三角（或上三角）的元素，需要n(n-1)/2个单元即可。无论以何种方式存储，邻接矩阵的空间复杂度为O(n2)，对于稀疏矩阵来说尤其浪费空间。故，适合稠密图。图的邻接表定义图的链式存储结构。在邻接表中，对图中每个顶点vi建立一个单链表，把与vi相邻接的顶点放在这个链表中。邻接表中每个单链表的第一个结点存放有关顶点的信息，把这一结点看成链表的表头，其余结点存放有关边的信息。对于图中每条弧均依附于两个结点，因此链表中的结点就是具有相同弧尾的弧结点。在实际存储时，图中顶点的邻接点链成链表，表结点中存储邻接点的存储位置。而在存储图中顶点时，除了本身的数据信息外，还要存储指示其第一个邻接点的指针。0A141B0452C353D254E015F123BACDFE无向图中n个顶点，e条边，则邻接表有n个头结点和2e个表结点。举例142301201234

ABCDE有向图的邻接表ABECD可见，在有向图的邻接表中不易找到指向该顶点的弧。ABECD有向图的逆邻接表ABCDE30342001234在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧。邻接表的C描述adjvexnextarc弧的结点结构typedefstruct

ArcNode

{

int adjvex;//邻接点的位置

structArcNode

*nextarc;//下一个邻接点OtherInfoinfo;//和边相关的信息，如权值}

ArcNode;infodatafirstarc顶点的结点结构typedefstruct

VexNode

{ VertexType data;//顶点信息

ArcNode

*firstarc;//指向第一个邻接点}

VexNode;图的结构定义constint MAX_VERTEX=最大顶点个数typedefstructGraph{

VexNode

vexs[MAX_VERTEX];//顶点向量

int vexnum,arcnum;//顶点和弧的个数}

Graph;采用邻接表创建无向图基于上述的邻接表表示法，要创建一个图则需要创建其相应的顶点表和边表。下面以一个无向图为例来说明采用邻接表表示法创建无向图的算法。步骤1：输入总顶点数和总边数。步骤2：依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL。步骤3：创建邻接表。依次输入每条边依附的两个顶点，确定这两个顶点的序号i和j后，将此边结点分别插入vi和vj对应的两个边链表的头部。voidCreateUDG(Graph&G){ scanf(G.vexnum);scanf(G.arcnum);

for(i=0;i<G.vexnum;i++){//输入各点,构造表头结点表

scanf(G.vexs[i].data); G.vexs[i].firstarc=NULL; }

for(k=0;k<G.arcnum;k++){//输入各边，构造邻接表

scanf(v1);scanf(v2);

i=LocateVex(G,v1); j=LocateVex(G,v2);

//插入到顶点vi的边表头部 p1=(ArcNode*)malloc(sizeof(ArcNode)); p1->adjvex=j; p1->nextarc=G.vexs[i].firstarc; G.vexs[i].firstarc=p1; //插入到顶点vj的边表头部

p2=(ArcNode*)malloc(sizeof(ArcNode)); p2->adjvex=i; p2->nextarc=G.vexs[j].firstarc; G.vexs[j].firstarc=p2; }}算法分析算法时间复杂度为O(n+e)。建立有向图的邻接表与此类似，只是更加简单，每读入一个顶点对序号<i,j>，仅需生成一个邻接点序号为j的边表结点，并将其插入到vi的边链表头部即可。若要创建网的邻接表，可以将边的权值存储到info域中。值得注意的是，一个图的邻接矩阵表示是唯一的，但是其邻接表表示不唯一，这是因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法，以及边的输入次序。邻接表表示法的优缺点优点1.便于增加和删除顶点。2.便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为O(n+e)。缺点1.不便于判断顶点之间是否有边，要判定vi和vj之间是否有边，就需要扫描第i个边表，最坏情况下要耗费O(n)时间。2.不便于计算有向图各个顶点的度。3.空间效率高，空间复杂度为O(n+e)。适合表示稀疏图。弧的结点结构弧尾顶点位置弧头顶点位置指向下一个有相同弧尾的弧结点指向下一个有相同弧头的弧结点有向图的十字链表typedefstruct

ArcNode

{//弧结点

inttailvex,headvex;//弧尾和弧头顶点的位置

structArcNode*nexttail,

*nexthead;//指向下一个同弧尾和同弧头的弧结点}

ArcNode;顶点的结点结构顶点信息指向该顶点的第一条入弧指向该顶点的第一条出弧typedefstruct

VexNode

{//顶点结点VertexType data;

//顶点信息

ArcNode *firstin,

*firstout;//指向第一条入弧和第一条出弧}

VexNode;有向图的结构定义（十字链表）constint MAX_VERTEX=最大顶点个数typedefstructGraph{

VexNodevexs[MAX_VERTEX]; //顶点向量

intvexnum,arcnum;//有向图的顶点和弧的个数}

Graph;有向图的十字链表相当于邻接表和逆邻接表的结合。ABCDEABCDE/\01234/\30/\40/\01/\02/\12/\13/\23/\/\43画图技巧：把弧结点按行排整齐，然后画链表。同弧尾的弧组成链表，同弧头的弧组成链表。无向图的邻接多重表边的结点结构边顶点1位置边顶点2位置指向下一个依附顶点1的边结点指向下一个依附顶点2的边结点typedef

struct

EdgeNode{

//边结点

VisitIfmark;//访问标记

int vexi,vexj; //边的两个顶点

structEdgeNode*nexti,*nextj;//两个顶点所依附的下一条边}EdgeNode;顶点的结点结构顶点信息指向依附该顶点的第一条边typedef

struct

VexNode{//顶点结点 VertexType data; //顶点信息

EdgeNode

*firstedge;//指向依附该顶点的第一条边}VexNode;无向图的结构