全ての連結成分の集合を求める

有向グラフにおける連結成分の集合みたいなのがどうだったか忘れたので、無向グラフ化(両方を有向にするっぽい感じで)して考えることにした。

# -*- coding: utf-8 -*-
require 'pp'
require 'set'

class Graph
  def initialize(edges)
    @edges = edges
    @nodes = Hash.new{|h,k| h[k] = []}
  end
  
  def add_edge(edge)
    @edges.push edge unless @edges.index(edge)
  end
  
  def add_node(u, v)
    if @edges.index(u).nil?
      @edges.push u
    elsif @edges.index(v).nil?
      @edges.push v
    end
    
    unless @nodes[u].index(v)
      @nodes[u].push v
    end
  end
    
  def dfs(s)
    stack = []
    stack.push s
    explored = []
    while(!stack.empty?)
      u = stack.shift
      if explored.include?(u) == false
        explored.push u
        @nodes[u].each{|v|
          stack.unshift v
        }
      end
    end
    return explored
  end

  def all_connected_components(rest_edges = @edges,result = [])
    dfs_result = dfs(rest_edges.shift)
    result.push dfs_result
    dfs_result.each{|item|
      rest_edges.delete(item)
    }
    while(!rest_edges.empty?)
      all_connected_components(rest_edges,result)
    end
    return result
  end
end

g = Graph.new(["1", "2", "3"])
g.add_edge("8")
g.add_edge("10")
g.add_edge("3")
g.add_edge("7")

g.add_node("3", "2")
g.add_node("2", "3")

g.add_node("1", "5")
g.add_node("5", "1")

g.add_node("1", "6")
g.add_node("6", "1")

g.add_node("5", "8")
g.add_node("8", "5")

g.add_node("1", "3")
g.add_node("3", "1")

g.add_node("2", "9")
g.add_node("9", "2")

g.add_node("10", "11")
g.add_node("11", "10")

pp g.all_connected_components()

ちゃんと3つの連結成分の集合になっていることが確認できる。

/tmp% ruby hash_graph.rb
[["1", "3", "2", "9", "6", "5", "8"], ["10", "11"], ["7"]]