克隆有向图

问题描述

给定一个有向图的根节点，通过创建其深度拷贝来复制该图，使得克隆后的图与原图具有相同的顶点和边。

示例

我们来看下面的图作为示例。如果输入图是 $G = (V, E)$，其中 $V$ 是顶点集合，$E$ 是边集合，那么输出图（即克隆图）是 $G' = (V', E')$，满足 $V = V'$ 且 $E = E'$。

假设所有顶点都从根顶点可达，即图为连通图。

原始图：

克隆图：

示例输入

示例输入是一个图：

10 -> { 2  3  4 }
21 -> { 2 }
32 -> { 0 }
43 -> { 2 }
54 -> { 1  3  0 }

第一列是所有顶点。在上述示例中，顶点 $0$ 的邻居是 ${2, 3, 4}$。

预期输出

10 -> { 2  3  4 }
21 -> { 2 }
32 -> { 0 }
43 -> { 2 }
54 -> { 1  3  0 }

自行尝试

多标签代码

C++

1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include "DirectedGraph.cpp"
6
7using namespace std;
8
9DirectedGraph* Clone(DirectedGraph* graph) {
10	// 用于记录已访问节点的哈希表
11	unordered_map<Node*, Node*> nodes_completed;
12
13	// 创建新图
14	DirectedGraph* clone_graph = new DirectedGraph();
15
16	// TODO: 写入代码
17
18	// 返回深度拷贝的图
19	return clone_graph;
20}

Java

1// 导入所需函数
2import java.util.*;
3
4class ClonedGraph<X> {
5	public DirectedGraph<X> clone(DirectedGraph<X> graph) {
6		// 用于记录已访问节点的哈希表
7		HashMap<Node<X>, Node<X>> nodesCompleted =
8				new HashMap<Node<X>, Node<X>>();
9
10		// 创建新图
11		DirectedGraph<X> cloneGraph = new DirectedGraph<X>();
12
13		// TODO: 写入代码
14
15		// 返回深度拷贝的图
16		return cloneGraph;
17	}
18}

Python

1from directed_graph import *
2
3def clone(graph):
4  # 用于记录已访问节点的字典
5  nodes_completed = {}
6  # 创建新图
7  clone_graph = DirectedGraph()
8
9  # TODO: 写入代码
10  
11  # 返回深度拷贝的图
12  return clone_graph

JS

1import {  DirectedGraph } from './DirectedGraph.js';
2import {Node} from "./Node.js";
3
4let clone = function(graph) {
5   
6    // 用于记录已访问节点的哈希表  
7    var nodesCompleted = {};
8    
9    // 创建新图
10    var cloneGraph = new DirectedGraph();
11
12    
13    if(graph.nodes.length == 0){
14        return null;
15    } else {
16       
17       // TODO: 写入代码
18    }
19    
20    // 返回深度拷贝的图
21    return cloneGraph;
22};

Ruby

1require './directed_graph'
2
3def clone(graph)
4  # 用于记录已访问节点的哈希表
5  nodes_completed = {}
6  # 创建新图
7  clone_graph = DirectedGraph.new()
8
9  # TODO: 写入代码
10  
11  
12  # 返回深度拷贝的图
13  return clone_graph
14end

Go

1package main
2
3import (
4  "fmt"
5  "encoding/json"
6  "sort"
7)
8
9func Clone(graph *DirectedGraph) *DirectedGraph {
10  // 创建新图
11	cloneGraph := new(DirectedGraph)
12  
13  // TODO: 写入代码
14
15  // 返回深度拷贝的图
16	return cloneGraph
17}

解决方案

我们使用深度优先遍历，在遍历图的过程中为每个节点创建副本。为了避免陷入循环，我们使用哈希表记录已访问的节点，并不再重新访问已在哈希表中的节点。哈希表的键是原图中的节点，值是对应克隆图中的节点。

对于上述图，假设根节点是节点 $0$，因此我们将从 $0$ 开始。

多标签代码

C++

