縦形検索
C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー) p.177
#! /usr/bin/env python # -*- encoding: shift_jis -*- adjacent = {} visited = {} def readgraph(data, n): for i in range(1, n+1): for j in range(1, n+1): adjacent[(i,j)] = 0 for k in range(len(data)): if k % 2 == 1: i = data[k-1] j = data[k] adjacent[(i,j)] = 1 adjacent[(j,i)] = 1 print "隣接行列:" for i in range(1, n+1): buf = "" for j in range(1, n+1): buf += " %d" % adjacent[(i,j)] print buf def visit(i, n): print "%d" % i, visited[i] = 1 for j in range(1, n+1): if adjacent[(i,j)] and not visited.has_key(j): visit(j, n) def main(): data = [1, 2, 2, 3, 1, 3, 2, 4, 5, 7] n = max(data) readgraph(data, n) print "連結成分:" count = 0 for i in range(1, n+1): if not visited.has_key(i): count += 1 print "%3d:" % count, visit(i, n) print "" return True if __name__ == "__main__": main()