Computermathematik Zwei
Übung Drei
8)
G = Graph({1:[2], 2:[3,4,5,6],3:[4],5:[6]})
G.plot()
|
|
9)
M=sum([[G.shortest_path(a,b) for a in G.vertices()] for b in G.vertices()],[]) #flatten list
N=[len(x) for x in M]
print "Längste Kürzeste Weg:",M[N.index(max(N))]
one of the longest shortest paths: [3, 2, 1] one of the longest shortest paths: [3, 2, 1] |
print "Längste Weg durch G"
(G.longest_path()).plot()
Längste Weg durch G Längste Weg durch G |
print "Ist G ein Baum:", G.is_tree()
list=[]
for i in range (1,7):
list.append(len(G.neighbors(i)))
maximal=max(list)
for i in range (len(list)):
if (list[i]==maximal):
print "Knoten von Maximalen Grad in G ist Knoten:", (i+1)
Ist G ein Baum: False Knoten von Maximalen Grad in G ist Knoten: 2 Ist G ein Baum: False Knoten von Maximalen Grad in G ist Knoten: 2 |
(G.complement()).plot()
|
|
10)
M2=2*graphs.PetersenGraph()
M2.plot()
|
|
def find_path(graph,start,end):
queue=[]
queue2=[]
queue3=[]
queue4=[]
var=[]
var=graph.neighbors(start)
if (end in var):
return "There's a path"
else:
queue=graph.neighbors(start)
for i in range(0,len(queue)):
queue2=graph.neighbors(queue[i])
if (end in queue2):
return "There is a path"
else:
for i in range (0,len(queue2)):
queue3=graph.neighbors(queue2[i])
if (end in queue3):
return "There is a path"
else:
for i in range(len(queue3)):
queue4=graph.neighbors(queue3[i])
if (end in queue4):
return "There is a path"
return "No Path found"
|
|
print(find_path(M2,0,15))
print(find_path(M2,0,9))
No Path found There is a path No Path found There is a path |
11)
M=graphs.PetersenGraph()
M.plot()
|
|
def bfs(g, start):
queue, enqueued = deque([(None, start)]), set([start])
while queue:
parent, n = queue.popleft()
yield parent, n
new = set(g[n]) - enqueued
enqueued |= new
queue.extend([(n, child) for child in new])
|
|
from collections import deque
def shortest_path(g, start, end):
parents = {}
for parent, child in bfs(g, start):
parents[child] = parent
if child == end:
revpath = [end]
while True:
parent = parents[child]
revpath.append(parent)
if parent == start:
break
child = parent
return list(reversed(revpath))
return "None # or raise appropriate exception"
|
|
shortest_path(M,0,9)
[0, 4, 9] [0, 4, 9] |
|
|