1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include "DirectedGraph.cpp"
6
7using namespace std;
8
9Node* CloneRec(
10	Node* root, DirectedGraph* graph,
11	unordered_map<Node*, Node*>& nodes_completed) {
12	// 基础情况：无节点时返回空
13	if (root == nullptr) {
14		return nullptr;
15	}
16
17	// 创建新顶点/节点
18	Node* p_new = new Node(root->data);
19
20	// 使用哈希表记录已访问节点
21	nodes_completed[root] = p_new;
22
23	// 将新节点加入图中
24	graph->AddVertexInNodes(p_new);
25
26	// 遍历当前节点的所有邻居
27	for (Node* p : root->neighbors) {
28		auto x = nodes_completed.find(p);
29		if (x == nodes_completed.end()) {
30			// 如果节点未被访问，递归调用以创建节点
31			p_new->neighbors.push_back(CloneRec(p, graph, nodes_completed));
32		} else {
33			// 如果节点已被访问，直接将其加入当前节点的邻居列表
34			p_new->neighbors.push_back(x->second /*值*/);
35		}
36	}
37
38	return p_new;
39}
40
41DirectedGraph* Clone(DirectedGraph* graph) {
42	// 用于记录已访问节点的哈希表
43	unordered_map<Node*, Node*> nodes_completed;
44
45	// 创建新图
46	DirectedGraph* clone_graph = new DirectedGraph();
47
48	// 如果原图为空，返回空图
49	if (graph->nodes.empty()) {
50		return clone_graph;
51	}
52	// 调用递归函数
53	// 以第一个节点作为根节点
54	CloneRec(graph->nodes[0], clone_graph, nodes_completed);
55
56	// 返回深度拷贝的图
57	return clone_graph;
58}
59
60int main() {
61	// 初始化图1
62	DirectedGraph* g1 = new DirectedGraph();
63
64	cout << "------------	 示例 # 1		-----------" << endl;
65	// 添加顶点/节点
66	g1->AddVertex(0);
67	g1->AddVertex(1);
68	g1->AddVertex(2);
69	g1->AddVertex(3);
70	g1->AddVertex(4);
71
72	// 添加节点0的边
73	g1->AddEdge(0, 2);
74	g1->AddEdge(0, 3);
75	g1->AddEdge(0, 4);
76
77	// 添加节点1的边
78	g1->AddEdge(1, 2);
79
80	// 添加节点2的边
81	g1->AddEdge(2, 0);
82
83	// 添加节点3的边
84	g1->AddEdge(3, 2);
85
86	// 添加节点4的边
87	g1->AddEdge(4, 1);
88	g1->AddEdge(4, 3);
89	g1->AddEdge(4, 0);
90
91	// 打印图
92	cout << "原始图（拷贝前）：" << endl;
93
94	// 自定义函数打印图
95	g1->PrintGraph();
96	cout << endl;
97
98
99	DirectedGraph* g1Copy = Clone(g1);
100	cout << "克隆图（拷贝后）：" << endl;
101	// 自定义函数打印图
102	g1Copy->PrintGraph();
103
104	cout << "\n原始图（删除边 [0->2] 后）：" << endl;
105	g1->DeleteEdge(0, 2);
106	// 自定义函数打印图
107	g1->PrintGraph();
108
109	cout << "\n克隆图（从原始图删除边 [0->2] 后）：" << endl;
110	// 自定义函数打印图
111	g1Copy->PrintGraph();
112
113
114	// 初始化图2
115	DirectedGraph* g2 = new DirectedGraph();
116
117	cout << "\n------------	 示例 # 2		-----------" << endl;
118	// 添加顶点/节点
119	g2->AddVertex(1);
120	g2->AddVertex(2);
121	g2->AddVertex(3);
122	g2->AddVertex(4);
123	g2->AddVertex(5);
124
125	g2->AddEdge(1, 2);
126	g2->AddEdge(1, 3);
127	g2->AddEdge(1, 4);
128
129	g2->AddEdge(2, 1);
130	g2->AddEdge(2, 3);
131	g2->AddEdge(2, 4);
132
133	g2->AddEdge(3, 1);
134	g2->AddEdge(3, 2);
135	g2->AddEdge(3, 4);
136	g2->AddEdge(3, 5);
137
138	g2->AddEdge(4, 1);
139	g2->AddEdge(4, 2);
140	g2->AddEdge(4, 3);
141	g2->AddEdge(4, 5);
142
143	g2->AddEdge(5, 3);
144
145	// 打印图
146	cout << "原始图（拷贝前）：" << endl;
147
148	// 自定义函数打印图
149	g2->PrintGraph();
150	cout << endl;
151
152	DirectedGraph* g2Copy = Clone(g2);
153	cout << "克隆图（拷贝后）：" << endl;
154	// 自定义函数打印图
155	g2Copy->PrintGraph();
156
157	cout << "\n原始图（删除边 [5->3] 后）：" << endl;
158	g2->DeleteEdge(5, 3);
159	// 自定义函数打印图
160	g2->PrintGraph();
161
162	cout << "\n克隆图（从原始图删除边 [5->3] 后）：" << endl;
163	// 自定义函数打印图
164	g2Copy->PrintGraph();
165}

