数据结构-图的课后习题（2）

题目要求：

对于下面的这个无向网，给出：

1.“深度优先搜索序列”（从V1开始）

2.“广度优先序列”（从V1开始）

3.“用Prim算法求最小生成树”

代码实现：

1.深度优先搜索：

代码部分：

#include<stdio.h>
#include<malloc.h>
#define MAX 100typedef struct ArcNode{int adjvex;int weight;struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{char vertex[2];ArcNode *firstarc;
}VNode;
typedef VNode AdjList[MAX];
typedef struct ALGraph{AdjList adjlist;int vexnum,arcnum;
}ALGraph;int LocateVerTex(ALGraph *G,char *v)
{int k;for(k=0;k<G->vexnum;k++)if(G->adjlist[k].vertex[0] == v[0] && G->adjlist[k].vertex[1] == v[1])return k;return -1;	
}void CreateALGraph(ALGraph *G)
{int i,adj1,adj2;int weight;char v1[2],v2[2];ArcNode *tmp = NULL;printf("请输入顶点个数和边数:\n");scanf("%d %d",&G->vexnum,&G->arcnum);getchar();printf("请输入{%d}个顶点\n",G->vexnum);for(i=0;i<G->vexnum;i++){scanf("%c%c",&G->adjlist[i].vertex[0],&G->adjlist[i].vertex[1]);G->adjlist[i].firstarc = NULL;}getchar();printf("请输入{%d}条边,格式(v1 v2 权值).\n",G->arcnum);for(i=0;i<G->arcnum;i++){scanf("%c%c %c%c %d",&v1[0],&v1[1],&v2[0],&v2[1],&weight);getchar();adj1 = LocateVerTex(G,v1);adj2 = LocateVerTex(G,v2);if(adj1 == -1 || adj2 == -1){printf("失败.\n");i = i - 1;continue;}else{tmp = (ArcNode*)malloc(sizeof(ArcNode));tmp->adjvex = adj2;tmp->weight = weight;tmp->nextarc = G->adjlist[adj1].firstarc;G->adjlist[adj1].firstarc = tmp;tmp = (ArcNode*)malloc(sizeof(ArcNode));tmp->adjvex = adj1;tmp->weight = weight;tmp->nextarc = G->adjlist[adj2].firstarc;G->adjlist[adj2].firstarc = tmp;printf("成功.\n");}}
}void DFS(ALGraph *G,int v,int *visit)
{	int w;ArcNode *tmp = NULL;visit[v] = 1;printf("访问顶点:{%c%c}.\n",G->adjlist[v].vertex[0],G->adjlist[v].vertex[1]);tmp = G->adjlist[v].firstarc;while(tmp){w = tmp->adjvex;if(visit[w] == 0){DFS(G,w,visit);}tmp = tmp->nextarc;}
}void DFSTraverse(ALGraph *G)
{int visit[G->vexnum];int v;for(v=0;v<G->vexnum;v++){visit[v] = 0;}for(v=0;v<G->vexnum;v++){if(visit[v] == 0){DFS(G,v,visit);}}
}int main()
{ALGraph G;CreateALGraph(&G);DFSTraverse(&G);return 0;
}

验证：

2.广度优先搜索：

代码部分：

#include<stdio.h>
#define MAX 100
typedef struct MGraph{char vertex[MAX][2];int arcs[MAX][MAX];int vexnum,arcnum;
}Mgraph;
int LocateVerTex(MGraph *G,char *v)
{int k;for(k=0;k<G->vexnum;k++){if(G->vertex[k][0] == v[0] && G->vertex[k][1] == v[1])return k;}return -1;	
}void CreateMGraph(MGraph *G)
{int i,j,adj1,adj2;int weight;char v1[2],v2[2];printf("请输入顶点个数和边数:\n");scanf("%d %d",&G->vexnum,&G->arcnum);getchar();printf("请输入{%d}个顶点\n",G->vexnum);for(i=0;i<G->vexnum;i++){scanf("%c%c",&G->vertex[i][0],&G->vertex[i][1]);}getchar();for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j] = 0;printf("请输入{%d}条边,格式(v1 v2 权值).\n",G->arcnum);for(i=0;i<G->arcnum;i++){scanf("%c%c %c%c %d",&v1[0],&v1[1],&v2[0],&v2[1],&weight);getchar();adj1 = LocateVerTex(G,v1);adj2 = LocateVerTex(G,v2);if(adj1 == -1 || adj2 == -1){printf("失败.\n");i = i - 1;continue;}else{G->arcs[adj1][adj2] = weight;G->arcs[adj2][adj1] = weight;printf("成功.\n");}}
}void BFSTraverse(MGraph *G)
{int Q[G->vexnum+1],visit[G->vexnum];int i,u,w;for(i=0;i<G->vexnum;i++)visit[i] = 0;int front = 0,rear = 0;for(i=0;i<G->vexnum;i++){if(visit[i] == 0){visit[i] = 1;printf("输出顶点:{%c%c}\n",G->vertex[i][0],G->vertex[i][1]);Q[rear] = i;rear = (rear+1) % (G->vexnum+1);while(front != rear){u = Q[front];front = (front+1) % (G->vexnum+1);for(w=0;w<G->vexnum;w++){if(G->arcs[u][w] != 0 && visit[w] == 0){visit[w] = 1;printf("输出顶点:{%c%c}\n",G->vertex[w][0],G->vertex[w][1]);Q[rear] = w;rear = (rear+1) % (G->vexnum+1);}}}}}
}int main()
{MGraph G;CreateMGraph(&G);BFSTraverse(&G);return 0;
}

