算法 数据结构 无向图G的邻接矩阵法和邻接表法以及遍历输出无向图G包括两种存储的FirstNeighbor和NextNeighbor两种基本操作

一.邻接矩阵法

将下列图G用邻接矩阵法进行存储

圆圈中的字符：是顶点的值

圆圈旁边的数字：是顶点的序号

边线上的值：是两个顶点之间的权值 

1.结构体

#define MaxVertexNum 10

typedef char VerTexType;//顶点的数据类型

typedef int EdgeType;//带权图中边上权值数据类型

typedef struct

{

VerTexType Vex[MaxVertexNum];//顶点表

EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表

int vexnum,arcnum;//图的当前顶点数和弧数

}MGraph;

 2.用邻接矩阵创造无向图G

//无向网的建立

void CreatMGraph(MGraph &G)

{

printf("请输入图的顶点数和边数：");

int m,n;

scanf_s("%d %d",&m,&n);

G.vexnum = m;

G.arcnum = n;

char val;

for(int i = 0; i < G.vexnum; ++i)

{

printf("第%d个顶点值为:",i);

scanf_s("%*c%c",&val);

G.Vex[i] = val;

}

for(int i = 0; i < G.vexnum; ++i)

{

for(int j = 0; j < G.vexnum; ++j)

{

G.Edge[i][j] = Max;

}

}

int i,j,w;

for(int k = 0; k < G.arcnum; ++k)

{

printf("请输入顶点和权值\n");

scanf_s("%d %d %d",&i,&j,&w);

printf("(Vi,Vj)下表为(%d,%d)的权值为%d:\n",i,j,w);

G.Edge[i][j] = w;

G.Edge[j][i] = G.Edge[i][j];

}

}

3.无向图G的遍历输出

//打印邻接矩阵存储的图

void PrintMGraph(MGraph G)

{

for(int i = 0; i < G.vexnum; ++i)

{

printf("第%d个顶点的值为%c\n",i,G.Vex[i]);

}

for(int i = 0; i < G.vexnum; ++i)

{

for(int j = 0; j < G.vexnum; ++j)

{

printf("%d ",G.Edge[i][j]);

}

printf("\n");

}

}

4.FirstNeighbor的操作：求图G中顶点编号x的第一个邻接点

//求图G中顶点编号x的第一个邻接点

int FirstNeighbor(MGraph G, int x)

{

for(int j = 0; j < G.vexnum; ++j)

{

if(G.Edge[x][j] != -1)

return j;

}

return -1;

}

5.NextNeighbor操作：假设图G中顶点y是顶点x的一个邻近点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

//假设图G中顶点y是顶点x的一个邻近点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

int NextNeighbor(MGraph G, int x, int y)

{

for(int j = y+1; j < G.vexnum; ++j)

{

if(G.Edge[x][j] != -1)

return j;

}

return -1;

}

6.main函数：

int main(void)

{

MGraph G;

CreatMGraph(G);

printf("%c",G.Vex[1]);

PrintMGraph(G);

printf("请输入你想查找顶点的编号：");

int pos;

scanf_s("%d",&pos);

int FN = FirstNeighbor(G,pos);

if(FN != -1)

printf("编号为%d顶点值为%c第一个临接的顶点的值为：%c\n",pos,G.Vex[pos],G.Vex[FN]);

else

printf("编号为%d顶点值为%c的没有第一个邻接点",pos,G.Vex[pos]);

int NN = NextNeighbor(G,pos,FN);

if(NN == -1)

printf("编号为%d顶点值为%c且第一个邻接顶点值为%c没有下一个邻接点",pos,G.Vex[2],G.Vex[FN]);

else

printf("编号为%d顶点值为%c且第一个邻接顶点值为%c的下一个邻接点值为%c",pos,G.Vex[2],G.Vex[FN],G.Vex[NN]);

return 0;

}

 6.运行结果

 二.邻接表法

将下面无向图G用邻接表法进行存储

圆圈中的字符：是顶点的值

圆圈旁边的数字：是顶点的序号

边线上的值：是两个顶点之间的权值 

 1.结构体

