返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言算法积累图的遍历邻接表简单路径
  • 512
分享到

C语言算法积累图的遍历邻接表简单路径

2024-04-02 19:04:59 512人浏览 泡泡鱼
摘要

目录题目:思路:代码:题目: 假设图用邻接表表示,设计一个算法,输出从顶点Vi到Vj的所有简单路径 关键字: 图,邻接表,简单路径 思路: Vi=u,Vj=v 本题采用基于递归的深度

题目

假设图用邻接表表示,设计一个算法,输出从顶点Vi到Vj的所有简单路径

关键字: 图,邻接表,简单路径

思路:

Vi=u,Vj=v

本题采用基于递归的深度优先遍历算法,从结点u出发,递归深度优先遍历图中各个结点,若访问到结点v,则输出该搜索路径上的结点。

为此,设置:一个path数组来存放路径上的结点(初始为空),d表示路径长度(初始为-1)。

查找从顶点u到v 的简单路径过程说明如下

(假设查找函数名为FindPath()):

1)FindPath(G,u,v,path,d):

d++;path[d]=u;

若找到u的未访问过的相邻结点u1,则继续下去,

否则置visited[u]=0并返回。

2)FindPath(G,u1,v,path,d):

d++;path[d]=u1;

若找到u1的未访问过的相邻结点u2,则继续下去,

否则置visited[u1]=0并返回。

3)以此类推,继续上述递归过程,直到ui=v,输出path

代码:

void FindPath (AGraph *G,int u,int v,int path[],int d){
      int w;//w是每一次遍历中,当前结点的下一个邻接顶点的代表变量
      Arcnode*p;
      d++;//路径长度增加1
      path[d]=u;//将当期顶点添加到路径中
      visited[u]=1;//设置已访问结点
      if(u==v)//找到一条路径则输出
           print(path[]);//输出路径上的结点
      p=G->adjlist[u].firstarc;//p指向u的第一个相邻点
      while(p!=NULL){     //遍历u的所有相邻点
        w=p->adjvex;//w为下一个邻接顶点
        if(visited[w]==0)//若顶点w未访问,递归访问它
           FindPath(G,w,V,path,d);
        p=p->nextarc;//p指向u的下一个相邻点
      }
      visited[u]=0;//恢复环境,使该顶点可重新使用
  }
        




以上就是C语言算法积累图的遍历邻接表简单路径的详细内容,更多关于C语言图遍历邻接表简单路径的资料请关注编程网其它相关文章!

--结束END--

本文标题: C语言算法积累图的遍历邻接表简单路径

本文链接: https://lsjlt.com/news/150673.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C语言算法积累图的遍历邻接表简单路径
    目录题目:思路:代码:题目: 假设图用邻接表表示,设计一个算法,输出从顶点Vi到Vj的所有简单路径 关键字: 图,邻接表,简单路径 思路: Vi=u,Vj=v 本题采用基于递归的深度...
    99+
    2024-04-02
  • C语言怎么遍历邻接表简单路径
    这篇“C语言怎么遍历邻接表简单路径”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C语言怎么遍历邻接表简单路径”文章吧。题目:...
    99+
    2023-07-01
  • C语言数据结构与算法图的遍历分析
    这篇文章主要介绍“C语言数据结构与算法图的遍历分析”,在日常操作中,相信很多人在C语言数据结构与算法图的遍历分析问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C语言数据结构与算法图的遍历分析”的疑惑有所帮助!...
    99+
    2023-06-22
  • C语言数据结构与算法之图的遍历(一)
    目录引入 深度优先搜索代码实现 完整代码  引入  在数据结构中常见的有深度优先搜索和广度优先搜索。为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆...
    99+
    2024-04-02
  • C语言数据结构与算法之图的遍历(二)
    目录前言 广度优先搜索过程主要思想 代码实现  前言  在上一章的内容中我们使用了深度优先搜索来进行遍历,这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下:...
    99+
    2024-04-02
  • C语言数据结构与算法中怎样完成图的遍历
    C语言数据结构与算法中怎样完成图的遍历,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。前言 我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下:广度...
    99+
    2023-06-22
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作