Python实现图转置算法

为什么我要用Python实现一些算法？

这是因为，使用Python能不用考虑一些数据类型的定义，以及内存使用和指针操作方面的问题，对于插入和删除操作更方便，避免一些与算法核心无关的细节，更能突出算法的框架。

针对邻接矩阵的算法实现：

AdjMatrixT.py :

#! /usr/bin/python
# filename : AdjMatrixT.py
# author : Jesse
# update : 2011/08/15 14:24

adjmatrix = [[0, 1, 0, 1], [0, 0, 1, 0], [0, 1, 0, 1], [0, 1, 0, 0]]
v = len(adjmatrix)

print 'before transposing :'
for i in range(v) :
    print adjmatrix[i]

for r in range(v) :
    for c in range(r, v) :
        adjmatrix[c][r] = adjmatrix[r][c] ^ adjmatrix[c][r]
        adjmatrix[r][c] = adjmatrix[r][c] ^ adjmatrix[c][r]
        adjmatrix[c][r] = adjmatrix[r][c] ^ adjmatrix[c][r]

print 'after transposing :'
for i in range(v) :
    print adjmatrix[i]

针对邻接表的算法实现：

AdjListT.py :

#! /usr/bin/python
# filename : AdjListT.py
# author : Jesse
# update : 2011/08/15 15:00

adjlist = [[2, 4], [3], [2, 4], [2]]
v = len(adjlist)

print 'before transposing :'
for i in range(v) :
    print i+1, ' ', adjlist[i]

newadjlist = adjlist[:]        # copy adjlist to newadjlist
for i in range(v) :            # clear the newadjlist
    newadjlist[i] = []

for i in range(v) :
    for e in adjlist[i] :
        newadjlist[e-1].append(i+1)        # - and +

print 'after transposing :'
for i in range(v) :
    print i+1, ' ', newadjlist[i]

说明： 这个程序关键是列表的复制和清空，以及对于索引的使用（列表是从0开始计数，但是我们图的结点是从1开始标号的！