#define MaxVertexNum 10//图中顶点数目的最大值

typedef char VertexType;

//定义边表结点

typedef struct ArcNode

{

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

struct ArcNode *next;//指向下一条弧的指针

int info;//网的边权值

}ArcNode;

//顶点表信息，用顺序结构存储顶点表的信息

typedef struct VNode

{

VertexType data;//顶点信息

ArcNode *first;//指向第一条依附该顶点的弧的指针

}VNode,AdjList[MaxVertexNum];

//邻接表

typedef struct

{

AdjList vertices;//邻接表

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

}ALGraph;//ALGraph是以邻接表存储图的类型

2.用邻接表法创建无向图G

//创建邻接表

void CreatALGraph(ALGraph &G)

{

printf("请输入图G的顶点数和边数：\n");

scanf_s("%d %d",&(G.vexnum),&(G.arcnum));

//输入结点

char val;

for(int i = 0; i < G.vexnum; ++i)

{

printf("请输入第%d个结点的值：\n",i);

scanf_s("%*c%c",&val);

G.vertices[i].data = val;

G.vertices[i].first = NULL;//最开始令每个顶点的第一条依附顶点的弧的指针为空

}

//输入边

int i,j,w;

for(int k = 0; k < G.arcnum; ++k)

{

ArcNode *m = (ArcNode*)malloc(sizeof(ArcNode));

printf("请输入顶点的序号和权值\n");

scanf_s("%d %d %d",&i,&j,&w);

printf("(Vi,Vj)下表为(%d,%d)的权值为%d:\n",i,j,w);

m->adjvex = j;

m->info = w;

//用头插法创造边表

m->next = G.vertices[i].first;

G.vertices[i].first = m;

//这个是无向图，而且令k

ArcNode *n = (ArcNode*)malloc(sizeof(ArcNode));

n->adjvex = i;

n->info = w;

//用头插法创建边表

n->next = G.vertices[j].first;

G.vertices[j].first = n;

}

}

2.遍历输出无向图G

//打印邻接表存储的图

void PrintALGraph(ALGraph G)

{

for(int i = 0; i < G.vexnum; ++i)

{

ArcNode *p = G.vertices[i].first;

printf("顶点编号为%d的值为：%c\n",i,G.vertices[i].data);

printf("顶点后面挂着的边表的值分别为：\n");

while(p != NULL)

{

printf("序号为：%d; 顶点值为：%c; (%c,%c)之间权值为：%d\n",p->adjvex,G.vertices[p->adjvex].data,G.vertices[i].data,G.vertices[p->adjvex].data,p->info);

p = p->next;

}

}

}

3.FirstNeighbor操作：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1.

//求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1.

int FirstNeighbor(ALGraph G, int x)

{

if(x >= G.vexnum)

{

printf("图G不存在x\n");

return -1;

}

else if(G.vertices[x].first == NULL)

{

printf("图G中顶点x没有邻接点\n");

return -1;

}

else

{

ArcNode *p = G.vertices[x].first;//指向图G的顶点x的邻接点的指针

int i = p->adjvex;//邻接点的序号

int j = p->info;//两个顶点之间的权值

printf("图G中顶点序号为%d的值为%c的邻接点的序号为%d值为%c且权值为%d\n",x,G.vertices[x].data,i,G.vertices[i].data,j);

return i;

}

}

4.NextNeighbor操作：假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

//假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

int NextNeighbor(ALGraph G,int x,int y)

{

ArcNode *p = G.vertices[x].first;

while(p->adjvex != y)

{

p = p->next;

}

if(p->next == NULL)

{

printf("%c是图G中顶点%c的最后一个邻接点\n",G.vertices[x].data,G.vertices[y].data);

return -1;

}

else

{

p = p->next;

int j = p->adjvex;

printf("%c是图G中除%c之外顶点%c的下一个邻接点\n",G.vertices[j].data,G.vertices[y].data,G.vertices[x].data);

return j;

}

}

5.main函数

int main(void)

