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

news/2024/11/17 21:24:19/

一.邻接矩阵法

将下列图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]);elseprintf("编号为%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]);elseprintf("编号为%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<G.arcnum，因为一个弧对应两个顶点，两个顶点都是顶点表中的，所以要同时将两个顶点表的边表都弄好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<stdio.h>
#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]);elseprintf("编号为%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]);elseprintf("编号为%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<stdio.h>
#include<malloc.h>
#include<stdlib.h>#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<G.arcnum，因为一个弧对应两个顶点，两个顶点都是顶点表中的，所以要同时将两个顶点表的边表都弄好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;}
}


http://www.ppmy.cn/news/583494.html

相关文章

途乐证券|股票XR是什么意思？买股票为什么赚不到钱？

途乐证券|股票XR是什么意思？买股票为什么赚不到钱？

股票市场上有时会出现一些股票在其名称前加上英文字母的情况&#xff0c;比如XD、XR等。那么股票XR是什么意思&#xff1f;买股票为什么赚不到钱&#xff1f;途乐证券为大家准备了相关内容&#xff0c;以供参考。 股票XR是什么意思&#xff1f; 股票名称中带有XR是表示股票在进…
阅读更多...
民用飞机飞控系统传感器故障诊断研究综述

民用飞机飞控系统传感器故障诊断研究综述

导语 飞控系统中的各类传感器对飞机稳定与操纵起着至关重要的影响&#xff0c;是飞机的重要安全机载设备之一。传统冗余方法具有“安全性高&#xff0c;经济性低”的特点&#xff0c;通过多余度设计来提升系统的安全性给飞机的重量与结构设计、系统综合集成、维修与检测成本都…
阅读更多...
详解MySQL的常用数据类型

详解MySQL的常用数据类型

文章目录 一、MySQL 数据类型1.1、mysql中编码和字符 二、数值类型2.1、整数类型的长度2.2、浮点型 三、字符串类型3.1、字符串类型长度 四、日期和时间类型4.1、DATETIME 五、二进制数据类型六、使用建议 一、MySQL 数据类型 MySQL支持很多数据类型&#xff0c;以便我们能在复…
阅读更多...
【永久服务器】EUserv

【永久服务器】EUserv

1. 请先自行准备网络&#xff08;我用的伦敦还可以&#xff09;、以及visa卡&#xff0c;淘宝可以代付&#xff0c;我总共花了97人民币&#xff08;10.94欧代付费&#xff09; 现在只能申请一台&#xff0c;多了会被删除&#xff0c;也就是两欧元&#xff0c;然后选择visa卡 选…
阅读更多...
sql增删改查语句

sql增删改查语句

sqlite语句 1.新建数据表 create table t_student(id INT PRIMARY KEY NOT NULL, name TEXT NOT NULL, score REAL NOT NULL); 2.删除数据表 drop table 3.往数据表插入数据条目 insert into t_st…
阅读更多...
【2023 · CANN训练营第一季】应用开发深入讲解之DVPP

【2023 · CANN训练营第一季】应用开发深入讲解之DVPP

应用开发深入讲解之DVPP 1.基本概念 昇腾Al处理器内置图像处理单元DVPP(Digital Video Pre-Processor)&#xff0c;提供强大的媒体处理硬加速能力。主要功能模块有&#xff1a; 2.常见接口 a.内存申请与释放 b.通道创建与释放 c.图片描述信息创建与销毁 d.图片描述参…
阅读更多...
CSND,再见。

CSND,再见。

红字醒目&#xff1a; 换博客了&#xff01;新博客名&#xff1a;魏延是反贼&#xff01;欢迎大家前往。 受不了CSDN的博客氛围&#xff0c;随便写个程序就可以瞬间把别人的博客踩成渣。 瞬间20踩的记录让我看的心花怒放~ 写个博客&#xff0c;博客的编辑器也好的不得了&…
阅读更多...
再见，CSND

再见，CSND

再见&#xff0c;CSND 一别两年&#xff0c;今又归来。如今我已回到家乡一年多了&#xff0c;进入了家乡的事业单位工作。告别了魔都上海&#xff0c;告别我所热爱的技术工作。今天我又回首往事&#xff0c;回忆这几年一路走来的点点滴滴&#xff0c;再次去体会曾经。从心灵深…
阅读更多...
最新文章

Copyright @ 2022~2023