图的邻接矩阵和邻接表相互转换

图的邻接矩阵和邻接表相互转换

图的邻接矩阵存储方法具有如下几个特征：

< br>1)

无向图的邻接矩阵一定是一个对称矩阵。

2

）对于无向图的邻接矩阵的第

i

行非零元素的个 数正好是第

i

个顶点的度

TD

?

v

i

?

。

3

）对于

有向图，邻接矩 阵的第

i

行非零元素的个数正好是第

i

个顶点的出度

OD

?

< br>v

i

?

（或入度

。

4

）用邻接矩阵方法存储图，很容易确定图中任意两 个顶点之间是否有边相连；

ID

?

v< /p>

i

?

）

但是，< /p>

要确定图中有多少条边，

则必须按行、

按 列对每个元素进行检测，所发费得时间代价

大。

邻接表是图的一种顺序存储与链式存储相结合的存储方法。若无向图中有

n< /p>

个顶点、

e

条边，则它的邻接表需

n

个头结点和

2e

个 表结点。显然，在边稀疏的情况下，用邻接表表

示图比邻接矩阵存储空间。

在无向图的邻接表中，

顶点

v

i

的度恰好是第

i

个链表中的结点数 ，

而在有向图中，第

i

个链表中结点个 数是顶点

v

i

的出度。

在建立邻接表或邻逆接表时，若输入的顶点信息即为顶点的编号，则建立临接 表的时

间复杂度是

O

(

n

?

e

)

；否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为

O

(

n

*

e

)

。

在邻接表上容易找到任意一顶点的第一个邻接点和下一 个邻接点，

但要判断任意

两个顶点之间是否有边或弧，则需要搜 索第

i

个或第

j

个链表，因此，不及邻接矩阵方便。

邻接矩阵和邻接表相互转换程序代码如下：

#include

#define MAX 20

//

图的邻接表存储表示

typedef struct ArcNode{

int adjvex;

//

弧的邻接定点

char info;

//

邻接点值

struct ArcNode *nextarc;

//

指向下一条弧的指针

}ArcNode;

typedef struct Vnode{

//

节点信息

char data;

ArcNode *link;

}Vnode,AdjList[MAX];

typedef struct{

AdjList vertices;

int vexnum;

//

节点数

int arcnum;

//

边数

}ALGraph;

//

图的邻接矩阵存储表示

typedef struct{

int n;

//

顶点个数

char vexs[MAX];

//

定点信息

int arcs[MAX][MAX];

//

边信息矩阵

}AdjMatrix;

/*** __________________________________________________ ___***/

//

函数名：

Adj ListToMatrix(AdjList g1,AdjListMatrix &gm,int n) < /p>

//

参数：

（传入）

AdjList g1

图的邻接表

,

（传入）

int n

顶点个数，

（传 出）

AdjMatrix gm

图的

邻接矩阵

< br>//

功能：把图的邻接表表示转换成图的邻接矩阵表示

void AdjListToAdjMatrix(ALGraph gl,AdjMatrix &gm){

int i,j,k;

ArcNode *p;

gm.n=;

for(k=0;k<;k++)

[k]=es[k].data;

for(i=0;i

for(j=0;j

[i][j]=0;

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

p=es[i].link;

//

取第一个邻接顶点

while(p!=NULL){

//

取下一个邻接顶点

[i][p->adjvex]=1;

p=p->nextarc;

}

}

}

/* **________________________________________________ ***/

//

函数名：

AdjMat rixToAdjList

void AdjMatrixToAdjList(AdjMatrix gm,ALGraph &gl){

int i,j,k,choice;

ArcNode *p;

k=0;

=gm.n;

cout<<

请选择所建立的图形是 无向图或是有向图：

cin>>choice;

for(i=0;i