Java

1// 导入所需函数
2import java.util.*;
3
4class ClonedGraph<X> {
5	private Node<X> cloneRec(Node<X> root, DirectedGraph<X> graph,
6			HashMap<Node<X>, Node<X>> nodesCompleted) {
7		// 基础情况：无节点时返回空
8		if (root == null) {
9			return null;
10		}
11
12		// 创建新顶点/节点
13		Node<X> pNew = new Node<X>(root.data);
14
15		// 使用哈希表记录已访问节点
16		nodesCompleted.put(root, pNew);
17
18		// 将新节点加入图中
19		graph.addVertexInNodes(pNew);
20
21		// 遍历当前节点的所有邻居
22		for (Node<X> p : root.neighbors) {
23			Node<X> x = nodesCompleted.get(p);
24			if (x == null) {
25				// 如果节点未被访问，递归调用以创建节点
26				pNew.neighbors.add(cloneRec(p, graph, nodesCompleted));
27			} else {
28				// 如果节点已被访问，直接将其加入当前节点的邻居列表
29				pNew.neighbors.add(x);
30			}
31		}
32		return pNew;
33	}
34
35	public DirectedGraph<X> clone(DirectedGraph<X> graph) {
36		// 用于记录已访问节点的哈希表
37		HashMap<Node<X>, Node<X>> nodesCompleted =
38				new HashMap<Node<X>, Node<X>>();
39
40		// 创建新图
41		DirectedGraph<X> cloneGraph = new DirectedGraph<X>();
42
43		// 如果原图为空，返回空图
44		if (graph.nodes.isEmpty()) {
45			return cloneGraph;
46		}
47
48		// 调用递归函数
49		// 以第一个节点作为根节点
50		cloneRec(graph.nodes.get(0), cloneGraph, nodesCompleted);
51
52		// 返回深度拷贝的图
53		return cloneGraph;
54	}
55
56	public static void main(String[] args) {
57		// 初始化图1
58		DirectedGraph<Integer> g1 = new DirectedGraph<Integer>();
59
60		System.out.println("------------   示例 # 1    -----------");
61		// 添加顶点/节点
62		g1.addVertex(0);
63		g1.addVertex(1);
64		g1.addVertex(2);
65		g1.addVertex(3);
66		g1.addVertex(4);
67
68		// 添加节点0的边
69		g1.addEdge(0, 2);
70		g1.addEdge(0, 3);
71		g1.addEdge(0, 4);
72
73		// 添加节点1的边
74		g1.addEdge(1, 2);
75
76		// 添加节点2的边
77		g1.addEdge(2, 0);
78
79		// 添加节点3的边
80		g1.addEdge(3, 2);
81
82		// 添加节点4的边
83		g1.addEdge(4, 1);
84		g1.addEdge(4, 3);
85		g1.addEdge(4, 0);
86
87		// 打印图
88		System.out.println("原始图（拷贝前）：");
89
90		// 自定义函数打印图
91		g1.printGraph();
92		System.out.println();
93
94		// 初始化克隆图
95		ClonedGraph<Integer> cloneGraphInt = new ClonedGraph<Integer>();
96		DirectedGraph<Integer> g1Copy = cloneGraphInt.clone(g1);
97		System.out.println("克隆图（拷贝后）：");
98		// 自定义函数打印图
99		g1Copy.printGraph();
100
101		System.out.println("\n原始图（删除边 [0->2] 后）：");
102		g1.deleteEdge(0, 2);
103		// 自定义函数打印图
104		g1.printGraph();;
105
106		System.out.println(
107				"\n克隆图（从原始图删除边 [0->2] 后）： ");
108		// 自定义函数打印图
109		g1Copy.printGraph();
110
111		// 初始化图2
112		DirectedGraph<String> g2 = new DirectedGraph<String>();
113
114		System.out.println("\n------------   示例 # 2    -----------");
115		g2.addVertex("v1");
116		g2.addVertex("v2");
117		g2.addVertex("v3");
118		g2.addVertex("v4");
119		g2.addVertex("v5");
120
121		g2.addEdge("v1", "v2");
122		g2.addEdge("v1", "v3");
123		g2.addEdge("v1", "v4");
124
125		g2.addEdge("v2", "v1");
126		g2.addEdge("v2", "v3");
127		g2.addEdge("v2", "v4");
128
129		g2.addEdge("v3", "v1");
130		g2.addEdge("v3", "v2");
131		g2.addEdge("v3", "v4");
132		g2.addEdge("v3", "v5");
133
134		g2.addEdge("v4", "v1");
135		g2.addEdge("v4", "v2");
136		g2.addEdge("v4", "v3");
137		g2.addEdge("v4", "v5");
138
139		g2.addEdge("v5", "v3");
140
141		// 打印图
142		System.out.println("原始图（拷贝前）：");
143
144		// 自定义函数打印图
145		g2.printGraph();
146
147		// 初始化克隆图
148		ClonedGraph<String> cloneGraphStr = new ClonedGraph<String>();
149		DirectedGraph<String> g2Copy = cloneGraphStr.clone(g2);
150		System.out.println("\n克隆图（拷贝后）：");
151		// 自定义函数打印图
152		g2Copy.printGraph();
153
154		System.out.println("\n原始图（删除边 [v5->v3] 后）：");
155		g2.deleteEdge("v5", "v3");
156		// 自定义函数打印图
157		g2.printGraph();
158
159		System.out.println(
160				"\n克隆图（从原始图删除边 [v5->v3] 后）： ");
161		// 自定义函数打印图
162		g2Copy.printGraph();
163	}
164}

