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

目录
  • 引入 
  • 深度优先搜索
    • 代码实现 
    • 完整代码  

引入 

在数据结构中常见的有深度优先搜索和广度优先搜索。为什么叫深度和广度呢？其实是针对图的遍历而言的，请看下面这个图：

图是由一些小圆点（称为顶点） 和 连接这些点的直线 （称为边）组成的。

例如上图就是由5个顶点（编号为 1,2,3,4,5） 和5条边（1-2,1-3,1-4,2-4）组成。

现在我们从1号顶点开始遍历这个图，遍历就是把图的每一个顶点都访问一次。使用深度优先搜索将会得到如下的结果。

图中每个顶点旁边的数表示这个顶点是第几个被访问到的，我们称之为 —— 时间戳 

深度优先搜索

使用深度优先搜索来遍历这个图的过程：

首先从一个未走过的顶点作为起始顶点，比如以1号顶点作为起点。沿1号顶点的边去尝试其他它未走过的顶点，首先发现的是2号顶点还没被走过，于是来到了2号顶点。

再以2号顶点作为出发点继续尝试访问其他未走到过的顶点，这样又来到了4号顶点。

再以4号顶点作为出发点继续尝试访问其他未走过的顶点。但是，此时在4号顶点的周围已经没有其他的顶点了，所以需要返回到2号顶点。返回到2号顶点后，发现沿2号顶点也不能在访问到其他未走到的点了，此时又需要返回到1号顶点。

继续以1号顶点尝试访问其他顶点，我们来到了3号点。以此类推，我们最后来到了5号点。到此，所以的顶点都走过了，遍历结束

深度优先搜索的主要思想是：

首先以一个未被访问的顶点作为起始顶点，沿当前顶点的边走到未被访问过的顶点

当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问过。

显然，深度优先搜索是沿着图的某一条分支遍历直至末端，然后回溯，再沿另一条实现相同的遍历，直到所以的顶点都被访问完为止。

代码实现 

上面的二维数组中 第i行第j列就是表示顶点i到顶点j是否有边。

1表示有边，x表示没有边，0表示顶点自己到自己。

我们将这种方法称为 ——  图的邻接矩阵储存法。 

细心的朋友可能会发现这张图沿着对角线全部是0，因为上面这张图是 无向图。 

所谓无向图就是指图的边没有方向。例如边 1 - 5 表示 1号顶点可以到 5号顶点，5号顶点也可以到1号顶点。

接下来就是解决怎么用深度优先搜索来实现遍历了：

void dfs(int cur)				//cur是当前所在的顶点编号
{
	printf("%d", cur);
	sum++;						//每访问一个点就sum++
	if (sum == n) return;		//所有的顶点都访问过了
	for (i = 1; i <= n; i++)	//从1到n的顶点依次尝试，看看有哪些顶点与当前顶点cur有边相连
	{
		//判断当前顶点cur到顶点i是否有边，并判断顶点i是否已被访问过
		{
			if (e[cur][i] == 1 && book[i] == 0)
			{
				book[i] = 1;	//标记顶点i已经访问过
				dfs(i);			//从顶点i出发继续遍历
			}
		}
	}
	return;
}

在上面的代码中 变量 cur 存储的是当前正在遍历的点，二维数组e存储的就是图的边（邻接矩阵），数组book用来标记哪些顶点已经访问过，变量sum用来记录已经访问多少个顶点，变量你存储的是图的顶点总个数。

完整代码  

#include <stdio.h>
int book[101], sum, n, e[101][101];
void dfs(int cur)				//cur是当前所在的顶点编号
{
	printf("%d", cur);
	sum++;						//每访问一个点就sum++
	if (sum == n) return;		//所有的顶点都访问过了
	for (i = 1; i <= n; i++)	//从1到n的顶点依次尝试，看看有哪些顶点与当前顶点cur有边相连
	{
		//判断当前顶点cur到顶点i是否有边，并判断顶点i是否已被访问过
		{
			if (e[cur][i] == 1 && book[i] == 0)
			{
				book[i] = 1;	//标记顶点i已经访问过
				dfs(i);			//从顶点i出发继续遍历
			}
		}
	}
	return;
}

