【数据结构】图的深度优先遍历 广度优先遍历
文件操作比直接输入方便许多
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 20/*邻接表的储存结构*/
typedef struct node /*表结点 或者 边表结点*/
{int adjvex;struct node *next;
}edgenode;typedef struct vnode /*头结点*/
{char vertex;edgenode *firsteage;
}vertexnode;typedef struct /*邻接表类型*/
{vertexnode adjlist[M];int n,e;
}linkedgraph;int vis[M];void creat (linkedgraph *g,int c)
{int i,j,k;edgenode *s;FILE *f;f=fopen("test.txt","r");if(f){fscanf(f,"%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){fscanf(f,"%1s",&g->adjlist[i].vertex);g->adjlist[i].firsteage=NULL;}for(k=0;k<g->e;k++){fscanf(f,"%d%d",&i,&j);s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=j;s->next=g->adjlist[i].firsteage;g->adjlist[i].firsteage=s;if(c==0){s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=i;s->next=g->adjlist[j].firsteage;g->adjlist[j].firsteage=s;}}fclose(f);}else{g->n=0;}
}void dfs(linkedgraph g,int i)
{edgenode *p;printf("%c ",g.adjlist[i].vertex);vis[i]=1;p=g.adjlist[i].firsteage;while(p){if(!vis[p->adjvex]){dfs(g,p->adjvex);}p=p->next;}
}void DfsTraverse(linkedgraph g)
{int i;memset(vis,0,sizeof(vis));printf("\nDFS:\n");for(i=0;i<g.n;i++){if(!vis[i]){dfs(g,i);printf("\n");}}printf("\n");
}void bfs(linkedgraph g,int i)
{int j;edgenode *p;int queue[M],front ,rear;front=0;rear=0;printf("%c ",g.adjlist[i].vertex);vis[i]=1;queue[rear++]=i;while(rear>front){j=queue[front++];p=g.adjlist[j].firsteage;while(p){if(vis[p->adjvex]==0){printf("%c ",g.adjlist[p->adjvex].vertex);queue[rear++]=p->adjvex;vis[p->adjvex]=1;}p=p->next;}}
}//返回连通分量的个数
int BfsTraverse(linkedgraph g)
{printf("BFS:\n");int i,count=0;memset(vis,0,sizeof(vis));for(i=0;i<g.n;i++){if(!vis[i]){count++;bfs(g,i);printf("\n");}}return count;
}void print(linkedgraph *g)
{printf("\n\n输出：\n");edgenode *p;int i;printf("一共有%d个结点，%d条边\n",g->n,g->e);for(i=0;i<g->n;i++){p=g->adjlist[i].firsteage;printf("V%d -> ",i);while(p){printf("%d",p->adjvex);if(p->next)printf(" -> ");p=p->next;}printf("\n");}
}int main ()
{int count;linkedgraph g;creat(&g,0);print(&g);DfsTraverse(g);count=BfsTraverse(g);printf("一共有%d个连通分量\n",count);return 0;
}
带权无向图的有区别的代码，有向图c=0即可。
typedef struct node /*表结点 或者 边表结点*/
{int adjvex;int data;struct node *next;
}edgenode;void creat (linkedgraph *g,int c)
{int i,j,k,w;edgenode *s;FILE *f;f=fopen("test.txt","r");if(f){fscanf(f,"%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){fscanf(f,"%1s",&g->adjlist[i].vertex);g->adjlist[i].firsteage=NULL;}for(k=0;k<g->e;k++){fscanf(f,"%d%d%d",&i,&j,&w);s=(edgenode*)malloc(sizeof(edgenode));s->data=w;s->adjvex=j;s->next=g->adjlist[i].firsteage;g->adjlist[i].firsteage=s;if(c==0){s=(edgenode*)malloc(sizeof(edgenode));s->data=w;s->adjvex=i;s->next=g->adjlist[j].firsteage;g->adjlist[j].firsteage=s;}}fclose(f);}else{g->n=0;}
}void print(linkedgraph *g)
{printf("\n\n输出：\n");edgenode *p;int i;printf("一共有%d个结点，%d条边\n",g->n,g->e);for(i=0;i<g->n;i++){p=g->adjlist[i].firsteage;printf("V%d -> ",i);while(p){printf("%d (w = %d)",p->adjvex,p->data);if(p->next)printf(" -> ");p=p->next;}printf("\n");}
}
相关文章：
C++ Primer(第4版)(评注版)
《C Primer(第4版)(评注版)》基本信息原书名： C Primer (4th Edition) 原出版社： Addison-Wesley Professional; 4 edition 作者： (美)Stanley B.Lippman Josee Lajoie Barbara E.Moo 译者： 陈硕 丛书名： 传世经典书丛…
win10安装emacs+spacemacs，建议用官方安装方式
1、下载emacs最新版 26.1 官网下载地址：https://www.gnu.org/software/emacs/download.html#nonfree 2、解压emacs到你的安装目录,我的系统是D:/Program File/。执行/bin目录下的addpm.exe 这一步会在开始菜单创建快捷方式 3、在系统环境变量中添加新项HOME(具体环…
【ACM】杭电OJ 2028
int 会 WA ，注意使用 long long 先除后乘，避免超出范围，但好像本题先乘后除也AC #include <iostream> #include <cstdio> #include <cstring>long long lcm(long long a,long long b) {long long c,t,ma,nb;if(a<b) {…
IIS8 添加配置 WCF服务
今天在Windows8.1 操作系统部署了半天的WCF 一直老是在报错、在这里做个记录 防止下次忘记 在网上查了半天。终于知道原来IIS８不支持WCF服务SVC的请求。所以必须要给IIS８添加WCF服务 的Managed Handler。 添加步骤： １打开IIS&a…
spacemacs各种问题修复方法
快捷键操作时报 tr不是内部命令 ------说明是缺少tr命令，win10可以安装coreutils for gnuwin32工具集，然后把bin目录加到系统path路径即可 没有ispell, flycheck error ------缺少ispell命令，windows下面用aspell替换，需要安装…
2016/08/27 What I Learned About Going Fast at eBay and Google
每天推荐一个英文视频 http://v.qq.com/page/i/2/d/i0...https://www.youtube.com/watch... 本日看点
【ACM】杭电OJ 2030
注意getchar()的使用，以及汉字占两个字节，因为比较特殊，可以单独记忆 #include <iostream> #include <cstdio> #include <cstring> int main () {char c;int n,i,sum;scanf("%d",&n);getchar();while(n--)…
背景图自适应屏幕居中显示，且不变形
html：<div classitem><div class container /> </div> css:.item {width: 100%;height: 100%;.container {max-width: 100%;height: auto;min-height: 600px; // 这里可监听屏幕变化，改变最小高度position: absolute;left: 50%;top:…
emacs按键绑定详解
key-binding: https://crazylxr.github.io/spacemacas-zh_CH-doc/binding-keys.html 概述：Emacs的键绑定方式看起来花样繁多，其本质上都是同一个机制 (define-key keymap key def) 这里的key是你要绑定的键。keymap是这个key所属的集合，不…
【面试】重建二叉树
一、描述 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树，假设输入的前序遍历和中序遍历的结果中都不含重复的数字，例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出该二叉树。二叉树结…
【ACM】杭电OJ 2034
开了三个数组 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <set> #include <algorithm> using namespace std; const int maxn 105; int a[maxn],b[maxn],c[maxn];…
Android 依赖库发布（上传 Library 到 JCenter）gradle最高支持4.4
1.注册 Bintray 注册时要注意哦，千万不要注册成组织的账户，一定要注册为个人。因为组织账户只有一个月的免费使用时间。 个人账户注册地址：bintray.com/signup/oss 有Github、Google、Twitter账号的可以直接登录哦 2.创建Maven仓库࿰…
emacs参考资料整理
spacemacs dired模式用法: https://blog.slegetank.com/blog/20170106-dired.htmlEmacs文件管理神器--dired常用操作说明 - 暗无天日快捷键用法：https://yuyang0.github.io/notes/spacemacs.htmlemacs官方参考手册：https://www.gnu.org/software/emacs/m…
Codeigniter文件上传类型不匹配错误
Codeigniter的文件上传类方便了我们使用PHP来处理文件上传的操作，使用起来非常简单，如下：$config[upload_path] ./uploads/;$config[allowed_types] gif|jpg|png;$config[max_size] 100;$config[max_width] 1024;$config[max_height] …
【ACM】杭电OJ 2036（待更）
AC代码 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <set> #include <algorithm> using namespace std; const int maxn 105; double a[maxn][3]; int main () {in…
Spring_boot_pom.xml和启动方式
spring-boot-starter-parent 整合第三方常用框架信息(各种依赖信息) spring-boot-starter-web 是Springboot整合SpringMvc Web 实现原理:Maven依赖继承关系 相当于把第三方常用maven依赖信息,在parent项目中已经封装好了 提供依赖信息关联整合的jar包 springboot中快速原理…
ubuntu18安装virtualbox
1. 报错No rule to make target arch/x86/tools/relocs_32.c 解决办法：sudo apt install linux-source sudo apt-get install linux-headers-5.4.0-42:i386 安装步骤： https://blog.csdn.net/AAMahone/article/details/86428040 安装完成后&…
10分钟学会php面相对象基础（Ⅰ）
<?php 声明一个类 class mycar{ etc. //成员方法 } class mycar{ function drive(){ etc. } } ?> 对象的实例化 内存中分栈和堆，栈定长，堆较大不能直接访问。实例化后，实例名称放在栈内，实例放在堆内，通过实例…
【ACM】杭电OJ 2039
先让啊、三边边长a，b，c按从小到大顺序排列，然后再用两边之和大于第三边，两边之差小于第三边来判断 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib&…
AI一周热闻：GitHub免费开放无限私有库；苹果市值蒸发超450亿美元；小米入股TCL...
CES 2019：英伟达发布RTX 2060和RTX 2080移动版小米入股TCL，增强供应链话语权苹果市值蒸发价值超过Facebook，全球市值第一不保GitHub开放无限私有仓库免费使用英特尔和Facebook等发布计算机视觉系统测试新基准旷视创建高性能的“姿态估计”网络…
ubuntu使用相关
ubuntu查看显卡驱动并安装适配的显卡驱动https://blog.csdn.net/qiancaobaicheng/article/details/95096354ubuntu20设置openssl tls versionhttps://www.coder.work/article/7495451
Atitit.提升 升级类库框架后的api代码兼容性设计指南
Atitit.提升 升级类库框架后的api代码兼容性设计指南 1. 增加api直接增加，版本号在注释上面增加1 2. 废弃api，使用主见dep1 3. 修改api，1 4. 修改依赖import，雅瑶增加文件模式。保持兼容性。。1 5. 优先选择同一个文件内的修改&am…
【ACM】杭电OJ 2040
第一个程序是 15MS #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <set> #include <algorithm> using namespace std; const int maxn 600000; int vis[maxn]; int ma…
阿里云 Aliplayer高级功能介绍(二)：缩略图
为什么80%的码农都做不了架构师？>>> 基本介绍 Aliplayer提供了缩略图的功能，让用户在拖动进度条之前知道视频的内容，用户能够得到很好的播放体验，缩略图是显示在Controlbar的上面，并且包含当前的时间&…
【ACM】杭电OJ 2044 2045
一开始全部使用int型，显示WA，百度之后，要全部改成long long 两个题都是死在long long 上 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <s…
POJO、JavaBean、DAO
POJO POJO全称是Plain Ordinary Java Object / Plain Old Java Object，中文可以翻译成：普通Java类，具有一部分getter/setter方法的那种类就可以称作POJO。一般在web应用程序中建立一个数据库的映射对象时，我们只能称它为POJO。 Ja…
jupyter notebook用法积累（快捷键）
打开Anaconda promt，如果想把代打都存在H：\python\py，则输入命令 h: 回车进入h盘，再输入 cd python\py回车就进入这个H：\python\py目录下再输入jupter notebook 回车就打开了浏览器 ctrl回车 可以当前块运行࿰…
android资料整理
1. android native内存分析：全民K歌Android端Native内存分析与监控方案实践总结 - 知乎一、背景在2020年的上半年，我们在用户反馈后台发现闪退、白屏问题不断增多，这些问题严重影响用户体验。观察Crash监控平台发现Crash率也在逐步升高,其中N…
Java读取property配置文件
读取配置文件已经成了Java程序员工作的一项必备技能。 配置文件的优点： 可维护性好 怎么个可维护性好呢？ 它会让程序中变化的地方很灵活的配置，不需要修改代码。Java程序部署到服务器上去之后就变成了class文件，修改困难…
【ACM】杭电OJ 2048 2049
两题均是错排公式与阶乘的运用 2048算的是一个比例，2049计算的是一个事情发生的总数 一个用double 来存放数据，一个用long long来存放数据 2048 #include <iostream> #include <cstdio> #include <cstring> #include <cmath&g…