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

目录
  • 题目：
  • 思路：
  • 代码：

题目：

假设图用邻接表表示，设计一个算法，输出从顶点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语言图遍历邻接表简单路径的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言数据结构与算法之图的遍历

    C语言数据结构与算法之图的遍历

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • C语言数据结构之图的遍历实例详解

    C语言数据结构之图的遍历实例详解 输入一组顶点,建立无向图的邻接矩阵.输入一组顶点,建立有向图的邻接表.分别对无向图和有向图进行DFS(深度优先遍历)和BFS(广度优先遍历).写出深度优先遍历的递归和非递归算法.根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列. 实现代码: #include <stdio.h> #include <stdlib.h> #define MAX 20 typedef struct ArcNode{ int adjvex; st

  • C语言实现图的遍历之深度优先搜索实例

    DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法.分享给大家供大家参考.具体方法如下: #include <iostream> #include <algorithm> #include <iterator> using namespace std; #define MAX_VERTEX_NUM 10 struct Node { int adjvex; struct Node *next; int info; }; typ

  • C语言数据结构与算法之图的遍历(二)

    C语言数据结构与算法之图的遍历(二)

    目录 前言  广度优先搜索过程 主要思想  代码实现   前言  在上一章的内容中我们使用了深度优先搜索来进行遍历,这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下: 广度优先搜索过程 使用广度优先搜索来遍历这个图的过程如下. 首先以一个未被访问过的顶点作为起始顶点,比如以1号点作为起始顶点. 将1号点放到队列中,然后将与1号点相邻的未访问过的顶点 即 2,3,5号顶点依次放入队列中,如下图: 接下来将2号顶点相邻的未访问过的顶点4号放入到队列中.到此所有的顶点都访问过了,遍历

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

    目录 题目: 思路: 代码: 题目: 假设图用邻接表表示,设计一个算法,输出从顶点Vi到Vj的所有简单路径 关键字: 图,邻接表,简单路径 思路: Vi=u,Vj=v 本题采用基于递归的深度优先遍历算法,从结点u出发,递归深度优先遍历图中各个结点,若访问到结点v,则输出该搜索路径上的结点. 为此,设置:一个path数组来存放路径上的结点(初始为空),d表示路径长度(初始为-1). 查找从顶点u到v 的简单路径过程说明如下 (假设查找函数名为FindPath()): 1)FindPath(G,u,

  • C语言数据结构与算法之图的遍历(一)

    C语言数据结构与算法之图的遍历(一)

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • Python算法之图的遍历

    Python算法之图的遍历

    本节主要介绍图的遍历算法BFS和DFS,以及寻找图的(强)连通分量的算法 Traversal就是遍历,主要是对图的遍历,也就是遍历图中的每个节点.对一个节点的遍历有两个阶段,首先是发现(discover),然后是访问(visit).遍历的重要性自然不必说,图中有几个算法和遍历没有关系?! [算法导论对于发现和访问区别的非常明显,对图的算法讲解地特别好,在遍历节点的时候给节点标注它的发现节点时间d[v]和结束访问时间f[v],然后由这些时间的一些规律得到了不少实用的定理,本节后面介绍了部分内容,感

  • C语言算法积累分离数位示例

    题目:输出一个三位整数的个.十.百位数. 关键字:得到数位 思路: Q:如何利用简单的基本运算来得到一个数字的各个数位上的数字? A:利用除法和求余运算:以153为例 首先,百位最容易得到:153/100=1.任何三位数除以100都是得到其百位的数字 其次,个位也好弄:153%10=3.任何三位数对10取余都是其个位数. 最后,十位数有四个方法. 最好想的: 1.用(原三位数—百位数* 100—个位数 * 1)/10 153-1X100-1X3=50; 50/10=5 2.将原三位数对100取余

  • C++实现图的遍历算法(DFS,BFS)的示例代码

    C++实现图的遍历算法(DFS,BFS)的示例代码

    目录 图的定义 图的相关术语 图的创建(邻接矩阵)---结构体 图的创建(邻接矩阵)---邻接矩阵的创建 图的创建(邻接表)---结构体 图的创建(邻接表)---邻接表的创建 对邻接矩阵进行深度优先遍历 对邻接矩阵进行广度优先遍历 对邻接表进行深度优先遍历 对邻接表进行广度优先遍历 整体代码 结果展示 图的定义 图由顶点集V(G)和边集E(G)组成,记为G=(V,E).其中E(G)是边的有限集合,边是顶点的无序对(无向图)或有序对(有向图).对于有向图来说,E(G)是有向边(也称弧(Arc))的

  • java实现图的邻接表存储结构的两种方式及实例应用详解

    java实现图的邻接表存储结构的两种方式及实例应用详解

    前言 本篇来谈一谈图的邻接表实现的两种方式,首先我们明确一点"学会图的邻接表实现的关键点在于":你所建立的图的邻接表的对象是什么! 首先我们看一下<算法导论>中关于图的邻接表的定义: 图G=(V,E)的邻接表表示有一个包含 |V| 个列表的数组Adj所组成,其中每个列表对应于V中的一个顶点,对于每一个u∈V,邻接表Adj[u]包含所有满足条件(u,v)∈E的顶点v,亦即,Adj[u]包含图G中所有和顶点u相邻的顶点.(或者他也可能指向这些顶点的指针),每个邻接表中的顶点一般

随机推荐