Python

1from directed_graph import *
2
3def clone_rec(root, graph, nodes_completed):
4  # 基础情况：无节点时返回空
5  if not root:
6    return None
7
8  # 创建新顶点/节点
9  pNew = Node(root.data)
10
11  # 使用字典记录已访问节点
12  nodes_completed[root] = pNew
13
14  # 将新节点加入图中
15  graph.add_vertex_in_nodes(pNew)
16
17  # 遍历当前节点的所有邻居
18  for p in root.neighbors:
19    x = nodes_completed.get(p)
20    if not x:
21      # 如果节点未被访问，递归调用以创建节点
22      pNew.neighbors.append(clone_rec(p, graph, nodes_completed))
23    else:
24      # 如果节点已被访问，直接将其加入当前节点的邻居列表
25      pNew.neighbors.append(x)
26  return pNew
27
28def clone(graph):
29  # 用于记录已访问节点的字典
30  nodes_completed = {}
31  
32  # 创建新图
33  clone_graph = DirectedGraph()
34  
35  # 调用递归函数
36  # 以第一个节点作为根节点
37  
38  if not graph.nodes:
39    return None
40  else:
41    clone_rec(graph.nodes[0], clone_graph, nodes_completed)
42
43  # 返回深度拷贝的图
44  return clone_graph
45
46def main():
47  # 主程序从这里开始
48  g1 = DirectedGraph()
49
50  print("------------   示例 # 1    -----------")
51  # 添加顶点/节点
52  g1.add_vertex(0)
53  g1.add_vertex(1)
54  g1.add_vertex(2)
55  g1.add_vertex(3)
56  g1.add_vertex(4)
57
58  # 添加节点0的边
59  g1.add_edge(0, 2)
60  g1.add_edge(0, 3)
61  g1.add_edge(0, 4)
62
63  # 添加节点1的边
64  g1.add_edge(1, 2)
65
66  # 添加节点2的边
67  g1.add_edge(2, 0)
68
69  # 添加节点3的边
70  g1.add_edge(3, 2)
71
72  # 添加节点4的边
73  g1.add_edge(4, 1)
74  g1.add_edge(4, 3)
75  g1.add_edge(4, 0)
76
77  # 打印图
78
79  print("原始图（拷贝前）： ")
80  print(g1)
81
82  g1_copy = clone(g1)
83  print("克隆图（拷贝后）：")
84  print(g1_copy)
85
86  print("\n原始图（删除边 [0->2] 后）：")
87  g1.delete_edge(0, 2)
88  print(g1)
89
90  print("\n克隆图（从原始图删除边 [0->2] 后）： ")
91  print(g1_copy)
92
93  g2 = DirectedGraph()
94
95  # 添加顶点/节点
96
97  print("\n\n------------   示例 # 2    -----------")
98  g2.add_vertex("v1")
99  g2.add_vertex("v2")
100  g2.add_vertex("v3")
101  g2.add_vertex("v4")
102  g2.add_vertex("v5")
103
104  g2.add_edge("v1", "v2")
105  g2.add_edge("v1", "v3")
106  g2.add_edge("v1", "v4")
107
108  g2.add_edge("v2", "v1")
109  g2.add_edge("v2", "v3")
110  g2.add_edge("v2", "v4")
111
112  g2.add_edge("v3", "v1")
113  g2.add_edge("v3", "v2")
114  g2.add_edge("v3", "v4")
115  g2.add_edge("v3", "v5")
116
117  g2.add_edge("v4", "v1")
118  g2.add_edge("v4", "v2")
119  g2.add_edge("v4", "v3")
120  g2.add_edge("v4", "v5")
121
122  g2.add_edge("v5", "v3")
123
124  print("原始图（拷贝前）：")
125  print(g2)
126
127  g2_copy = clone(g2)
128  print("\n克隆图（拷贝后）：")
129  print(g2_copy)
130
131
132  print("\n原始图（删除边 [v5->v3] 后）：")
133  g2.delete_edge("v5", "v3")
134  print(g2)
135
136  print("\n克隆图（从原始图删除边 [v5->v3] 后）： ")
137  print(g2_copy)
138
139if __name__ == '__main__':
140  main()