验证：

3.用Prim算法求得最小生成树：

代码部分：

#include<stdio.h>
#define MAX 100
typedef struct MGraph{char vertex[MAX][2];int arcs[MAX][MAX];int vexnum,arcnum;
}Mgraph;
typedef struct closedge{char vertex[MAX][2];int lowcost[MAX];
}closedge;int LocateVerTex(MGraph *G,char *v)
{int k;for(k=0;k<G->vexnum;k++){if(G->vertex[k][0] == v[0] && G->vertex[k][1] == v[1])return k;}return -1;	
}void CreateMGraph(MGraph *G)
{int i,j,adj1,adj2;int weight;char v1[2],v2[2];printf("请输入顶点个数和边数:\n");scanf("%d %d",&G->vexnum,&G->arcnum);getchar();printf("请输入{%d}个顶点\n",G->vexnum);for(i=0;i<G->vexnum;i++){scanf("%c%c",&G->vertex[i][0],&G->vertex[i][1]);}getchar();for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j] = 999;printf("请输入{%d}条边,格式(v1 v2 权值).\n",G->arcnum);for(i=0;i<G->arcnum;i++){scanf("%c%c %c%c %d",&v1[0],&v1[1],&v2[0],&v2[1],&weight);getchar();adj1 = LocateVerTex(G,v1);adj2 = LocateVerTex(G,v2);if(adj1 == -1 || adj2 == -1){printf("失败.\n");i = i - 1;continue;}else{G->arcs[adj1][adj2] = weight;G->arcs[adj2][adj1] = weight;printf("成功.\n");}}
}int MiniMum(MGraph *G,closedge *cd)
{int j,p=1,min=999;for(j=0;j<G->vexnum;j++){if(cd->lowcost[j] != 0 && cd->lowcost[j] < min){min = cd->lowcost[j];p = j;}}return p;
}void MiniSpanTree_PRIM(MGraph *G,char *u)
{closedge cd;int i,j,k;k = LocateVerTex(G,u);for(j=0;j<G->vexnum;j++){if(j != k){cd.vertex[j][0] = u[0];cd.vertex[j][1] = u[1];cd.lowcost[j] = G->arcs[k][j];}}cd.lowcost[k] = 0;printf("最小代价生成树的各条边为:\n");for(i=1;i<G->vexnum;i++){k = MiniMum(G,&cd);printf("输出边%c%c->%c%c,权值为:{%d}\n",cd.vertex[k][0],cd.vertex[k][1],G->vertex[k][0],G->vertex[k][1],cd.lowcost[k]);cd.lowcost[k] = 0;for(j=0;j<G->vexnum;j++){if(G->arcs[k][j] < cd.lowcost[j]){cd.vertex[j][0] = G->vertex[k][0];cd.vertex[j][1] = G->vertex[k][1];cd.lowcost[j] = G->arcs[k][j];}}}
}int main()
{char original_vertex[2]={'V','1'};MGraph G;CreateMGraph(&G);MiniSpanTree_PRIM(&G,original_vertex);return 0;
}

验证：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/187593.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

AI由许多不同的技术组成，其中一些最核心的技术如下

AI由许多不同的技术组成，其中一些最核心的技术如下

