Do bfs on graph (dfs does not work). Corner case is when a node has an edge to itself.

//example
1 - 2 5
| X | /
3 - 4--
|_|
edges:
1-2, 1-3, 1-4
2-3, 2-4
3-4
4-4, 4-5

graph:
id
set{node} nodes
node:
id
set{node} neighbors
(graph):
edges = new //list{tuple{node, node}}
visited = new //set
q = new
for node in graph.nodes:
if visited.has(node):
continue
q.enqueue(node)
while !q.isempty():
node = q.dequeue()
if visited.has(node):
continue
for neighbor in node.neighbors:
if visited.has(neighbor):
continue
q.enqueue(neighbor)
edges.add(tuple(node, neighbor))
// corner case: node could have edge to itself,
// so mark it visited after visiting its neighbors
visited.add(node)
return edges

## No comments:

## Post a Comment