JS

1import { Node } from './Node.js';
2import {  DirectedGraph } from './DirectedGraph.js';
3
4let cloneRec = function(root, graph, nodesCompleted) {
5    // 基础情况：无节点时返回空
6    if (!root) {
7        return null;
8    }
9    // 创建新顶点/节点
10    let pNew = new Node(root.data);
11
12    // 使用哈希表记录已访问节点
13    nodesCompleted[root.data] = pNew;
14
15    // 将新节点加入图中
16    graph.addVertexInNodes(pNew);
17
18    for (let p in root.neighbors) {
19        let x = nodesCompleted[root.neighbors[p].data];
20        if (!x) {
21            pNew.neighbors.push(cloneRec(root.neighbors[p], graph, nodesCompleted));
22        } else {
23            pNew.neighbors.push(x);
24        }
25    }
26
27    return pNew;
28};
29
30let clone = function(graph) {
31    // 用于记录已访问节点的哈希表  
32    var nodesCompleted = {};
33    // 创建新图
34    var cloneGraph = new DirectedGraph();
35    // 调用递归函数
36    // 以第一个节点作为根节点
37    if(graph.nodes.length == 0){
38        return null
39    } else {
40        cloneRec(graph.nodes[0], cloneGraph, nodesCompleted);
41    }
42    // 返回深度拷贝的图
43    return cloneGraph;
44};
45
46let g1 = new DirectedGraph()
47
48console.log("------------   示例 # 1    -----------")
49// 添加顶点/节点
50g1.addVertex(0)
51g1.addVertex(1)
52g1.addVertex(2)
53g1.addVertex(3)
54g1.addVertex(4)
55
56// 添加节点0的边
57g1.addEdge(0, 2)
58g1.addEdge(0, 3)
59g1.addEdge(0, 4)
60
61// 添加节点1的边
62g1.addEdge(1, 2)
63
64// 添加节点2的边
65g1.addEdge(2, 0)
66
67// 添加节点3的边
68g1.addEdge(3, 2)
69
70// 添加节点4的边
71g1.addEdge(4, 1)
72g1.addEdge(4, 3)
73g1.addEdge(4, 0)
74
75// 打印图
76
77console.log("原始图（拷贝前）： ")
78g1.printGraph()
79
80let g1_copy = clone(g1)
81console.log("克隆图（拷贝后）：")
82g1_copy.printGraph()
83
84console.log("\n原始图（删除边 [0->2] 后）：")
85g1.deleteEdge(0, 2)
86g1.printGraph()
87
88console.log("\n克隆图（从原始图删除边 [0->2] 后）： ")
89g1_copy.printGraph()
90
91let g2 = new DirectedGraph()
92
93// 添加顶点/节点
94
95console.log("\n\n------------   示例 // 2    -----------")
96g2.addVertex("v1")
97g2.addVertex("v2")
98g2.addVertex("v3")
99g2.addVertex("v4")
100g2.addVertex("v5")
101
102g2.addEdge("v1", "v2")
103g2.addEdge("v1", "v3")
104g2.addEdge("v1", "v4")
105
106g2.addEdge("v2", "v1")
107g2.addEdge("v2", "v3")
108g2.addEdge("v2", "v4")
109
110g2.addEdge("v3", "v1")
111g2.addEdge("v3", "v2")
112g2.addEdge("v3", "v4")
113g2.addEdge("v3", "v5")
114
115g2.addEdge("v4", "v1")
116g2.addEdge("v4", "v2")
117g2.addEdge("v4", "v3")
118g2.addEdge("v4", "v5")
119
120g2.addEdge("v5", "v3")
121
122console.log("原始图（拷贝前）：")
123g2.printGraph()
124
125let g2_copy = clone(g2)
126console.log("\n克隆图（拷贝后）：")
127g2_copy.printGraph()
128
129
130console.log("\n原始图（删除边 [v5->v3] 后）：")
131g2.deleteEdge("v5", "v3")
132g2.printGraph()
133
134console.log("\n克隆图（从原始图删除边 [v5->v3] 后）： ")
135g2_copy.printGraph()

