图的深度遍历和广度遍历

简介: 图的深度遍历和广度遍历

实事上,这些遍历问题只是老生常谈的bfs和dfs过程,学习图的时候前面的图的定义和存储都没有讲解,但定义那些初试就学过,这里更注重讲解图的存储,再顺带把其遍历解决。

图的存储有邻接矩阵和邻接表这几种方式,邻接矩阵是个二维数组,邻接表是一个点集加链表的形式,这里我们想用vector来实现邻接表。

为什么vector可以实现邻接表,注意邻接表是点集加链表,为什么加链表是因为链表长度不一定需要确定,恰好vector也是一个可变数组,所以可以定义node后,用vector<node>Adj[N]实现邻接表。特别当题目不涉及权重,只管连通信息时,直接用vector<int>Adj[N]即可模拟邻接表

之后就是基于邻接表的两种遍历

#include<iostream> 
#include<vector>
#include<queue>
using namespace std;
struct node{
  int vex;
  int weight; 
};
vector <node>Adj[1000];//定义邻接表
int n;//结点数 
bool vis[1000];
void dfs(int u) {
    vis[u]=true;
    printf("%d",u);
    for(int i=0;i<Adj[u].size();i++)
{   
    int k=Adj[u][i].vex;
  if(!vis[k])
  dfs(k);
}
} 
void dfstrave() //深度遍历图G
 {
  for(int i=1;i<=n;i++) 
      vis[i]=false;
    for(int i=1;i<=n;i++){
      if(!vis[i])
      dfs(i);
  }
 } 
 void bfs(int u) {
  queue<int>q;
  q.push(u);
  int temp;
  while(!q.empty()){
    temp=q.front();q.pop();
    vis[temp]=true;
    printf("%d",temp);
    for(int i=0;i<Adj[temp].size();i++){
      int k=Adj[u][i].vex;
        if(!vis[k])
           q.push(k);
     }
   }
 }
 void bfstrave() //广度遍历图G
 {
  for(int i=1;i<=n;i++) 
      vis[i]=false;
    for(int i=1;i<=n;i++){
      if(!vis[i])
      dfs(i);
  }
 } 
 int main(){
  return 0;
 }

如果要解决连通分量个数问题在遍历是加入一个数据看调用了几次bfs或dfs即可。

目录
打赏
0
0
0
0
1
分享
相关文章
图与树的遍历:探索广度优先、深度优先及其他遍历算法的原理与实现
图与树的遍历:探索广度优先、深度优先及其他遍历算法的原理与实现
525 0
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
60 4
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
49 0
数据结构实验之图论二:图的深度遍历
数据结构实验之图论二:图的深度遍历
用递归的思想实现二叉树前、中、后序迭代遍历
用递归的思想实现二叉树前、中、后序迭代遍历
96 1
深度优先遍历与广度优先遍历:理解它们的原理与差异
深度优先遍历与广度优先遍历:理解它们的原理与差异
|
9月前
|
邻接矩阵表示 深度遍历 广度遍历
邻接矩阵表示 深度遍历 广度遍历
43 0
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
66 0
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(下
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
102 0
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(上)
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
135 0