对图的广度优先遍历BFS和深度优先遍历DFS的应用——基于LeetCode133 克隆图
对于图的广度优先遍历的基本形式
这个基本大家都是了解的,基于队列,每一次出队列一个节点,把相关的没有进入队列的节点加入队列,循环执行操作即可实现对图的BFS了。但是如果BFS+其他知识点,可能就有些令人不好下手了。比如说这道克隆的题目(虽然python3 里面已经提供了真·深拷贝,节省了不少功夫,不过我们为了锻炼code能力,还是自己做一下比较好),对我个人来说,就加深了我对于内存空间和map的理解和熟练掌握的程度。
对于图的深度优先遍历DFS的基本形式
相较于BFS,DFS就更加的多样一些了,主要是实现形式的多样化,我们可以利用递归的方法来实现我们的目标(这个也是大多数DFS问题的解决方式),不过如果我们有特殊需求,不想系统给我们压栈的话,我们也可以自己搞一个栈出来,一样可以做到,不过这道题也没有什么要求,我图一个省事,就用的递归的形式来做,如果之后有需要自己设置堆栈的题目,我会特别单写一个博客的。
题目内容
给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。
class Node {
public int val;
public List neighbors;
}
测试用例格式:
简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/clone-graph
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
测试样例
输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。
————————————————————————————
输入:adjList = [[]]
输出:[[]]
解释:输入包含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何邻居。
————————————————————————————
输入:adjList = []
输出:[]
解释:这个图是空的,它不含任何节点。
————————————————————————————
输入:adjList = [[2],[1]]
输出:[[2],[1]]
解题思路
这道题要做的其实还是很明确的,就是要我们遍历一遍这个图,然后把每一个点的内容都去copy一份,这里我使用的还是比较习惯用的BFS,但是在执行的过程中遇到了一些问题。
代码的目的是比较清楚的,一个队列用来实现BFS,一个map是为了防止图中的环的情况导致一些节点一直被copy陷入循环。对于初始情况完成了入队列和新旧节点的设置之后,开始进入BFS的循环,其中只要是遇到了新的节点,就是生成新的,进入map,同时节点进队列,继续BFS。
但是我遇到的一个主要的问题在于我希望可以所有地方都是用new NODE来生成新的,不过现在想一下,这样一来1-3边和2-3边同样是3号节点就会有多个不同的节点地址了,的确是有问题的。
在使用BFS完成之后,我们可以再延伸一下,使用相对我不是那么熟练的DFS来完成一下,DFS的话相较于BFS,可以理解为一条路走到死之后才考虑回头,这样的方式的话,递归自然是最好的选择了,我们可以设定这个结点已经copy过,或者是走到头了,这个点没有neighbor了作为终点,而在补充邻居那里使用的就是邻居的clone函数,就可以实现递归了,虽然遍历图的手段不同,但是copy和map的核心内容还是一样的。
BFS具体代码
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* cloneGraph(Node* node) {
if(node==NULL){
return node;
}
queue<Node*> link;
map<Node*,Node*> jihe;
link.push(node);
jihe.insert(pair<Node*,Node*>(node,new Node(node->val)));
while(!link.empty()){
Node* biao=link.front();
link.pop();
for(vector<Node*> ::iterator it=biao->neighbors.begin();it!=biao->neighbors.end();it++){
if(jihe.find(*it)==jihe.end()){
// jihe[*it]=new Node(*it->val);
jihe.insert(pair<Node*,Node*>(*it,new Node((*it)->val)));
// jihe[biao]->neighbors.push_back(new Node((*it)->val));
link.push(*it);
}
// jihe[biao]->neighbors.push_back(new Node((*it)->val));
jihe[biao]->neighbors.push_back(jihe[*it]);
}
}
return jihe[node];
}
};
DFS的具体代码(看起来短一些,毕竟递归嘛)
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
map<Node*,Node*> jihe;
Node* cloneGraph(Node* node) {
if(node==NULL){
return node;
}
if(jihe.find(node)!=jihe.end()){
return jihe[node];
}
jihe.insert(pair<Node*,Node*>(node,new Node(node->val)));
for(vector<Node*>:: iterator it=node->neighbors.begin();it!=node->neighbors.end();it++){
jihe[node]->neighbors.push_back(cloneGraph(*it));
}
return jihe[node];
}
};
相关文章
- R3下,遍历所有进程的伪句柄表,关闭指定句柄
- C#保留2位小数几种场景总结 游标遍历所有数据库循环执行修改数据库的sql命令 原生js轮盘抽奖实例分析(幸运大转盘抽奖) javascript中的typeof和类型判断
- 图的宽度优先遍历:BFS遍历
- JS遍历循环渲染数据(模板字符串的应用)
- rails应用遍历Controllers目录并取出所有的Controller和action
- 遍历Opencv中Mat中每个像素的值
- 【漏洞通告】Spring-cloud-config-server路径遍历漏洞(CVE-2020-5405)通告
- 二叉树的层序遍历-Python
- 剑指offer编程题解法汇总23-二叉搜索树的后序遍历序列
- 浅析深度优先和广度优先遍历实现过程、区别及使用场景
- 35、【栈和队列】二叉树的中序遍历(C++版)
- delphi如何按照控件的左右顺序来遍历窗体中的每个控件 [问题点数:20 http://bbs.csdn.net/topics/380216822
- cocos2d-x 3.0 android mk文件 之 自己主动遍历*.cpp文件
- JS怎样遍历对象
- [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历