from __future__ import print_functiontry:raw_input # Python 2except NameError:raw_input = input # Python 3try:xrange # Python 2except NameError:xrange = range # Python 3# Accept No. of Nodes and edgesn, m = map(int, raw_input().split(" "))# Initialising Dictionary of edgesg = {}for i in xrange(n):g[i + 1] = []"""--------------------------------------------------------------------------------Accepting edges of Unweighted Directed Graphs--------------------------------------------------------------------------------"""for _ in xrange(m):x, y = map(int, raw_input().split(" "))g[x].append(y)"""--------------------------------------------------------------------------------Accepting edges of Unweighted Undirected Graphs--------------------------------------------------------------------------------"""for _ in xrange(m):x, y = map(int, raw_input().split(" "))g[x].append(y)g[y].append(x)"""--------------------------------------------------------------------------------Accepting edges of Weighted Undirected Graphs--------------------------------------------------------------------------------"""for _ in xrange(m):x, y, r = map(int, raw_input().split(" "))g[x].append([y, r])g[y].append([x, r])"""--------------------------------------------------------------------------------Depth First Search.Args : G - Dictionary of edgess - Starting NodeVars : vis - Set of visited nodesS - Traversal Stack--------------------------------------------------------------------------------"""def dfs(G, s):vis, S = set([s]), [s]print(s)while S:flag = 0for i in G[S[-1]]:if i not in vis:S.append(i)vis.add(i)flag = 1print(i)breakif not flag:S.pop()"""--------------------------------------------------------------------------------Breadth First Search.Args : G - Dictionary of edgess - Starting NodeVars : vis - Set of visited nodesQ - Traveral Stack--------------------------------------------------------------------------------"""from collections import dequedef bfs(G, s):vis, Q = set([s]), deque([s])print(s)while Q:u = Q.popleft()for v in G[u]:if v not in vis:vis.add(v)Q.append(v)print(v)"""--------------------------------------------------------------------------------Dijkstra's shortest path AlgorithmArgs : G - Dictionary of edgess - Starting NodeVars : dist - Dictionary storing shortest distance from s to every other nodeknown - Set of knows nodespath - Preceding node in path--------------------------------------------------------------------------------"""def dijk(G, s):dist, known, path = {s: 0}, set(), {s: 0}while True:if len(known) == len(G) - 1:breakmini = 100000for i in dist:if i not in known and dist[i] < mini:mini = dist[i]u = iknown.add(u)for v in G[u]:if v[0] not in known:if dist[u] + v[1] < dist.get(v[0], 100000):dist[v[0]] = dist[u] + v[1]path[v[0]] = ufor i in dist:if i != s:print(dist[i])"""--------------------------------------------------------------------------------Topological Sort--------------------------------------------------------------------------------"""from collections import dequedef topo(G, ind=None, Q=[1]):if ind is None:ind = [0] * (len(G) + 1) # SInce oth Index is ignoredfor u in G:for v in G[u]:ind[v] += 1Q = deque()for i in G:if ind[i] == 0:Q.append(i)if len(Q) == 0:returnv = Q.popleft()print(v)for w in G[v]:ind[w] -= 1if ind[w] == 0:Q.append(w)topo(G, ind, Q)"""--------------------------------------------------------------------------------Reading an Adjacency matrix--------------------------------------------------------------------------------"""def adjm():n, a = raw_input(), []for i in xrange(n):a.append(map(int, raw_input().split()))return a, n"""--------------------------------------------------------------------------------Floyd Warshall's algorithmArgs : G - Dictionary of edgess - Starting NodeVars : dist - Dictionary storing shortest distance from s to every other nodeknown - Set of knows nodespath - Preceding node in path--------------------------------------------------------------------------------"""def floy(A_and_n):(A, n) = A_and_ndist = list(A)path = [[0] * n for i in xrange(n)]for k in xrange(n):for i in xrange(n):for j in xrange(n):if dist[i][j] > dist[i][k] + dist[k][j]:dist[i][j] = dist[i][k] + dist[k][j]path[i][k] = kprint(dist)"""--------------------------------------------------------------------------------Prim's MST AlgorithmArgs : G - Dictionary of edgess - Starting NodeVars : dist - Dictionary storing shortest distance from s to nearest nodeknown - Set of knows nodespath - Preceding node in path--------------------------------------------------------------------------------"""def prim(G, s):dist, known, path = {s: 0}, set(), {s: 0}while True:if len(known) == len(G) - 1:breakmini = 100000for i in dist:if i not in known and dist[i] < mini:mini = dist[i]u = iknown.add(u)for v in G[u]:if v[0] not in known:if v[1] < dist.get(v[0], 100000):dist[v[0]] = v[1]path[v[0]] = u"""--------------------------------------------------------------------------------Accepting Edge listVars : n - Number of nodesm - Number of edgesReturns : l - Edge listn - Number of Nodes--------------------------------------------------------------------------------"""def edglist():n, m = map(int, raw_input().split(" "))l = []for i in xrange(m):l.append(map(int, raw_input().split(' ')))return l, n"""--------------------------------------------------------------------------------Kruskal's MST AlgorithmArgs : E - Edge listn - Number of NodesVars : s - Set of all nodes as unique disjoint sets (initially)--------------------------------------------------------------------------------"""def krusk(E_and_n):# Sort edges on the basis of distance(E, n) = E_and_nE.sort(reverse=True, key=lambda x: x[2])s = [set([i]) for i in range(1, n + 1)]while True:if len(s) == 1:breakprint(s)x = E.pop()for i in xrange(len(s)):if x[0] in s[i]:breakfor j in xrange(len(s)):if x[1] in s[j]:if i == j:breaks[j].update(s[i])s.pop(i)break# find the isolated node in the graphdef find_isolated_nodes(graph):isolated = []for node in graph:if not graph[node]:isolated.append(node)return isolated
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。