邻接矩阵怎么求

邻接矩阵是图论中表示图的一种方法，它用一个矩阵来表示图中各个节点之间的连接关系。对于一个有$n$个节点的无向图，其领接矩阵是一个$n \times n$的矩阵$A$，其中：

①如果节点$i$和节点$j$之间有边相连，则$A_{i,j}=1$；

②如果节点$i$和节点$j$之间没有边相连，则$A_{i,j}=0$。

对搏销于一个有向图，其领接矩阵也是一个$n \times n$的矩阵$A$，其中：

①如果从节点$i$到节点$j$有一条有向边，则$A_{i,j}=1$；

②如果从节点$i$到节点$j$没有一条有向边，则$A_{i,j}=0$。

下面以无向图为例，介绍如何求领接矩阵：

1、假设我们有一个无向图$G$，它有$n$个节点和$m$条边，我们可以使用一个邻接表来表示这个图。邻接表是一个数组，每个元素表示一个节点，数组中每个元素的值是一个链表，链表中存储了与该节点相邻的其他节点的编号。

2、我们可以使用邻接表来求出领接矩阵。具体来说，我们可以创建一个$n \times n$的矩阵$A$，然后遍历邻接表，对于祥困每个节点$i$和其相邻的节点$j$，将$A_{i,j}$和$A_{j,i}$都设置为1，表示这两个节点之间有边相连。最后，我们就可以得到这个无向图的领接矩阵。

下面是求领接矩阵的具体步骤：

①创建一个$n \times n$的矩阵$A$，并将所有元素谨银念初始化为0。

②遍历邻接表，对于每个节点$i$和其相邻的节点$j$，将$A_{i,j}$和$A_{j,i}$都设置为1。

③返回矩阵$A$，即为这个无向图的领接矩阵。

#include<iostream>

using namespace std

#define MAX 32767

#define MAX_VERTEX_NUM 20

#define OK 1

#define ERROR 0

typedef char VertexType

typedef struct ArcNode

{

int adjvex//该弧所指向顶点的位置

struct ArcNode *nextarc

int info//指向下一运银橘条弧的指针

}ArcNode

typedef struct VNode

{

char data//顶点信息

ArcNode *firstarc//指向第一条依附该顶点的搏梁弧的指针

}VNode,AdjList[MAX_VERTEX_NUM]

typedef struct

{

AdjList vertices

AdjList adjlist

int vexnum,arcnum

int n,e//图当前的顶点数和弧数

}ALGraph

//typedef struct

//{

//int no

//int info

//}VertexType

typedef struct

{

int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]

int vexnum,arcnum

VertexType Vexs[MAX_VERTEX_NUM]

int n,e

}MGraph

int LocateVex(ALGraph G,char v)

{int i

for(i=0i<G.vexnumi++)

{

if(G.vertices[i].data==v)

return i

}

return -1

}

int CreateGraph(ALGraph *G)

{

char v1,v2

int i,j,k

ArcNode *p

cout<<"请输入待创建有向图的顶点数，弧数："

cin>>G->vexnum>>G->arcnum

cout<<endl

for(i=0i<G->vexnumi++)

{

cout<<"请输入第"<<i+1<<"个结点的值："

cin>>G->vertices[i].data

}

cout<<endl

for(i=0i<G->vexnumi++)

G->vertices[i].firstarc=NULL

for(k=0k<G->arcnumk++)

{ cout<<"建立弧，请输入"<<k+1<<"条弧对应的两个顶点:"

cin>>v1>>v2

i=LocateVex(*G,v1)

j=LocateVex(*G,v2)

p=G->vertices[i].firstarc

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

p->adjvex=j

p->nextarc=G->vertices[i].firstarc

G->vertices[i].firstarc=p

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

p->adjvex=j

p->adjvex=i

p->nextarc=G->vertices[j].firstarc

G->vertices[j].firstarc=p

}

return OK

}

void PrintGraph(ALGraph *G)

{

int i

ArcNode *p

cout<<endl<<"图的邻接表为:"<<endl

for (i=0i<G->vexnumi++)

{

cout<<i<<" "<<G->vertices[i].data<<" -> "

p=G->vertices[i].firstarc

while (p!=NULL)

{

cout<<"["<<G->vertices[i].data<<","<<p->adjvex<<"]"<<" ->"

p=p->nextarc

}

cout<<"旁团^"<<endl

}

}

void ListToMat(ALGraph *G,MGraph *g){/*邻接表转换为邻接矩阵*/

int i,j,n=G->vexnum

ArcNode *p

for(i=0i<ni++)

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

g->edges[i][j]=0

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

p=G->vertices[i].firstarc

while(p!=NULL){

g->edges[i][p->adjvex]=1

p=p->nextarc

}

}

g->vexnum=n

g->arcnum=G->e

}

void DispMat(MGraph g)/*显示邻接矩阵*/

{

int i,j

for(i=0i<g.vexnumi++){

for(j=0j<g.vexnumj++)

if(g.edges[i][j]==MAX)

printf("%3s","∞")

else

printf("%3d",g.edges[i][j])

printf("\n")

}

}

int main()

{

MGraph g

ALGraph *G

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

CreateGraph(G)

PrintGraph(G)

printf("图G的邻接表转换为邻接矩阵:\n")

ListToMat(G,&g)

DispMat(g)

return 0

}

---