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

Commit360cba9

Browse files
committed
Implementing unweighted graph BFS
1 parentaf56ad0 commit360cba9

File tree

2 files changed

+123
-0
lines changed

2 files changed

+123
-0
lines changed

‎data_structures/graphs/bfs.rb

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
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+
#
29+
# The algorithm has a time complexity of O(|V| + |E|), where:
30+
# - |V| is the number of nodes in the graph;
31+
# - |E| is the number of edges in the graph.
32+
33+
defbfs(graph,start_node)
34+
seen=Set[]
35+
visited=Set[]
36+
parents={start_node=>nil}
37+
distances={start_node=>0}
38+
39+
seen.add(start_node)
40+
q=Queue.new
41+
q.push(start_node)
42+
untilq.empty?
43+
node=q.pop
44+
forneighboringraph.neighbors(node)
45+
unlessseen.include?(neighbor)
46+
seen.add(neighbor)
47+
distances[neighbor]=distances[node] +1
48+
parents[neighbor]=node
49+
q.push(neighbor)
50+
end
51+
end
52+
visited.add(node)
53+
end
54+
55+
GraphBfsResult.new(visited,parents,distances)
56+
end

‎data_structures/graphs/bfs_test.rb

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
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_undirected_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_undirected_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+
end

0 commit comments

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