Leetcode 图 133. 克隆图

女爷i 2023-02-09 05:26 1阅读 0赞

### Leetcode 133. 克隆图 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

题目链接： [https://leetcode-cn.com/problems/clone-graph/][https_leetcode-cn.com_problems_clone-graph]  
  本质上就是一个图的遍历问题，首先用一个`hashmap`存储节点的值和节点本身的对应关系（根据源节点创建），然后仍然根据源节点，将之前 `hashmap` 中没有赋值的`neighbors`给赋值。最后输出第一个节点即可。读者可以直接看源代码。我基本每一个重要步骤都注释了。

# 2、问题解决 #

笔者以C++方式解决。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "map"
    
    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 { 
    private:
    	// 定义顶点数目
    	static const int MAXV = 101;
    	// 用于复制节点时 标记是否访问
    	bool vis[MAXV] = {  false };
    	// 用于给neighbors赋值时， 标记是否访问
    	bool vis1[MAXV] = {  false };
    	// 将节点的值和节点对应
    	map<int, Node *> val_map;
    public:
    	Node *cloneGraph(Node *node) { 
    		if (node == NULL) { 
    			return NULL;
    		}
    		dfs_create_node(node);
    		dfs(node);
    		return val_map[1];
    	}
    
    	/** * 根据 node 创建节点，并对应到map中 * 本质就是图的遍历 * @param node */
    	void dfs_create_node(Node *node) { 
    		// 标记该节点已经访问
    		vis[node->val] = true;
    		// 根据源节点生成新节点（先赋值，不更新 neighbors ，
    		// 即 neighbors 暂时为空，因为此时的 neighbors 节点可能还没有new 出来）
    		val_map[node->val] = new Node(node->val);
    		// 根据邻接表对图进行深搜
    		for (int i = 0; i < node->neighbors.size(); ++i) { 
    			// 获取下一个访问节点的值
    			int v = node->neighbors[i]->val;
    			// 如果之前没有访问过该节点
    			if (!vis[v]) { 
    				// 根据 node->neighbors[i]) 创建节点，并对应到map中
    				dfs_create_node(node->neighbors[i]);
    			}
    		}
    	}
    
    	/** * 根据源节点 给 map 中的 neighbors 赋值 * @param node */
    	void dfs(Node *node) { 
    		//标记该节点已经访问
    		vis1[node->val] = true;
    
    		// 取出map 中的节点，根据 源节点 node 的值标记 该节点的邻接表 即 neighbors ，
    		// 注意这里的 neighbors 存储的仍然是 map 中的节点
    		for (int i = 0; i < node->neighbors.size(); ++i) { 
    			val_map[node->val]->neighbors.push_back(val_map[node->neighbors[i]->val]);
    		}
    
    
    		// 和上面一样深搜
    		for (int i = 0; i < node->neighbors.size(); ++i) { 
    			int v = node->neighbors[i]->val;
    			if (!vis1[v]) { 
    				dfs(node->neighbors[i]);
    			}
    		}
    	}
    };
    
    
    int main() { 
    	// 创建节点
    	Node *pNode1 = new Node(1);
    	Node *pNode2 = new Node(2);
    	Node *pNode3 = new Node(3);
    	Node *pNode4 = new Node(4);
    
    	// 给节点建立邻接表
    	pNode1->neighbors.push_back(pNode2);
    	pNode1->neighbors.push_back(pNode4);
    
    	pNode2->neighbors.push_back(pNode1);
    	pNode2->neighbors.push_back(pNode3);
    
    	pNode3->neighbors.push_back(pNode2);
    	pNode3->neighbors.push_back(pNode4);
    
    	pNode4->neighbors.push_back(pNode1);
    	pNode4->neighbors.push_back(pNode3);
    
    	Solution *pSolution = new Solution;
    	Node *pNode = pSolution->cloneGraph(pNode1);
    	cout << pNode1 << endl;
    
    	system("pause");
    	return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]

有点菜，有时间再优化一下。

# 3、总结 #

书上的代码直接运行绝大部分是对的，但是总有一些软件的更新使得作者无能为力。之前的API是对的，但是之后就废弃了或修改了是常有的事。所以我们需要跟踪源代码。这只是一个小小的问题，如果没有前辈的无私奉献，很难想象我们自己一天能学到多少内容。感谢各位前辈的辛勤付出，让我们少走了很多的弯路！

点个赞再走呗！欢迎留言哦！

[https_leetcode-cn.com_problems_clone-graph]: https://leetcode-cn.com/problems/clone-graph/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200518135702141.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3,size_16,color_FFFFFF,t_70