{

ALGraph G;

CreatALGraph(G);

PrintALGraph(G);

printf("请输入你想查找结点的序号：\n");

int m;

scanf_s("%d",&m);

FirstNeighbor(G,m);

printf("请输入你想查找结点和某一个邻接结点的序号：\n");

int a,b;

scanf_s("%d %d",&a,&b);

NextNeighbor(G,a,b);

return 0;

}

6.运行结果图：

 完整代码：

邻接矩阵法：

#include

#define Max -1//这里以-1代表最大值

#define MaxVertexNum 10

typedef char VerTexType;//顶点的数据类型

typedef int EdgeType;//带权图中边上权值数据类型

typedef struct

{

VerTexType Vex[MaxVertexNum];//顶点表

EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表

int vexnum,arcnum;//图的当前顶点数和弧数

}MGraph;

//函数说明

void CreatMGraph(MGraph &G);

void PrintMGraph(MGraph G);

int FirstNeighbor(MGraph G, int x);

int NextNeighbor(MGraph G, int x, int y);

int main(void)

{

MGraph G;

CreatMGraph(G);

printf("%c",G.Vex[1]);

PrintMGraph(G);

printf("请输入你想查找顶点的编号：");

int pos;

scanf_s("%d",&pos);

int FN = FirstNeighbor(G,pos);

if(FN != -1)

printf("编号为%d顶点值为%c第一个临接的顶点的值为：%c\n",pos,G.Vex[pos],G.Vex[FN]);

else

printf("编号为%d顶点值为%c的没有第一个邻接点",pos,G.Vex[pos]);

int NN = NextNeighbor(G,pos,FN);

if(NN == -1)

printf("编号为%d顶点值为%c且第一个邻接顶点值为%c没有下一个邻接点",pos,G.Vex[2],G.Vex[FN]);

else

printf("编号为%d顶点值为%c且第一个邻接顶点值为%c的下一个邻接点值为%c",pos,G.Vex[2],G.Vex[FN],G.Vex[NN]);

return 0;

}

//无向网的建立

void CreatMGraph(MGraph &G)

{

printf("请输入图的顶点数和边数：");

int m,n;

scanf_s("%d %d",&m,&n);

G.vexnum = m;

G.arcnum = n;

char val;

for(int i = 0; i < G.vexnum; ++i)

{

printf("第%d个顶点值为:",i);

scanf_s("%*c%c",&val);

G.Vex[i] = val;

}

for(int i = 0; i < G.vexnum; ++i)

{

for(int j = 0; j < G.vexnum; ++j)

{

G.Edge[i][j] = Max;

}

}

int i,j,w;

for(int k = 0; k < G.arcnum; ++k)

{

printf("请输入顶点和权值\n");

scanf_s("%d %d %d",&i,&j,&w);

printf("(Vi,Vj)下表为(%d,%d)的权值为%d:\n",i,j,w);

G.Edge[i][j] = w;

G.Edge[j][i] = G.Edge[i][j];

}

}

//打印邻接矩阵存储的图

void PrintMGraph(MGraph G)

{

for(int i = 0; i < G.vexnum; ++i)

{

printf("第%d个顶点的值为%c\n",i,G.Vex[i]);

}

for(int i = 0; i < G.vexnum; ++i)

{

for(int j = 0; j < G.vexnum; ++j)

{

printf("%d ",G.Edge[i][j]);

}

printf("\n");

}

}

//求图G中顶点编号x的第一个邻接点

int FirstNeighbor(MGraph G, int x)

{

for(int j = 0; j < G.vexnum; ++j)

{

if(G.Edge[x][j] != -1)

return j;

}

return -1;

}

//假设图G中顶点y是顶点x的一个邻近点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

int NextNeighbor(MGraph G, int x, int y)

{

for(int j = y+1; j < G.vexnum; ++j)

{

if(G.Edge[x][j] != -1)

return j;

}

return -1;

}

邻接表法：

#include

#include

#include

#define MaxVertexNum 10//图中顶点数目的最大值

typedef char VertexType;

//定义边表结点

typedef struct ArcNode

{

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

struct ArcNode *next;//指向下一条弧的指针

int info;//网的边权值

}ArcNode;

//顶点表信息，用顺序结构存储顶点表的信息

typedef struct VNode

