縦形検索

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()