Ruby

1require './directed_graph'
2
3def clone_rec(root, graph, nodes_completed)
4    # 基础情况：无节点时返回空
5    return unless root
6
7    # 创建新顶点/节点
8    p_new = Node.new(root.data)
9
10    # 使用哈希表记录已访问节点
11    nodes_completed[root] = p_new
12    
13    # 将新节点加入图中
14    graph.add_vertex_in_nodes(p_new)
15  
16    # 遍历当前节点的所有邻居
17    root.neighbors.each do |p|
18      x = nodes_completed[p]
19      if !x
20        # 如果节点未被访问，递归调用以创建节点
21        p_new.neighbors.push(clone_rec(p, graph, nodes_completed))
22      else
23        # 如果节点已被访问，直接将其加入当前节点的邻居列表
24        p_new.neighbors.push(x)
25      end
26    end
27  return p_new
28end
29  
30def clone(graph)
31  # 用于记录已访问节点的哈希表
32  nodes_completed = {}
33  # 创建新图
34  clone_graph = DirectedGraph.new()
35  # 调用递归函数
36  # 以第一个节点作为根节点
37  clone_rec(graph.nodes[0], clone_graph, nodes_completed)
38  # 返回深度拷贝的图
39  return clone_graph
40end
41  
42
43
44# 主程序从这里开始
45g1 = DirectedGraph.new()
46
47puts "------------   示例 # 1    -----------"
48# 添加顶点/节点
49g1.add_vertex(0)
50g1.add_vertex(1)
51g1.add_vertex(2)
52g1.add_vertex(3)
53g1.add_vertex(4)
54
55# 添加节点0的边
56g1.add_edge(0, 2)
57g1.add_edge(0, 3)
58g1.add_edge(0, 4)
59
60# 添加节点1的边
61g1.add_edge(1, 2)
62
63# 添加节点2的边
64g1.add_edge(2, 0)
65
66# 添加节点3的边
67g1.add_edge(3, 2)
68
69# 添加节点4的边
70g1.add_edge(4, 1)
71g1.add_edge(4, 3)
72g1.add_edge(4, 0)
73
74# 打印图
75
76puts "原始图（拷贝前）： "
77g1.print_graph()
78
79puts
80
81g1_copy = clone(g1)
82puts "克隆图（拷贝后）："
83g1_copy.print_graph()
84
85puts "\n原始图（删除边 [0->2] 后）："
86g1.delete_edge(0, 2)
87g1.print_graph()
88
89puts "\n克隆图（从原始图删除边 [0->2] 后）： "
90g1_copy.print_graph()
91
92
93g2 = DirectedGraph.new()
94
95# 添加顶点/节点
96
97puts "\n\n------------   示例 # 2    -----------"
98g2.add_vertex("v1")
99g2.add_vertex("v2")
100g2.add_vertex("v3")
101g2.add_vertex("v4")
102g2.add_vertex("v5")
103
104g2.add_edge("v1", "v2")
105g2.add_edge("v1", "v3")
106g2.add_edge("v1", "v4")
107
108g2.add_edge("v2", "v1")
109g2.add_edge("v2", "v3")
110g2.add_edge("v2", "v4")
111
112g2.add_edge("v3", "v1")
113g2.add_edge("v3", "v2")
114g2.add_edge("v3", "v4")
115g2.add_edge("v3", "v5")
116
117g2.add_edge("v4", "v1")
118g2.add_edge("v4", "v2")
119g2.add_edge("v4", "v3")
120g2.add_edge("v4", "v5")
121
122g2.add_edge("v5", "v3")
123
124puts "原始图（拷贝前）："
125g2.print_graph()
126
127g2_copy = clone(g2)
128puts "\n克隆图（拷贝后）："
129g2_copy.print_graph()
130
131
132puts "\n原始图（删除边 [v5->v3] 后）："
133g2.delete_edge("v5", "v3")
134g2.print_graph()
135
136puts "\n克隆图（从原始图删除边 [v5->v3] 后）： "
137g2_copy.print_graph()

