基于图的深度优先搜索策略(耿7.10)_试基于图的深度-程序员宅基地

技术标签: 数据结构—图  

Description

试基于图的深度优先搜索策略编写程序,判别以邻接表方式存储的有向图中,是否存在由顶点vi到顶点vj的路径(i不等于j)。注意:程序中涉及的图的基本操作必须在此存储结构上实现。

Input

第一行输入有向图的顶点数n和边数m,用空格隔开;第二行输入顶点信息;分m行输入有向图边的信息,例如顶点对1,2表示从顶点1到顶点2的一条弧。最后一行输入待判别的顶点对vi,vj.(0<m,n<100)

Output

若有向图中存在由顶点vi到顶点vj的路径(i不等于j),则输出yes;否则输出no。

  Sample input

  4 4

  1 2 3 4

  1 2

  1 3

  1 4

  2 3

  Sample output

   yes
#include <stdio.h>
#include <stdlib.h>

typedef struct lnode//邻接表结点
{
    int v,tag;
    struct lnode *next;
}lnode;

typedef struct tnode//表头结点
{
    int v,tag;
    lnode *head;
}tnode;

typedef struct graph
{
    tnode h[20];
    int n,m;
}graph;

void DFS(graph g,int vi,int vj,int *t)
{
    lnode *p;
    if(g.h[vi].head){
            p=g.h[vi].head;
        while(p){
            if(p->tag==0){
                p->tag=1;
                if(p->v==vj) break;
                else{
                    if(*t==1) break;
                    else DFS(g,p->v,vj,t);
                }
            }
            else p=p->next;
        }
        if(p&&p->v==vj) printf("yes"),*t=1;
    }
}

int main()
{
    graph g;
    lnode *p;
    int i,a,b,vi,vj,*t;
    t=(int*)malloc(sizeof(int));
    *t=0;
    scanf("%d %d",&g.n,&g.m);
    for(i=0;i<g.n;i++){
        scanf("%d",&g.h[i].v);
        g.h[g.h[i].v].head=NULL;
    }
    for(i=0;i<g.m;i++){//建立邻接表
        scanf("%d %d",&a,&b);
        p=(lnode*)malloc(sizeof(lnode));
        if(g.h[a].head==NULL){
            p->v=b,p->tag=0,p->next=NULL,g.h[a].head=p;
        }
        else{
            p->v=b,p->tag=0,p->next=g.h[a].head->next,g.h[a].head->next=p;
        }
    }
    scanf("%d %d",&vi,&vj);
    DFS(g,vi,vj,t);
    if(*t!=1) printf("no");
    return 0;
}
又是自己瞎编的,编完看了看老师的,觉得老师的简单的多……下次一定先看笔记。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39683838/article/details/80850199

智能推荐

glide默认的缓存图片路径地址_android – Glide:获取缓存文件位置-程序员宅基地

文章浏览阅读1.5k次。我正在使用Glide在我的应用程序中显示图像.现在我想知道Glide存储从网址下载的缓存图像的位置.我使用下面的代码来显示图像.Glide.with(mContext).load(mData.get(position).getImage()).centerCrop().override(300, 300).placeholder(R.drawable.default_small).diskCach..._diskcachestrategy保存的地址是哪里

Python的数据类型——数字(Number)_python number-程序员宅基地

文章浏览阅读3.6k次,点赞2次,收藏11次。Python数据类型----数字类型_python number

C语言实现二叉树的遍历(非递归)_先序非递归遍历二叉树c语言-程序员宅基地

文章浏览阅读511次。C语言实现二叉树的遍历(非递归)_先序非递归遍历二叉树c语言

Linux下Nginx配置nginx-module-vts_no nginx-module-vts/config was found-程序员宅基地

文章浏览阅读5.7k次,点赞2次,收藏5次。用Prometheus进行nginx的监控可以自动的对相关server_name和upstream进行监控,你也可以自定义Prometheus的数据标签,实现对不同机房和不同项目的nginx进行监控。监控Nginx主要用到以下三个模块:nginx-module-vts:Nginx的监控模块,能够提供JSON格式的数据产出。nginx-vts-exporter:主要用于收集Nginx的监控数据,并给Prometheus提供监控接口,默认端口号9913。Prometheus:监控Nginx-vt_no nginx-module-vts/config was found

系统运维架构师体系_系统运维体系-程序员宅基地

