16 BFS: Shortest Reach in a Graph
以下の形式の入力が与えられる。
2 4 2 1 2 1 3 1 3 1 2 3 2
最初の行には、クエリの数を示す整数が示される。後続の行は、各クエリを次の形式で示す。
- 最初の行には、グラフ内のノードの数nとエッジの数mのそれぞれの値をスペースで区切りの2つの整数で示す。
- 後続の各行には、スペースで区切られた2つの整数が含まれており、ノードからノードに接続するエッジが示される。
- 最後の行には、開始ノードのインデックスを示す1つの整数が示される。
出力は、開始ノードから各ノードへの距離を出力する。1つのエッジの距離は6、エッジで繋がっていないノードへの距離は-1 とする。
上記入力の場合、解答は以下となる。
6 6 -1 -1 6
solution
この問題は、無向グラフの探索問題である。 幅優先探索(BFS)アルゴリズムで解いている。以下、rubyでの解。
class Node def initialize @neighbors = [] end def addNeighbor(id) @neighbors << id if !@neighbors.index(id) end def getNeighbors return @neighbors end end class Graph DIST = 6 def initialize @nodes = [] end def addNode(node) @nodes << node end def shortestReach(startId) dist = Array.new(@nodes.size, -1) dist[startId] = 0 queue = [] queue << startId while (!queue.empty?) nodeId = queue.shift @nodes[nodeId].getNeighbors.each do |neighbor| if dist[neighbor] == -1 queue << neighbor dist[neighbor] = dist[nodeId] + DIST end end end return dist end end input = $stdin.read.split("\n") q = input.shift.to_i q.times do n, edges = input.shift.split(" ").map(&:to_i) graph, nodes = Graph.new, [] n.times { nodes << Node.new } for i in 0..edges-1 ary = input.shift.split(" ").map(&:to_i) idx1, idx2 = ary[0] - 1, ary[1] - 1 nodes[idx1].addNeighbor(idx2) if nodes[idx1] nodes[idx2].addNeighbor(idx1) if nodes[idx2] end nodes.each { |node| graph.addNode(node) } startId = input.shift.to_i - 1 dist = graph.shortestReach(startId) dist.delete_at(startId) puts dist.join(" ") # output answer here end
グラフ理論
BFS(breadth first search: 幅優先探索)とは
感想
BFSアルゴリズム自体は難しくないが、有向or無向、深さ優先or幅優先、訪問済みを無視するかどうか、など一歩処理を間違えると期待する答えが得られなくなるので注意する。