Go

1package main
2
3import (
4	"fmt"
5)
6/* CloneRec 是一个工作函数，将被 Clone 函数用于递归地克隆图 */
7func CloneRec(root *Node, graph *DirectedGraph, nodesCompleted map[*Node]*Node) *Node {
8	// 基础情况：无节点时返回空
9	if root == nil {
10		return nil
11	}
12	// 创建新顶点/节点
13	pNew := &Node{data: root.data}
14	// 使用哈希表记录已访问节点
15	nodesCompleted[root] = pNew
16	// 将新节点加入图中
17	graph.AddVertexInNodes(pNew)
18	// 遍历当前节点的所有邻居
19	for _, p := range root.neighbors {
20		x := nodesCompleted[p]
21		if x == nil {
22			// 如果节点未被访问，递归调用以创建节点
23			pNew.neighbors = append(pNew.neighbors, CloneRec(p, graph, nodesCompleted))
24		} else {
25			// 如果节点已被访问，直接将其加入当前节点的邻居列表
26			pNew.neighbors = append(pNew.neighbors, x)
27		}
28	}
29	return pNew
30}
31/* Clone 是我们的挑战函数，我们将用它实现图的克隆功能 */ 
32func Clone(graph *DirectedGraph) *DirectedGraph {
33	// 用于记录已访问节点的哈希表
34	nodesCompleted := make(map[*Node]*Node)
35	// 创建新图
36	cloneGraph := new(DirectedGraph)
37	// 如果图中节点数量为0，返回空
38	if len(graph.nodes) == 0 {
39		return nil
40	}
41	// 调用递归函数
42	// 以第一个节点作为根节点
43	CloneRec(graph.nodes[0], cloneGraph, nodesCompleted)
44 	// 返回深度拷贝的图
45	return cloneGraph
46}
47
48func main() {
49	
50	// 主程序从这里开始
51	g1 := new(DirectedGraph)
52
53	fmt.Print("------------   示例 # 1    -----------\n")
54	// 添加顶点/节点
55	g1.AddVertex("0")
56	g1.AddVertex("1")
57	g1.AddVertex("2")
58	g1.AddVertex("3")
59	g1.AddVertex("4")
60
61	// 添加节点0的边
62	g1.AddEdge("0", "2")
63	g1.AddEdge("0", "3")
64	g1.AddEdge("0", "4")
65
66	// 添加节点1的边
67	g1.AddEdge("1", "2")
68
69	// 添加节点2的边
70	g1.AddEdge("2", "0")
71	// 添加节点3的边
72	g1.AddEdge("3", "2")
73
74	// 添加节点4的边
75	g1.AddEdge("4", "1")
76	g1.AddEdge("4", "3")
77	g1.AddEdge("4", "0")
78
79	// 打印图
80	fmt.Println("原始图（拷贝前）： ")
81	g1.PrintGraph()
82
83	g1Copy := Clone(g1)
84	fmt.Print("\n克隆图（拷贝后）：\n")
85	g1Copy.PrintGraph()
86
87	fmt.Print("\n原始图（删除边 [0->2] 后）：\n")
88	g1.DeleteEdge("0", "2")
89	g1.PrintGraph()
90
91	fmt.Print("\n克隆图（从原始图删除边 [0->2] 后）： \n")
92	g1Copy.PrintGraph()
93
94	g2 := new(DirectedGraph)
95
96	// 添加顶点/节点
97	fmt.Print("\n\n------------   示例 # 2    -----------\n")
98	g2.AddVertex("v1")
99	g2.AddVertex("v2")
100	g2.AddVertex("v3")
101	g2.AddVertex("v4")
102	g2.AddVertex("v5")
103
104	g2.AddEdge("v1", "v2")
105	g2.AddEdge("v1", "v3")
106	g2.AddEdge("v1", "v4")
107
108	g2.AddEdge("v2", "v1")
109	g2.AddEdge("v2", "v3")
110	g2.AddEdge("v2", "v4")
111
112	g2.AddEdge("v3", "v1")
113	g2.AddEdge("v3", "v2")
114	g2.AddEdge("v3", "v4")
115	g2.AddEdge("v3", "v5")
116
117	g2.AddEdge("v4", "v1")
118	g2.AddEdge("v4", "v2")
119	g2.AddEdge("v4", "v3")
120	g2.AddEdge("v4", "v5")
121
122	g2.AddEdge("v5", "v3")
123
124
125	fmt.Print("原始图（拷贝前）：\n")
126	g2.PrintGraph()
127
128	g2Copy := Clone(g2)
129	fmt.Print("\n克隆图（拷贝后）：\n")
130	g2Copy.PrintGraph()
131
132	fmt.Print("\n原始图（删除边 [5->3] 后）：\n")
133	g2.DeleteEdge("v5", "v3")
134	g2.PrintGraph()
135
136	fmt.Print("\n克隆图（从原始图删除边 [5->3] 后）： \n")
137	g2Copy.PrintGraph()
138
139}

时间复杂度

此解决方案的时间复杂度为 $O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。

空间复杂度

此解决方案的空间复杂度为线性，$O(n)$，其中 $n$ 是图中顶点的数量。

哈希表最多包含 $n$ 个条目，因此最坏情况下的空间复杂度为 $O(n)$。