6.10 Graph Serialization
6.10.1 Problem Metadata
- Platform: Other
- Tags:
- Techniques: Breadth First Search, Graph
6.10.3 Solution - BFS
6.10.3.1 Walkthrough
Traverse the graph with BFS, recording each node and its neighbors. Use a visited set to avoid cycles. For deserialization, parse each line and rebuild adjacency lists.
6.10.3.3 Code - Java
public String serialize(Node node) {
if (node == null) {
return "";
}
Set<Node> visited = new HashSet<>();
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
visited.add(node);
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
Node current = queue.poll();
sb.append(current.val);
for (Node neighbor : current.neighbors) {
sb.append(',').append(neighbor.val);
if (visited.add(neighbor)) {
queue.offer(neighbor);
}
}
sb.append('\n');
}
return sb.toString();
}