图的基本操作

2023-07-06 0 1,370

定义

//邻接矩阵
typedef struct MGraph{
	char vex[MAXSIZE];
	int edge[MAXSIZE][MAXSIZE];
	int vexnum,edgenum;
}MGraph;
//带权重的邻接矩阵
struct MGraphW{
	//储存的顶点表 
	char vex[MAXSIZE];
	//路径矩阵,只不过改成权重了 
	int weight[MAXSIZE][MAXSIZE];
	//存储顶点与边的个数
	int vexnum,arcnum;
};
//邻接表
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *next;
}ArcNode; 
typedef struct VNode{
	char value;
	ArcNode *first;
}VNode,AdjList[MAXSIZE];
typedef struct{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;

基本操作

//创建邻接矩阵
MGraph createMGraph(){
	MGraph G;
	scanf("%d,%d",&G.vexnum,&G.edgenum);
	for(int i=0;i<MAXSIZE;i++){
		scanf("%c",&G.vex[i]); //输入顶点的符号 
		for(int j=0;j<MAXSIZE;j++){
			G.edge[i][j] = 0;
		}
	}
	int v1,v2;
	for(int i=0;i<G.edgenum;i++){
		scanf("%d,%d",&v1,&v2);
		G.edge[v1][v2] = 1;
	}
	return G;
} 

//邻接矩阵求入度
int getInDegreeByMG(MGraph G,int k){
	int sum = 0;
	for(int i=0;i<G.vexnum;i++){
		if(G.edge[i][k]!=0)sum++;
	}
	return sum;
} 

//邻接矩阵求出度
int getOutDegreeByMG(MGraph G,int k){
	int sum = 0;
	for(int i=0;i<G.vexnum;i++){
		if(G.edge[k][i]!=0)sum++;
	}
	return sum;
} 

//邻接矩阵求解有向图的边数
int getEdgeNumInDMG(MGraph G){
	int sum = 0;
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(G.edge[i][j]!=0)sum++;
		}
	}
	return sum;
}

//邻接矩阵创建带权重的有向图
MGraphW createGraphW(){
	MGraphW G;
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	for(int i=0;i<G.vexnum;i++){
		scanf("%c",&G.vex[i]); //输入顶点的符号 
		for(int j=0;j<G.vexnum;j++){
			G.weight[i][j] = INF;
		}
	}
	int v1,v2,w; 
	for(int i=0;i<G.arcnum;i++){
		scanf("%d,%d,%d",&v1,&v2,&w);
		G.weight[v1][v2] = w;
	}
	return G;
}

//邻接矩阵创建无向图
MGraph createMGraphWD(){
	MGraph G;
	scanf("%d,%d",&G.vexnum,&G.edgenum);
	for(int i=0;i<G.vexnum;i++){
		scanf("%c",&G.vex[i]); //输入顶点的符号 
		for(int j=0;j<G.vexnum;j++){
			G.edge[i][j] = 0;
		}
	}
	int v1,v2,w; 
	for(int i=0;i<G.edgenum;i++){
		scanf("%d,%d",&v1,&v2);
		G.edge[v1][v2] = 1;
		G.edge[v2][v1] = 1;
	}
	return G;
}

//邻接矩阵创建带权重的无向图
MGraphW createGraphWD(){
	MGraphW G;
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	for(int i=0;i<G.vexnum;i++){
		scanf("%c",&G.vex[i]); //输入顶点的符号 
		for(int j=0;j<G.vexnum;j++){
			G.weight[i][j] = INF;
		}
	}
	int v1,v2,w; 
	for(int i=0;i<G.arcnum;i++){
		scanf("%d,%d,%d",&v1,&v2,&w);
		G.weight[v1][v2] = w;
		G.weight[v2][v1] = w;
	}
	return G;
}

//(难)创建邻接表
ALGraph createALGraph(){
	ALGraph G;
	//p代表前一个结点 q代表工作结点 
	ArcNode *p,*q;
	int n; 
	scanf("%d,%d",&G.vexnum,&G.arcnum); 
	for(int i=0;i<G.vexnum;i++){
		//输入点的值和此点的边数 
		scanf("%c,%d",&G.vertices[i].value,n);
		for(int j=0;j<n;j++){
			//构造弧链表 
			q = (ArcNode*)malloc(sizeof(ArcNode));
			scanf("%d",&q->adjvex);
			if(!G.vertices[i].first){
				q->next = NULL;
				G.vertices[i].first = q;
				p = q;
			}else{
				q->next = NULL;
				p->next = q;
				p = q;
			}
		}
		p = q = NULL;
	}
	return G;
}

//邻接表求出度
int getOutDegreeByALG(ALGraph G,int k){
	int sum = 0;
	ArcNode *p;
	p = G.vertices[k].first;
	while(p){
		sum++;
		p = p->next;
	}
	return sum;
} 

//邻接表求入度
int getInDegreeByALG(ALGraph G,int k){
	int sum=0;
	ArcNode *p;
	for(int i=0;i<G.vexnum;i++){
		p = G.vertices[i].first;
		while(p){
			if(p->adjvex == k)sum++;
			p = p->next;
		}
	}
	return sum;
}
收藏 (0) 打赏

感谢您的支持,我会继续努力的!

打开微信扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

本站部分资源收集自互联网,我站仅分享内容,仅供用户个人研究,不提供商业使用,如有侵权下架处理,觉得资源内容不错请您在官方渠道购买正版,您在阅读的同时下载的内容本站不承担任何法律责任!Some resources of this website are collected from the Internet. We only share the content, which is only for personal research of users, and not for commercial use. If there is infringement and off shelf processing, please purchase the authentic version of the resource content from the official channel if you think it is good. We will not bear any legal responsibility for the content you download while reading!

橙凰素材-精品源码下载|正版主题更新 学习交流 图的基本操作 https://b.bqzmz.com/2023/07/06/%e5%9b%be%e7%9a%84%e5%9f%ba%e6%9c%ac%e6%93%8d%e4%bd%9c/

一名苦逼的程序员

常见问题
  • 正版主题是指站长在指定渠道购买的官方主题,提供作者联系,资源支持,长期更新等等内容
查看详情
  • 非常抱歉,请联系网站页脚的客服,我们将在核实后下架处理并返还给您此资源的收益(会扣去网站运营的费用),谢谢理解!
查看详情
  • 网络资源是站长从互联网分享收集而来的内容,本站不会做测试,直接分享,不包源码可用性,运营性,如有需求点击右边的联系正版,谢谢!
查看详情
  • 如果资源不是最新版本,请在资源下方评论区进行催更或提交工单处理,我们会尽快更新并通过邮箱通知您。
查看详情

相关文章

发表评论
暂无评论
官方客服团队

为您解决烦忧 - 24小时在线 专业服务