azex bih kada bih skuzila zasto odjednom ne da formatirati kod - skuzila sam minutu nakon sto je proslo vrijeme za editanje
mrkva
DIJKSTRA MST
hint: ako cete imati u MST zadatku time exceeded error na jednom od zadataka i ako ste u NewAdjMatrix copy stavili u True, probajte promijeniti u False, tj. ostaviti default vrijednost
dobiveni kod
import collections
import copy
def _NewAdjMatrix(G, copy=False):
am = {}
for u in G:
am[u] = {}
for v in G[u]:
if copy:
am[u][v] = G[u][v]
else:
am[u][v] = 0
return am
def _FindCyclesMatrix(G):
visited = []
cycs = []
S = collections.deque()
for u0 in G:
if u0 not in visited:
P = _NewAdjMatrix(G)
_FindCyclesMatrix_r(G, P, u0, visited, S, cycs)
return cycs
def _FindCyclesMatrix_r(G, P, u, visited, S, cycs):
visited.append(u)
S.append(u)
n = []
for v in G[u]:
if G[u][v] != 0: n.append(v)
for v in n:
if v not in S:
P[u][v] = P[v][u] = 1
_FindCyclesMatrix_r(G, P, v, visited, S, cycs)
else:
if P[u][v] != 1: # prevents turning back to the previous vertex in undirected graphs
c = []
for vx in reversed(S):
c.append(vx)
if vx is v:
break
if c not in cycs:
cycs.append(c)
S.pop()
def _adj(G, u):
a = []
for v in G[u]:
if G[u][v] != 0:
a.append(v)
return a
def _edges(G):
e = {}
for u in G:
for v in _adj(G, u):
if not (v, u) in e.keys():
e[(u, v)] = G[u][v]
return e
def FindCycle(G: dict) -> dict:
c = _FindCyclesMatrix(G)
E2 = {}
E = _edges(G)
if len(c) > 0:
c = c[0]
cp = [(c[-1], c[0])]
for i in range(len(c) - 1):
cp.append((c[i], c[i + 1]))
for cpi in cp:
E2 = {**E2, **dict(filter(lambda x: x[0][0] in cpi and x[0][1] in cpi, E.items()))}
return E2
#za testiranje#
G = {'a': {'a': 0, 'b': 2, 'c': 3, 'd': 0},
'b': {'a': 2, 'b': 0, 'c': 5, 'd': 0},
'c': {'a': 3, 'b': 5, 'c': 0, 'd': 0},
'd': {'a': 0, 'b': 0, 'c': 0, 'd': 0}}