AI由许多不同的技术组成&#xff0c;其中一些最核心的技术包括&#xff1a; 机器学习&#xff1a;这是一种让计算机从数据中学习的技术&#xff0c;它可以根据已有的数据预测未来的趋势和行为。机器学习包括监督学习、无监督学习和强化学习等多种类型。深度学习&#xff1a;这…
阅读更多...
Java-多态

Java-多态

1. 多态 1.1 多态的概念 多态的概念&#xff1a;通俗来说&#xff0c;就是多种形态&#xff0c;具体点就是去完成某个行为&#xff0c;当不同的对象去完成时会产生出不同的状态。 1.2 多态实现条件 在java中要实现多态&#xff0c;必须要满足如下几个条件&#xff0c;缺一不…
阅读更多...
C语言--汉诺塔【内容超级详细】

C语言--汉诺塔【内容超级详细】

今天与大家分享一下如何用C语言解决汉诺塔问题。 目录 一.前言 二.找规律⭐ 三.总结⭐⭐⭐ 四.代码实现⭐⭐ 一.前言 有一部很好看的电影《猩球崛起》⭐&#xff0c;说呀&#xff0c;人类为了抗击癌症发明了一种药物&#x1f357;&#xff0c;然后给猩猩做了实验&#xff0…
阅读更多...
LeetCode（4）删除有序数组中的重复项 II【数组/字符串】【中等】

LeetCode（4）删除有序数组中的重复项 II【数组/字符串】【中等】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; 80. 删除有序数组中的重复项 II 1.题目 给你一个有序数组 nums &#xff0c;请你** 原地** 删除重复出现的元素&#xff0c;使得出现次数超过两次的元素只出现两次 &#xff0c;返回删除后数组的新长度。 不要使用额外的数…
阅读更多...
Conda executable is not found 三种问题解决

Conda executable is not found 三种问题解决

如果在PyCharm中配置Python解释器时显示“conda executable is not found”错误消息&#xff0c;这意味着PyCharm无法找到您的Conda可执行文件。您可以按照以下步骤解决此问题&#xff1a; 1.方法一 确认Conda已正确安装。请确保您已经正确安装了Anaconda或Miniconda&#xff…
阅读更多...
前端-第一部分-HTML

前端-第一部分-HTML

一.初识HTML 1.1 HTML 简介 HTML 全称为 HyperText Mark-up Language&#xff0c;翻译为超文本标签语言&#xff0c;标签也称作标记或者元素。HTML 是目前网络上应用最为广泛的技术之一&#xff0c;也是构成网页文档的主要基石之一。HTML文本是由 HTML 标签组成的描述性文本&a…
阅读更多...
Hadoop架构、Hive相关知识点及Hive执行流程

Hadoop架构、Hive相关知识点及Hive执行流程

Hadoop架构 Hadoop由三大部分组成:HDFS、MapReduce、yarn HDFS&#xff1a;负责数据的存储 其中包括&#xff1a; namenode&#xff1a;主节点&#xff0c;用来分配任务给从节点 secondarynamenode&#xff1a;副节点&#xff0c;辅助主节点 datanode&#xff1a;从节点&#x…
阅读更多...
评国青、优青、杰青，到底需要什么级别的文章？五篇代表作如何选？

评国青、优青、杰青，到底需要什么级别的文章？五篇代表作如何选？

一到年底就听同事们讨论到底申报“杰青”、“优青”还是“国青”&#xff0c;那么&#xff0c;“杰青”到底是什么呢&#xff1f;它和“优青”、“国青”又有什么区别呢&#xff1f; 杰青&#xff0c;全称“国家杰出青年基金获得者”&#xff0c;是国家自然科学基金里人才资助…
阅读更多...
WAF入侵防御系统标准检查表

WAF入侵防御系统标准检查表

软件开发全文档获取&#xff1a;进主页
阅读更多...
pyOCD

pyOCD

pyOCD 目录结构
阅读更多...
在 Arduino IDE 2.0 中安装 ESP32 板（Windows、Mac OS X、Linux）

在 Arduino IDE 2.0 中安装 ESP32 板（Windows、Mac OS X、Linux）

有一个新的 Arduino IDE——Arduino IDE 2.0&#xff08;测试版&#xff09;。在本教程中&#xff0c;您将学习如何在 Arduino IDE 2.0 中安装 ESP32 板并将代码上传到板。本教程与 Windows、Mac OS X 和 Linux 操作系统兼容。 据 Arduino 网站称&#xff1a;“ Arduino IDE 2.…
阅读更多...
机器学习---多分类SVM、支持向量机分类