{

VertexType data;//顶点信息

ArcNode *first;//指向第一条依附该顶点的弧的指针

}VNode,AdjList[MaxVertexNum];

//邻接表

typedef struct

{

AdjList vertices;//邻接表

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

}ALGraph;//ALGraph是以邻接表存储图的类型

//函数说明

void CreatALGraph(ALGraph &G);

void PrintALGraph(ALGraph G);

int FirstNeighbor(ALGraph G, int x);

int NextNeighbor(ALGraph G,int x,int y);

int main(void)

{

ALGraph G;

CreatALGraph(G);

PrintALGraph(G);

printf("请输入你想查找结点的序号：\n");

int m;

scanf_s("%d",&m);

FirstNeighbor(G,m);

printf("请输入你想查找结点和某一个邻接结点的序号：\n");

int a,b;

scanf_s("%d %d",&a,&b);

NextNeighbor(G,a,b);

return 0;

}

//创建邻接表

void CreatALGraph(ALGraph &G)

{

printf("请输入图G的顶点数和边数：\n");

scanf_s("%d %d",&(G.vexnum),&(G.arcnum));

//输入结点

char val;

for(int i = 0; i < G.vexnum; ++i)

{

printf("请输入第%d个结点的值：\n",i);

scanf_s("%*c%c",&val);

G.vertices[i].data = val;

G.vertices[i].first = NULL;//最开始令每个顶点的第一条依附顶点的弧的指针为空

}

//输入边

int i,j,w;

for(int k = 0; k < G.arcnum; ++k)

{

ArcNode *m = (ArcNode*)malloc(sizeof(ArcNode));

printf("请输入顶点的序号和权值\n");

scanf_s("%d %d %d",&i,&j,&w);

printf("(Vi,Vj)下表为(%d,%d)的权值为%d:\n",i,j,w);

m->adjvex = j;

m->info = w;

//用头插法创造边表

m->next = G.vertices[i].first;

G.vertices[i].first = m;

//这个是无向图，而且令k

ArcNode *n = (ArcNode*)malloc(sizeof(ArcNode));

n->adjvex = i;

n->info = w;

//用头插法创建边表

n->next = G.vertices[j].first;

G.vertices[j].first = n;

}

}

//打印邻接表存储的图

void PrintALGraph(ALGraph G)

{

for(int i = 0; i < G.vexnum; ++i)

{

ArcNode *p = G.vertices[i].first;

printf("顶点编号为%d的值为：%c\n",i,G.vertices[i].data);

printf("顶点后面挂着的边表的值分别为：\n");

while(p != NULL)

{

printf("序号为：%d; 顶点值为：%c; (%c,%c)之间权值为：%d\n",p->adjvex,G.vertices[p->adjvex].data,G.vertices[i].data,G.vertices[p->adjvex].data,p->info);

p = p->next;

}

}

}

//求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1.

int FirstNeighbor(ALGraph G, int x)

{

if(x >= G.vexnum)

{

printf("图G不存在x\n");

return -1;

}

else if(G.vertices[x].first == NULL)

{

printf("图G中顶点x没有邻接点\n");

return -1;

}

else

{

ArcNode *p = G.vertices[x].first;//指向图G的顶点x的邻接点的指针

int i = p->adjvex;//邻接点的序号

int j = p->info;//两个顶点之间的权值

printf("图G中顶点序号为%d的值为%c的邻接点的序号为%d值为%c且权值为%d\n",x,G.vertices[x].data,i,G.vertices[i].data,j);

return i;

}

}

//假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

int NextNeighbor(ALGraph G,int x,int y)

{

ArcNode *p = G.vertices[x].first;

while(p->adjvex != y)

{

p = p->next;

}

if(p->next == NULL)

{

printf("%c是图G中顶点%c的最后一个邻接点\n",G.vertices[x].data,G.vertices[y].data);

return -1;

}

else

{

p = p->next;

int j = p->adjvex;

printf("%c是图G中除%c之外顶点%c的下一个邻接点\n",G.vertices[j].data,G.vertices[y].data,G.vertices[x].data);

return j;

}

}

好文链接