当前位置: 代码迷 >> 综合 >> 1,clone-graph java leetcode
  详细解决方案

1,clone-graph java leetcode

热度:67   发布时间:2023-09-30 06:32:09.0

题目描述
本题要求复制一个无向图,图中每个节点都包含一个标签和它的邻居列表
我们无向图用以下的方法序列化:
节点的标签是互不相同的,
我们使用“#”作为节点之间的分隔符,使用“,”作为节点标签和节点的节点邻居的分隔符。
例如:现在有一个序列化的无向图{0,1,2#1,2#2,2}.
这个无向图一共有3个节点,因此序列被#分隔成三部分
第一个节点的标签是0,节点0和节点1,节点2之间有边
第二个节点的标签是1,节点1和节点2之间有边
第三个节点的标签是2,节点2和节点2(它自己)之间有边,形成了自环

import java.util.ArrayList;public class UndirectedGraphNode {
    int label;ArrayList<UndirectedGraphNode> neighbors;UndirectedGraphNode(int x) {
    label = x; neighbors = new ArrayList<UndirectedGraphNode>();}
}

分割------------------------------

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;public class demo12 {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) {
    return null;}// 建立辅助队列LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();// 建立map,跟踪已经访问的节点Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();// 节点入队queue.offer(node);// 复制节点-只复制了label域,neighbors域是引用对象,直接复制无意义UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);// 节点进入代表已经访问的mapmap.put(node, newNode);// 中断条件:队列为空while(!queue.isEmpty()) {
    // 出队UndirectedGraphNode temp = queue.poll();// 获取邻居,遍历邻居ArrayList<UndirectedGraphNode> neighbors = temp.neighbors;for(UndirectedGraphNode neighbor : neighbors) {
    // 声明当前邻居节点 的 复制节点UndirectedGraphNode copy;// 若邻居未访问过if (!map.containsKey(neighbor)) {
    // 该邻居节点入队queue.offer(neighbor);// 复制该邻居节点copy = new UndirectedGraphNode(neighbor.label);// 将未访问邻居记录进mapmap.put(neighbor, copy);} else {
    // 邻居节点 之前被访问过// 获取邻居节点的复制节点copy = map.get(neighbor);}// 无论当前邻居节点 是否被访问过// 它的复制节点 都应该跟 复制的根节点建立 邻居关系map.get(temp).neighbors.add(copy);}}// 返回 复制的图return newNode;}}
  相关解决方案