def makeAdjacencyList():
al = {}
al[1] = [2, 4]
al[2] = [4, 5]
al[3] = [1, 6]
al[4] = [5, 6, 7, 3]
al[5] = [7]
al[6] = []
al[7] = [6]
return al
class Vertex(object):
def __init__(self):
self.known = False
self.dist = None
self.path = None
def initializeTable(adjacencyList, vertexAsStart):
T = {}
for vrtx in adjacencyList.iterkeys():
v = Vertex()
T[vrtx] = v
T[vertexAsStart].dist = 0
return T
def findShortestPathInUnweightedGraph(adjacencyList):
T = initializeTable(adjacencyList, 3)
vertexs = adjacencyList.keys()
currDist = 0
for i in vertexs:
for v in vertexs:
if T[v].known == False and T[v].dist == currDist:
T[v].known = True
for w in adjacencyList[v]:
if T[w].dist == None:
T[w].dist = currDist + 1
T[w].path = v
currDist += 1
return T
adjacencyList = makeAdjacencyList()
T = findShortestPathInUnweightedGraph(adjacencyList)
dct = {}
for vrtx, attrs in T.iteritems():
dct.setdefault(attrs.dist, [])
dct[attrs.dist].append(vrtx)
print dct
for vrtx, attrs in T.iteritems():
print vrtx, attrs.known, attrs.dist, attrs.path
{0: [3], 1: [1, 6], 2: [2, 4], 3: [5, 7]}
1 True 1 3
2 True 2 1
3 True 0 None
4 True 2 1
5 True 3 2
6 True 1 3
7 True 3 4