int main()
{
	int i, j, m, a, b;
	scanf("%d %d", &n, &m);
	//初始化二维矩阵
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i == j) e[i][j] = 0;
			else e[i][j] = 99999999;	//我们假设99999999为x

	//读入顶点之间的边
	for (i = 1; i <= n; i++)
	{
		scanf("%d %d", &a, &b);
		e[a][b] = 1;
		e[b][a] = 1;	//因为该图为无向图
	}

	//从1号顶点出发
	book[1] = 1;  //标记1号顶点已经访问
	dfs(1);		  //从1号顶点开始遍历

	return 0;
}

到此这篇关于C语言数据结构与算法之图的遍历(一)的文章就介绍到这了,更多相关C语言数据结构 图的遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言数据结构树之后序遍历的实现

    C语言数据结构树之后序遍历的实现

    后续遍历的实现: 数据结构树中的后续遍历,这里提供简单实例,代码中有注释,大家参考下! 看下实现效果: 题目及分析 给定树的先序遍历和中序遍历,求后续遍历 输入 abdec dbeac 输出 debca 三.实现代码: #include <iostream> #include <string> using namespace std; string s1="abdec";//先序遍历 string s2="dbeac";//中序遍历 void

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

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

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

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

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

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

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

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

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

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

  • C语言数据结构与算法之排序总结(二)

    C语言数据结构与算法之排序总结(二)

    目录 一.前言 二.选择类排序 1.简单选择排序 2.树形选择排序 3.堆选择排序 三.归并排序 四.分配类排序 1.多关键字排序 2.链式基数排序 五.总结归纳 一.前言 之前的排序总结(一)对插入类和交换类排序作了比较详细的总结,对于直接插入.希尔排序.冒泡排序.快速排序要求熟练掌握 这篇排序全面总结(二)主要介绍选择类排序中的简单.树形和堆排序,归并排序.分配类排序的基数排序 二.选择类排序 选择类:每次从待排序的无序序列中,选择一个最大或最小的数字,放到前面,数据元素为空时排序结束 1.

  • C语言数据结构与算法之排序总结(一)

    C语言数据结构与算法之排序总结(一)

    目录 一.前言 二.基本概念 1.排序 2.排序方法的稳定性 3.内部和外部排序 三.插入类排序 1.直接插入排序 2.折半插入排序 3.希尔排序 四.交换类排序 1.冒泡排序 2.快速排序 五.总结比较 一.前言 学习目标: 排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确 理解各种排序算法的定义和特点,并能将代码灵活运用 掌握各种排序方法时间复杂度与空间复杂度 理解排序稳定和不稳定的概念                 重点和难点: 希尔.快速.堆.归并排序这几种快

  • Python数据结构与算法之图结构（Graph）实例分析

    Python数据结构与算法之图结构（Graph）实例分析

    本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简

  • Python数据结构与算法之图的基本实现及迭代器实例详解

    Python数据结构与算法之图的基本实现及迭代器实例详解

    本文实例讲述了Python数据结构与算法之图的基本实现及迭代器.分享给大家供大家参考,具体如下: 这篇文章参考自<复杂性思考>一书的第二章,并给出这一章节里我的习题解答. (这书不到120页纸,要卖50块!!,一开始以为很厚的样子,拿回来一看,尼玛.....代码很少,给点提示,然后让读者自己思考怎么实现) 先定义顶点和边 class Vertex(object): def __init__(self, label=''): self.label = label def __repr__(sel

  • Python数据结构与算法之图的广度优先与深度优先搜索算法示例

    本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法.分享给大家供大家参考,具体如下: 根据维基百科的伪代码实现: 广度优先BFS: 使用队列,集合 标记初始结点已被发现,放入队列 每次循环从队列弹出一个结点 将该节点的所有相连结点放入队列,并标记已被发现 通过队列,将迷宫路口所有的门打开,从一个门进去继续打开里面的门,然后返回前一个门处 """ procedure BFS(G,v) is let Q be a queue Q.enqueue(v) lab

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • C语言数据结构与算法之链表(二)

    C语言数据结构与算法之链表(二)

    目录 引入 模拟链表介绍 插入代码实现 代码实现   引入 在上一节的学习中我们介绍了C语言如何实现链表,但是,在这一章,我们将抛开令人头秃的指针和结构体,我们将另外使用一种数组来实现的方式,叫做模拟链表.让我们一起来看看. 模拟链表介绍 链表中的每一个结点都只有两个部分. 我们可以使用一个数组date来储存每序列中的每一个数.那每一个数右边的数是谁,这一点该如何解决呢?在上一章的内容中我们是使用指针来解决的,这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了.具体要怎么

随机推荐