鄰接表的python實現(xiàn)(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 "拓撲排序的結(jié)果： ", 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]
--------------------
拓撲排序的結(jié)果： [1, 2, 5, 4, 3, 7, 6]
