Repository navigation
Expand file tree
/
Copy pathbfs.py
More file actions
112 lines (94 loc) · 2.42 KB
/
Copy pathbfs.py
File metadata and controls
112 lines (94 loc) · 2.42 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class Graph:
def __init__(self):
self.nodes = {}
def insertNode(self, u):
if u not in self.nodes:
self.nodes[u] = {}
def V(self):
return self.nodes.keys()
def adj(self, u):
if u in self.nodes:
return self.nodes[u]
def insertEdge(self, u, v, w=0):
if u not in self.nodes:
self.insertNode(u)
if v not in self.nodes:
self.insertNode(v)
self.nodes[u][v] = w
self.nodes[v][u] = w
def bfs(self, start):
S = [start]
visited = {}
for node in self.V():
visited[node] = False
visited[start] = True
while len(S) > 0:
u = S.pop(0)
for v in self.adj(u):
print "Start \t", u, " | Destination:\t", v
if not visited[v]:
visited[v] = True
S.append(v)
def __str__(self):
string = ""
for u in self.V():
string += (str(u) + "->" + str(self.adj(u)) + "\n")
return string
class OrientedGraph:
def __init__(self):
self.nodes = {}
def insertNode(self, u):
if u not in self.nodes:
self.nodes[u] = {}
def V(self):
return self.nodes.keys()
def adj(self, u):
if u in self.nodes:
return self.nodes[u]
def insertEdge(self, u, v, w=0):
if u not in self.nodes:
self.insertNode(u)
if v not in self.nodes:
self.insertNode(v)
self.nodes[u][v] = w
def bfs(self, start):
S = [start]
visited = {}
for node in self.V():
visited[node] = False
visited[start] = True
while len(S) > 0:
u = S.pop(0)
for v in self.adj(u):
print "Start \t", u, " | Destination:\t", v, " | Cost:\t", self.nodes[u][v]
if not visited[v]:
visited[v] = True
S.append(v)
def __str__(self):
string = ""
for u in self.V():
string += (str(u) + "->" + str(self.adj(u)) + "\n")
return string
def init():
print "Test for non-oriented graph"
graph = Graph()
for u in ['a', 'b', 'c', 'd', 'e', 'f']:
graph.insertNode(u)
for u, v in [('a', 'b'), ('a', 'd'), ('b', 'c'), ('d', 'a'), ('d', 'c'), ('d', 'e'), ('e', 'c'), ('e', 'f')]:
graph.insertEdge(u, v)
print
3F94
str(graph)
# Test bfs starting from a
graph.bfs('a')
print "---------------------------------------------"
print "\nTest for Oriented Graph"
graph = Graph()
for u in ['a', 'b', 'c', 'd', 'e', 'f']:
graph.insertNode(u)
for u, v, w in [('a', 'b', 3), ('a', 'd', 2), ('b', 'c', 0), ('d', 'a', 1), ('d', 'c', 6), ('d', 'e', 10), ('e', 'c', 1), ('e', 'f', 0)]:
graph.insertEdge(u, v, w)
print str(graph)
# Test bellman starting from a
graph.bfs('a')
return
if __name__ == '__main__':
init()