#16/20 BFS: Shortest Reach in a Graph [Cracking the Coding Interview Challenges]

16 BFS: Shortest Reach in a Graph

www.hackerrank.com

以下の形式の入力が与えられる。

最初の行には、クエリの数を示す整数が示される。後続の行は、各クエリを次の形式で示す。

最初の行には、グラフ内のノードの数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

グラフ理論

グラフ理論 - Wikipedia

BFS(breadth first search: 幅優先探索)とは

幅優先探索 - Wikipedia

感想

BFSアルゴリズム自体は難しくないが、有向or無向、深さ優先or幅優先、訪問済みを無視するかどうか、など一歩処理を間違えると期待する答えが得られなくなるので注意する。