文章浏览阅读961次,点赞2次,收藏12次。一、系统运维架构师体系1. 系统运维架构体系排列:2. Linux运维架构的薪资水平:3. Linux运维的技能进化论4. Linux运维大致的知识框架4-1. Linux系统初级体系4-2. Linux系统中高级体系5. Linux运维的具体规划实践5-1. Linux运维基础5-2. Linux运维进阶6. Linux工作的必备要求7. Linux运维学习建议一、系统运维架构师体系1.系统运维架构体系排列:Linux运维工程师 应用运维工程师,大数据运维工程师,运维开发工程师,云计算运维工程_系统运维体系

DITA-OT 4.0新特性 - PDF themes,定制PDF样式的新方法-程序员宅基地

文章浏览阅读655次。DITA-OT 4.0推出PDF Themes,用于简化PDF样式发布。本文是对此功能特性的实验和总结。

随便推点

VMware centos7增加磁盘空间_vmware 新增磁盘动态生效 centos 7-程序员宅基地

文章浏览阅读192次。我们创建centos的时候默认创建20G磁盘大小,往往 不够用前提:关机在VMware客户端更改大小开机后查看分区信息fdisk -l一般来说扩容的大小都会位于/dev/sda之上创建新的分区fdisk /dev/sda输入n创建新分区接着选p创建主分区一直回车,会有创建成功提示接下来再输入t选择创建的分区的分区号接着输入8e将分区类型设置为linux lvm类型最后输入w保存退出查看分区fdisk -l如果看到一个新的分区并且类型为linux lvm说明创建成功了!_vmware 新增磁盘动态生效 centos 7

SpringBoot 整合 SpringSecurity——自定义登录页面_springboot集成springsecurity+自定义页面-程序员宅基地

文章浏览阅读4.2k次。SpringBoot 整合 SpringSecurity——自定义登录页面_springboot集成springsecurity+自定义页面

HTML5存储系统_html实现信息存储系统-程序员宅基地

文章浏览阅读301次。html5中的存储系统包括了两种存储方式:sessionStorage和localStorage。两种存储系统的操作方法相同,他们之间的区别在于:sessionStorage存储系统存储数据的特点 1. 当浏览器窗口关闭时,数据全部丢失 2.当再次打开浏览器窗口时,数据不能使用localStorage存储系统存储数据的特点 1.当浏览器窗_html实现信息存储系统

鸟哥的Linux私房菜_服务器架设篇 第三版-程序员宅基地

文章浏览阅读921次。鸟哥的Linux私房菜_服务器架设篇 第三版这些文件主要是针对在 Linux 上的网络服务器来书写架设方式的,鸟哥主要以使用 RPM/YUM 作为软件安装的 CentOS 为基础系统。CentOS 是属于 Red Hat Enterprise Linux (RHEL) 的操作系统,所以理论上 RHEL, CentOS, Fedora 等版本都适用的啦! 为什么要使用默认的软件管理方式来安装所有的服务器程序呢?这是因为大多数的 Linux 开发商都会有所谓的在线升级系统,包括 CentOS/Fedora 的

如何将NTFS For Mac手动激活-程序员宅基地

文章浏览阅读1.5k次。在线NTFS For Mac 激活过程中,如果在互联网或专门配置的防火墙出现问题,会提示你手动激活产品。如何手动激活呢?小编做了一个简单的教程。NTFS For Mac手动激活步骤:1. 如果在线激活出现问题,请单击“激活”产品。图一:激活2. 在打开的对话框中你可以看到输入序列号和产品密匙栏目。输入进去就可以了。图二:输入密匙3. 输入之后点击确定,会跳转页面如下图三:显示激活成功3.

机器学习-k近邻算法(kNN算法)及简单实现_k近邻算法的实现思路-程序员宅基地

文章浏览阅读930次,点赞2次,收藏9次。k-近邻(k-Nearest Neighbor,简称kNN)是一种常用的监督学习方法,其工作机制非常简单:给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个“邻居”的信息来进行预测,选择这k个样本中出现最多的类别标记作为预测结果。,其类型属于图书馆,而k-近邻算法不会,因为在它眼里,建筑类型只有食堂和教学楼,它会提取样本集中特征最相似数据(最邻近)的分类标签,得到的结果可能是食堂,也可能是教学楼,但绝不会是图书馆。开始,随着k的逐渐增大,k近邻算法的分类效果会逐渐提升;_k近邻算法的实现思路

推荐文章

热门文章

相关标签