Graph Algorithms(1)

邻接表的python实现(adjacency list)

def makeAdjacencyList():
    al = {}
    al[1] = [2, 4, 3]
    al[2] = [4, 5]
    al[3] = [6]
    al[4] = [6, 7, 3]
    al[5] = [4, 7]
    al[6] = []
    al[7] = [6]
    return al

拓扑排序

#入度
Ind = [0, 0, 1, 2, 3, 1, 3, 2]
# topo sort
def enqueue(v, q):
    q.append(v)

def dequeue(q):
    return q.pop(0)

def isEmpty(q):
    if len(q) == 0:
        return True
    return False

import time

def topoSort(al, Ind):
    q = []
    toBeAvoided = []
    topoNum = [0]*8
    counter = 0
    for i in range(1, 8):
        if Ind[i] == 0:
            enqueue(i, q)
    print "第一步, q = ", q
    while not isEmpty(q):
        #time.sleep(2)
        print "q = ", q
        while not isEmpty(q):
            v = dequeue(q)
            toBeAvoided.append(v)
            print "弹出v =", v
            counter += 1
            topoNum[v] = counter
            for w in al[v]:
                Ind[w ] -= 1
            print "Ind = ", Ind
        for i in range(1, 8):
            if Ind[i] == 0 and i not in toBeAvoided:
                enqueue(i, q)
                print "将%d压入q"%i
    return topoNum

al = makeAdjacencyList()
res = topoSort(al, Ind)[1:]
print "--------------------"
print "拓扑排序的结果： ", res 

第一步, q =  [1]
q =  [1]
弹出v = 1
Ind =  [0, 0, 0, 1, 2, 1, 3, 2]
将2压入q
q =  [2]
弹出v = 2
Ind =  [0, 0, 0, 1, 1, 0, 3, 2]
将5压入q
q =  [5]
弹出v = 5
Ind =  [0, 0, 0, 1, 0, 0, 3, 1]
将4压入q
q =  [4]
弹出v = 4
Ind =  [0, 0, 0, 0, 0, 0, 2, 0]
将3压入q
将7压入q
q =  [3, 7]
弹出v = 3
Ind =  [0, 0, 0, 0, 0, 0, 1, 0]
弹出v = 7
Ind =  [0, 0, 0, 0, 0, 0, 0, 0]
将6压入q
q =  [6]
弹出v = 6
Ind =  [0, 0, 0, 0, 0, 0, 0, 0]
--------------------
拓扑排序的结果：  [1, 2, 5, 4, 3, 7, 6]