图是一种比较重要的数据结构,无论多复杂的图都是由顶点和边构成的,图有两种常用的存储结构为邻接矩阵和邻接表。本篇博客将使用邻接表存储图,邻接表是一种顺序分配和链式分配相结合的存储方式。邻接表是表示图的标准方法,尤其对于稀疏图节省很多存储空间,空间复杂度是O(|E|+|V|). 对于每个顶点,使用一个表存放所有邻接的顶点。
我们要操作的有向图如下:
通过图我们可以轻松画出此有向图的邻接表
下面我们通过代码来实现图的邻接表存储结构。
邻接表存储
定义所需的结构体:
//定义邻接表结点的结构 struct node { int data;//结点名 int weight;//权值 node * next;//下一个结点的指针 node() { next=NULL; } }; //定义邻接表的表头 struct Head { int data;//结点名 node * first;//执行第一个结点 Head() { first=NULL; } };
定义一个宏表示图的总结点数:
#define MAXSIZE 5 //定义图的结点数
定义表头指针数组
Head * head[MAXSIZE];//表头指针数组
有了上面的准备我们可以开始书写存储邻接表的函数了
具体代码如下:
//建立邻接表 void Create(Head * & head) { while(true) { int name,wg; cin>>name;//输入结点 if(name==-1)//输入-1表示链表结束 break; cin>>wg;//输入权值 node * temp=new node;//定义表结点 temp->data=name; temp->weight=wg; //把表结点插入到head后面 if(head->first==NULL) head->first=temp; else { temp->next=head->first; head->first=temp; } } }
到此我们就可以通过输入把图的信息存储到邻接表里,我们已经把图数据化了,下面就可以对图进行遍历了
首先我们要明白图的遍历的定义。
从给定图中任意指定的顶点(称为起始点)出发,按照某种搜索方式沿着图的边访问图中所有的顶点,使每一个顶点仅被访问一次,这个过程就是图的遍历
深度优先搜索算法
深度优先搜索算法的过程是:从图中某一个初始顶点v出发,首先访问初始顶点v,然后选择一个与顶点v相邻且没被访问过的顶点w为起始顶点,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。这里面涉及到回溯。
根据此方法的过程,可以写出其代码
//递归深度优先搜索 void DFS_DG(Head *head[],int v,int visited[])//head[]-头指针数组,v-起始顶点,visited[]--标记数组 { node * p;//表结点 visited[v]=1; cout<<v; p=head[v]->first;//获取第一个表结点 while(p!=NULL) { if(visited[p->data]==0)//还没访问 DFS_DG(head,p->data,visited); p=p->next; } }
广度优先搜索算法
广度优先算法里面我们使用到队列,首先学习下队列。
队列
队列也是一种运算受限的线性表。在这种线性表上,插入限定在表的某一端进行,删除限定在表的另一端进行。允许插入的一端称为队尾(Rear),允许删除的一端称为队头(Front)。
特点:队列中数据元素的入队和出队过程是按照“先进先出”的原则进行的。因此,队列又称为“先进先出”的线性表,简称FIFO表。
这里我们使用顺序队列,为了充分的使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表。下面我们将来介绍顺序队列
队空的条件
rear==front
队满的条件
(rear+1)%MAXSIZE==front//MAXSIZE队的容量
初始化队列很简单:
int queue[MAXSIZE],front=0,rear=0;//顺序队列,front是头,rear是尾,队列是插尾删头,先进先出
在队列不满的时候入队:
if((rear+1)%MAXSIZE==front)//即队满了 return; //入队 rear=(rear+1)%MAXSIZE; queue[rear]=data;
在队不为空的时候出队
if(rear==front)//空队 return; //入队 front=(front+1)%MAXSIZE; data=queue[front];
有了上面的队列知识,我们可以开始学习广度优先搜索了。
广度优先搜索算法过程是:广度优先搜索是从图的某个顶点v0出发,在访问v0之后,依次搜索访问v0的各个未被访问过的邻接点w1,w2,…。然后顺序搜索访问w1的各未被访问过的邻接点,w2的各未被访问过的邻接点,…。以此类推,直到图中所有和初始点v有路径想通的顶点都被访问完为止。
其代码为:
//广度优先搜索遍历--使用队列 void BFS(Head *head[],int v) { node *p;//表结点指针 int queue[MAXSIZE],front=0,rear=0;//顺序队列,front是头,rear是尾,队列是插尾删头,先进先出 int visited[MAXSIZE]={0};//访问标志数组初始化为0 //开始访问 cout<<v; visited[v]=1; rear=(rear+1)%MAXSIZE; queue[rear]=v;//入队 int ok; while(front!=rear)//队列不为空 { front=(front+1)%MAXSIZE; ok=queue[front];//出队 p=head[ok]->first;//获取第一个表结点 while(p!=NULL)//循环遍历其表结点 { if(visited[p->data]==0)//该表结点没有访问过 { cout<<p->data; visited[p->data]=1; rear=(rear+1)%MAXSIZE; queue[rear]=p->data;//入队 } p=p->next;//找下一个结点 } } }
附上源码地址:https://github.com/longpo/algorithm/tree/master/Graph
相关推荐
本文通篇围绕遍历列表这一主题,系统而详尽地介绍了相关的数据结构知识、遍历算法思想、代码实现方法以及应用场景分析。全面阐述了列表这种数据结构的特点,以及使用循环和迭代器遍历列表的两种方式,并分析了算法时间...
广度优先遍历图算法解释。。。 烦死了,要写这么多
本文实例讲述了JavaScript数据结构与算法之二叉树遍历算法。分享给大家供大家参考,具体如下: javascript数据结构与算法–二叉树遍历(先序) 先序遍历先访问根节点, 然后以同样方式访问左子树和右子树 代码如下...
主要介绍了二叉树的非递归后序遍历算法实例,需要的朋友可以参考下
关于C语言的算法时候可能用到的图的深度优先遍历算法动画详解
上图就是典型的二叉树,其中左边的图还叫做满二叉树,右边是完全二叉树。然后我们可以得出结论,满二叉树一定是完全二叉树,但是反过来就不一定。满二叉树的定义是除了叶子结点,其它结点左右孩子都有,深度为k的满...
用Python实现树的构造和几种遍历算法,虽然不难,不过还是把代码作了一下整理总结。实现功能: ① 树的构造 ② 递归实现先序遍历、中序遍历、后序遍历 ③ 堆栈实现先序遍历、中序遍历、后序遍历 ④ 队列实现层次遍历...
本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法。分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历 采用队列的遍历操作第一次访问根,在...
本文实例讲述了Python3字典遍历操作。分享给大家供大家参考,具体如下: 字典是针对非序列集合而提供的一种数据类型。 通过任意键查找集合中值信息的过程叫映射,python通过字典实现映射。 为字典赋值: >>> d={'...
DFS(深度优先搜索)和BFS(广度优先搜索)是两种用于遍历或搜索树或图的算法。它们的主要区别在于访问节点的顺序。 1. **深度优先搜索(DFS)** 深度优先搜索是一种用于遍历或搜索树或图的算法。这个算法会尽可能...
今天我就在B站看了数据结构中关于树的内容后,又用我浅薄的Python大法来实现一些树的建立和遍历。 关于树的建立我觉得层序建立对于使用者来说最为直观,输入很好写。(好吧,我是看LeetCode中的树输入都是采用层序...
在C语言程序中可能用到的算法,关于图的广度优先遍历的动画详解
冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就交换位置。这个过程持续对数列的末尾进行,直到整个数列都排序完成。 冒泡排序的时间复杂度为O(n^2),这使得它在...
数据结构与算法(Python) 一、引入概念 1-01算法引入 1-02 时间复杂度与大O表示法 1-03-最坏时间复杂度与计算规则 1-04-常见时间复杂度与大小关系 1-05-代码执行时间测量模块 1-06-Python列表类型不同操作的...
* 似的,也可以用bfs来按照起点的距离顺序遍历迷宫图。不断沿着父亲指针走, * 保存方向序列dir,最后反向输出。 * 比深度优化的效率要高很多,因为每次都定义了活结点还有下一个扩展节点, * 在活结点当中去寻找...
本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个...
使用一个二维数组来存储每个子问题的解,并使用两个嵌套循环来遍历所有可能的物品和容量组合,并计算出最优解。 单词拆分问题 可以将此问题简化为背包问题,单词就是物品,字符串s就是背包,单词能否组成字符串s,...