机器学习---多分类SVM、支持向量机分类

1. 多分类SVM 1.1 基本思想 Grammer-singer多分类支持向量机的出发点是直接用超平面把样本空间划分成M个区域&#xff0c;其 中每个区域对应一个类别的输入。如下例&#xff0c;用从原点出发的M条射线把平面分成M个区域&#xff0c;下图画 出了M3的情形&#xff1a; 1.2 问题…
阅读更多...
局域网内部服务器访问外部网络

局域网内部服务器访问外部网络

​ 一、环境说明 如下图所示&#xff0c;局域网1中的服务器是可以访问外网的&#xff0c;局域网2中的服务器发出的数据包经过中间路由可以到达局域网1中的服务器。现在有一种需求需要使局域网2中的服务器也要能访问外网&#xff0c;这里考虑采用如下方法来实现。 ​​ 二、软…
阅读更多...
MySQL | 数据库的表的增删改查【进阶】

MySQL | 数据库的表的增删改查【进阶】

MySQL | 数据库的表的增删改查【进阶】 文章目录 MySQL | 数据库的表的增删改查【进阶】系列文章目录本节目标&#xff1a;数据库约束约束类型NULL约束UNIQUE&#xff1a;唯一约束DEFAULT&#xff1a;默认值PRIMARY KEY&#xff1a;主键FOREIGN KEY&#xff1a;外键CHECK 表的设…
阅读更多...
JSON可视化管理工具JSON Hero

JSON可视化管理工具JSON Hero

本文软件由网友 zxc 推荐&#xff1b; 什么是 JSON Hero &#xff1f; JSON Hero 是一个简单实用的 JSON 工具&#xff0c;通过简介美观的 UI 及增强的额外功能&#xff0c;使得阅读和理解 JSON 文档变得更容易、直观。 主要功能 支持多种视图以便查看 JSON&#xff1a;列视图…
阅读更多...
网易云音乐未登录接口返回301

网易云音乐未登录接口返回301

网易云音乐 NodeJS 版 API (neteasecloudmusicapi.js.org) 上面是网易云音乐的官方API接口文档 当我调用接口发送请求的时候部分接口数据是需要登录之后进行获取的&#xff0c;但是当我发送请求的时候原生js项目中的跨端问题是比较难解决的。 遇到的问题&#xff1a;跨端请求…
阅读更多...
启动Docker服务后显示Docker Engine stopped

启动Docker服务后显示Docker Engine stopped

1、重新启动Docker服务&#xff1a;打开Windows服务管理器&#xff08;可以在开始菜单中搜索&#xff09;&#xff0c;找到"Docker Desktop Service"或类似命名的服务&#xff0c;右键单击并选择"重启"。稍等片刻&#xff0c;看看是否重新启动成功 2、尝试…
阅读更多...
「我在淘天做技术」音视频技术及其在淘宝内容业务中的应用

「我在淘天做技术」音视频技术及其在淘宝内容业务中的应用

作者&#xff1a;李凯 一、前言 近年来&#xff0c;内容电商似乎已经充分融入到人们的生活中&#xff1a;在闲暇时间&#xff0c;我们已经习惯于拿出手机&#xff0c;从电商平台的直播间、或者短视频链接下单自己心仪的商品。 尽管优质的货品、实惠的价格、精致的布景、有趣的…
阅读更多...
最新宝塔面板第三方云端站点程序源码/第三方宝塔面板PHP源码/全开源ThinkPHP框架

最新宝塔面板第三方云端站点程序源码/第三方宝塔面板PHP源码/全开源ThinkPHP框架

源码简介&#xff1a; 实现宝塔面板第三方云端站点程序源码,这个是第三方宝塔面板 btcloud PHP源码&#xff0c;它还有云端使用记录、IP黑白名单、定时任务等功能。 这是一个使用PHP开发的宝塔面板第三方云端站点程序。 您可以利用此程序搭建属于自己的宝塔面板第三方云端&a…
阅读更多...
使用切面实现前端重复提交（防抖）

使用切面实现前端重复提交（防抖）

使用切面实现前端重复提交&#xff08;防抖&#xff09; 代码结构定义注解请求锁切面处理器入参对象使用注解 代码结构 原理&#xff1a; 1、前端提交保存操作&#xff1b; 2、后端通过注解指定重复提交的关键字段进行识别&#xff0c;可以有多个&#xff1b; 3、拼接关键字段&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023