图的邻接矩阵存储

Ⅰ 图的存储结构——所存储的信息有哪些

一、邻接矩阵存储方法

邻接矩阵是表示顶点之间相邻关系的矩阵。

设G=(V，E)是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则G的邻接矩阵A是n阶方阵，其定义如下：

（1）如果G是无向图，则：

A[i][j]=1：若(i,j)∈E(G) 0:其他

（2）如果G是有向图，则：

A[i][j]=1：若<i,j>∈E(G) 0:其他

（3）如果G是带权无向图，则：

A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他

（4）如果G是带权有向图，则：

A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他

注意：带权图和不带权图表示的元素类型不同。

带权图（不论有向还是无向图）A[i][j]用double表示，不带权图（不论有向还是无向图）A[i][j]用int表示。

用一维数组G[ ]存储有4个顶点的无向图如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }

则顶点2和顶点0之间是有边的。

如：

邻接矩阵的特点如下：

（1）图的邻接矩阵表示是唯一的。

（2）无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。

（3）不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵。因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。

（4）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。

（5）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。

（6）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

邻接矩阵的数据类型定义如下：

#define MAXV <最大顶点个数>

typedef struct

{ int no; //顶点编号

InfoType info; //顶点其他信息

} VertexType; //顶点类型

typedef struct //图的定义

{ int edges[MAXV][MAXV]; //邻接矩阵

int n，e; //顶点数，弧数

VertexType vexs[MAXV]; //存放顶点信息

} MGraph; //图的邻接矩阵表示类型

二、 邻接表存储方法

图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。

在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。

其中，表节点由三个域组成，adjvex指示与顶点i邻接的点在图中的位置，nextarc指示下一条边或弧的节点，info存储与边或弧相关的信息，如权值等。

表头节点由两个域组成，data存储顶点i的名称或其他信息，firstarc指向链表中第一个节点。

typedef struct ANode

{ int adjvex; //该边的终点编号

struct ANode *nextarc; //指向下一条边的指针

InfoType info; //该边的相关信息

} ArcNode; //边表节点类型

typedef struct Vnode

{ Vertex data; //顶点信息

ArcNode *firstarc; //指向第一条边

} VNode; //邻接表头节点类型

typedef VNode AdjList[MAXV]; //AdjList是邻接表类型

typedef struct

{ AdjList adjlist; //邻接表

int n,e; //图中顶点数n和边数e

} ALGraph; //完整的图邻接表类型

邻接表的特点如下：

（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。

（2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。

（3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。

（4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。

例， 给定一个具有n个节点的无向图的邻接矩阵和邻接表。

（1）设计一个将邻接矩阵转换为邻接表的算法；

（2）设计一个将邻接表转换为邻接矩阵的算法；

（3）分析上述两个算法的时间复杂度。

解：

（1）在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表节点并在邻接表对应的单链表中采用前插法插入该节点。

void MatToList(MGraph g，ALGraph *&G)

//将邻接矩阵g转换成邻接表G

{ int i，j，n=g.n; ArcNode *p; //n为顶点数

G=(ALGraph *)malloc(sizeof(ALGraph));

for (i=0;i<n;i++) //给所有头节点的指针域置初值

G->adjlist[i].firstarc=NULL;

for (i=0;i<n;i++) //检查邻接矩阵中每个元素

for (j=n-1;j>=0;j--)

if (g.edges[i][j]!=0)

{ p=(ArcNode *)malloc(sizeof(ArcNode));

//创建节点*p

p->adjvex=j;

p->nextarc=G->adjlist[i].firstarc;

//将*p链到链表头

G->adjlist[i].firstarc=p;

}

G->n=n;G->e=g.e;

}

（2）在邻接表上查找相邻节点，找到后修改相应邻接矩阵元素的值。

void ListToMat(ALGraph *G，MGraph &g)

{ int i，j，n=G->n;ArcNode *p;

for (i=0;i<n;i++)

{ p=G->adjlist[i].firstarc;

while (p!=NULL)

{ g.edges[i][p->adjvex]=1;

p=p->nextarc;

}

}

g.n=n;g.e=G->e;

}

（3）算法1的时间复杂度均为O(n2)。算法2的时间复杂度为O(n+e)，其中e为图的边数。

Ⅱ 有向图的邻接表存储如图所示，请画出其邻接矩阵存储结构

有向图的邻接表存储如图所示，其邻接矩阵存储如图：

Ⅲ 若具有n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵一定为一个什么矩阵

原则上的确是n的平方，不过由于无向图的邻接矩阵是一个对称矩阵，只需要存储下三角或者上三角的元素，个数就是从1加到n，就是n（n+1）/ 2，这是压缩存储，是用一维数组存放，一般好像不叫矩阵。

其实更精确地说，上面的数字个数是普通对称矩阵的，这个邻接矩阵的对角线一定为0，所以，只需要存储1加到n-1，也就是n(n-1)/2就可以了。

用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

(3)图的邻接矩阵存储扩展阅读：

对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。

在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。

用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

Ⅳ 图的图的存储表示

数组（邻接矩阵）存储表示（有向或无向）
邻接表存储表示
有向图的十字链表存储表示
无向图的邻接多重表存储表示
一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（info）。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。
在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。
在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作<vi,vj>，它表示从顶点vi到顶点vj有一条边。
若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和<vj,vi>两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条弧，我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。
路径长度是指路径上边或弧的数目。
若第一个顶点和最后一个顶点相同，则这条路径是一条回路。
若路径中顶点没有重复出现，则称这条路径为简单路径。
在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。
在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。