Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit85a1175

Browse files
committed
Splitting consumers for seen and visited nodes in graph BFS
1 parentb561094 commit85a1175

File tree

2 files changed

+21
-7
lines changed

2 files changed

+21
-7
lines changed

‎data_structures/graphs/bfs.rb

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -25,33 +25,36 @@ def initialize(visited, parents, distances)
2525
##
2626
# Performs a breadth-first search for the provided graph, starting at the given node.
2727
# Returns the search result (see GraphBfsResult).
28-
# Nodes are consumed upon discovery using the provided node consumer (nothing, by default).
28+
# Nodes are consumed using the provided consumers upon being first seen, or being completely visited
29+
# (nothing, by default).
2930
#
3031
# The algorithm has a time complexity of O(|V| + |E|), where:
3132
# - |V| is the number of nodes in the graph;
3233
# - |E| is the number of edges in the graph.
3334

34-
defbfs(graph,start_node,node_consumer=method(:do_nothing_on_node))
35+
defbfs(graph,start_node,seen_node_consumer:method(:do_nothing_on_node),visited_node_consumer:method(:do_nothing_on_node))
3536
seen=Set[]
3637
visited=Set[]
3738
parents={start_node=>nil}
3839
distances={start_node=>0}
3940

4041
seen.add(start_node)
42+
seen_node_consumer.call(start_node)
4143
q=Queue.new
4244
q.push(start_node)
4345
untilq.empty?
4446
node=q.pop
45-
node_consumer.call(node)
4647
forneighboringraph.neighbors(node)
4748
unlessseen.include?(neighbor)
4849
seen.add(neighbor)
4950
distances[neighbor]=distances[node] +1
5051
parents[neighbor]=node
52+
seen_node_consumer.call(neighbor)
5153
q.push(neighbor)
5254
end
5355
end
5456
visited.add(node)
57+
visited_node_consumer.call(node)
5558
end
5659

5760
GraphBfsResult.new(visited,parents,distances)

‎data_structures/graphs/bfs_test.rb

Lines changed: 15 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -65,14 +65,25 @@ def test_bfs_visits_graph_partially
6565
}
6666
end
6767

68-
deftest_bfs_visits_with_node_consumer
68+
deftest_bfs_visits_with_seen_node_consumer
6969
graph=UnweightedGraph.new(nodes:[:u,:v,:w],directed:false)
7070
graph.add_edge(:u,:v)
7171
graph.add_edge(:u,:w)
7272

73-
visit_order=[]
74-
bfs(graph,:w,->(node){visit_order.append(node)})
73+
seen_order=[]
74+
bfs(graph,:w,seen_node_consumer:->(node){seen_order.append(node)})
7575

76-
assertvisit_order ==[:w,:u,:v]
76+
assertseen_order ==[:w,:u,:v]
77+
end
78+
79+
deftest_bfs_visits_with_visited_node_consumer
80+
graph=UnweightedGraph.new(nodes:[:u,:v,:w],directed:false)
81+
graph.add_edge(:u,:v)
82+
graph.add_edge(:u,:w)
83+
84+
visited_order=[]
85+
bfs(graph,:w,visited_node_consumer:->(node){visited_order.append(node)})
86+
87+
assertvisited_order ==[:w,:u,:v]
7788
end
7889
end

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp