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

Commit774a964

Browse files
authored
Merge pull requestTheAlgorithms#207 from aparibocci/feature/graph_bfs
Implementing BFS for unweighted graphs
2 parents450ba13 +85a1175 commit774a964

File tree

4 files changed

+156
-2
lines changed

4 files changed

+156
-2
lines changed

‎data_structures/graphs/bfs.rb

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
require'set'
2+
3+
##
4+
# This class represents the result of a breadth-first search performed on an unweighted graph.
5+
#
6+
# It exposes:
7+
# - the set of visited nodes
8+
# - a hash of distances by node from the search root node
9+
# (only for visited nodes, 0 for the search root node);
10+
# - a hash of parent nodes by node
11+
# (only for visited nodes, nil for the search root node).
12+
13+
classGraphBfsResult
14+
attr_reader:visited
15+
attr_reader:parents
16+
attr_reader:distances
17+
18+
definitialize(visited,parents,distances)
19+
@visited=visited
20+
@parents=parents
21+
@distances=distances
22+
end
23+
end
24+
25+
##
26+
# Performs a breadth-first search for the provided graph, starting at the given node.
27+
# Returns the search result (see GraphBfsResult).
28+
# Nodes are consumed using the provided consumers upon being first seen, or being completely visited
29+
# (nothing, by default).
30+
#
31+
# The algorithm has a time complexity of O(|V| + |E|), where:
32+
# - |V| is the number of nodes in the graph;
33+
# - |E| is the number of edges in the graph.
34+
35+
defbfs(graph,start_node,seen_node_consumer:method(:do_nothing_on_node),visited_node_consumer:method(:do_nothing_on_node))
36+
seen=Set[]
37+
visited=Set[]
38+
parents={start_node=>nil}
39+
distances={start_node=>0}
40+
41+
seen.add(start_node)
42+
seen_node_consumer.call(start_node)
43+
q=Queue.new
44+
q.push(start_node)
45+
untilq.empty?
46+
node=q.pop
47+
forneighboringraph.neighbors(node)
48+
unlessseen.include?(neighbor)
49+
seen.add(neighbor)
50+
distances[neighbor]=distances[node] +1
51+
parents[neighbor]=node
52+
seen_node_consumer.call(neighbor)
53+
q.push(neighbor)
54+
end
55+
end
56+
visited.add(node)
57+
visited_node_consumer.call(node)
58+
end
59+
60+
GraphBfsResult.new(visited,parents,distances)
61+
end
62+
63+
private
64+
defdo_nothing_on_node(node)
65+
end

‎data_structures/graphs/bfs_test.rb

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
require'minitest/autorun'
2+
require_relative'bfs'
3+
require_relative'unweighted_graph'
4+
5+
classTestBfs <Minitest::Test
6+
deftest_bfs_visits_single_graph_node
7+
graph=UnweightedGraph.new(nodes:[:u,:v,:w],directed:false)
8+
graph.add_edge(:u,:v)
9+
10+
bfs_result=bfs(graph,:w)
11+
12+
assertbfs_result.visited.to_set ==[:w].to_set
13+
assertbfs_result.parents =={
14+
:w=>nil
15+
}
16+
assertbfs_result.distances =={
17+
:w=>0
18+
}
19+
end
20+
21+
deftest_bfs_visits_graph_fully
22+
graph=UnweightedGraph.new(nodes:[:u,:v,:w,:x],directed:false)
23+
graph.add_edge(:u,:v)
24+
graph.add_edge(:u,:w)
25+
graph.add_edge(:w,:x)
26+
27+
bfs_result=bfs(graph,:u)
28+
29+
assertbfs_result.visited.to_set ==[:u,:v,:w,:x].to_set
30+
assertbfs_result.parents =={
31+
:u=>nil,
32+
:v=>:u,
33+
:w=>:u,
34+
:x=>:w
35+
}
36+
assertbfs_result.distances =={
37+
:u=>0,
38+
:v=>1,
39+
:w=>1,
40+
:x=>2
41+
}
42+
end
43+
44+
deftest_bfs_visits_graph_partially
45+
graph=UnweightedGraph.new(nodes:[:u,:v,:w,:x,:y,:z],directed:false)
46+
graph.add_edge(:u,:v)
47+
graph.add_edge(:w,:x)
48+
graph.add_edge(:x,:y)
49+
graph.add_edge(:y,:z)
50+
51+
bfs_result=bfs(graph,:x)
52+
53+
assertbfs_result.visited.to_set ==[:w,:x,:y,:z].to_set
54+
assertbfs_result.parents =={
55+
:w=>:x,
56+
:x=>nil,
57+
:y=>:x,
58+
:z=>:y
59+
}
60+
assertbfs_result.distances =={
61+
:w=>1,
62+
:x=>0,
63+
:y=>1,
64+
:z=>2
65+
}
66+
end
67+
68+
deftest_bfs_visits_with_seen_node_consumer
69+
graph=UnweightedGraph.new(nodes:[:u,:v,:w],directed:false)
70+
graph.add_edge(:u,:v)
71+
graph.add_edge(:u,:w)
72+
73+
seen_order=[]
74+
bfs(graph,:w,seen_node_consumer:->(node){seen_order.append(node)})
75+
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]
88+
end
89+
end

‎data_structures/graphs/unweighted_graph_test.rb

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,7 +72,7 @@ def test_add_edge_adds_edge_to_directed_unweighted_graph
7272
assertgraph.neighbors(:v).empty?
7373
end
7474

75-
deftest_add_edge_adds_edge_to_directed_unweighted_graph
75+
deftest_add_edge_adds_edge_to_undirected_unweighted_graph
7676
graph=UnweightedGraph.new(nodes:[:u,:v],directed:false)
7777
graph.add_edge(:u,:v)
7878

‎data_structures/graphs/weighted_graph_test.rb

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -78,7 +78,7 @@ def test_add_edge_adds_edge_to_directed_weighted_graph
7878
assertgraph.edges(:v).empty?
7979
end
8080

81-
deftest_add_edge_adds_edge_to_directed_weighted_graph
81+
deftest_add_edge_adds_edge_to_undirected_weighted_graph
8282
graph=WeightedGraph.new(nodes:[:u,:v],directed:false)
8383
graph.add_edge(:u,:v,2)
8484

0 commit comments

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