This action will force synchronization from 编程语言算法集/Python, which will overwrite any changes that you have made since you forked the repository, and can not be recovered!!!
Synchronous operation will process in the background and will refresh the page when finishing processing. Please be patient.
from collections import dequedef _input(message):return input(message).strip().split(" ")def initialize_unweighted_directed_graph(node_count: int, edge_count: int) -> dict[int, list[int]]:graph: dict[int, list[int]] = {}for i in range(node_count):graph[i + 1] = []for e in range(edge_count):x, y = (int(i) for i in _input(f"Edge {e + 1}: <node1> <node2> "))graph[x].append(y)return graphdef initialize_unweighted_undirected_graph(node_count: int, edge_count: int) -> dict[int, list[int]]:graph: dict[int, list[int]] = {}for i in range(node_count):graph[i + 1] = []for e in range(edge_count):x, y = (int(i) for i in _input(f"Edge {e + 1}: <node1> <node2> "))graph[x].append(y)graph[y].append(x)return graphdef initialize_weighted_undirected_graph(node_count: int, edge_count: int) -> dict[int, list[tuple[int, int]]]:graph: dict[int, list[tuple[int, int]]] = {}for i in range(node_count):graph[i + 1] = []for e in range(edge_count):x, y, w = (int(i) for i in _input(f"Edge {e + 1}: <node1> <node2> <weight> "))graph[x].append((y, w))graph[y].append((x, w))return graphif __name__ == "__main__":n, m = (int(i) for i in _input("Number of nodes and edges: "))graph_choice = int(_input("Press 1 or 2 or 3 \n""1. Unweighted directed \n""2. Unweighted undirected \n""3. Weighted undirected \n")[0])g = {1: initialize_unweighted_directed_graph,2: initialize_unweighted_undirected_graph,3: initialize_weighted_undirected_graph,}[graph_choice](n, m)"""--------------------------------------------------------------------------------Depth First Search.Args : G - Dictionary of edgess - Starting NodeVars : vis - Set of visited nodesS - Traversal Stack--------------------------------------------------------------------------------"""def dfs(G, s):vis, S = {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 - Traversal Stack--------------------------------------------------------------------------------"""def bfs(G, s):vis, Q = {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--------------------------------------------------------------------------------"""def topo(G, ind=None, Q=None):if Q is 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 = input().strip()a = []for i in range(n):a.append(map(int, input().strip().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 range(n)]for k in range(n):for i in range(n):for j in range(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]] = ureturn dist"""--------------------------------------------------------------------------------Accepting Edge listVars : n - Number of nodesm - Number of edgesReturns : l - Edge listn - Number of Nodes--------------------------------------------------------------------------------"""def edglist():n, m = map(int, input().split(" "))edges = []for i in range(m):edges.append(map(int, input().split(" ")))return edges, 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 = [{i} for i in range(1, n + 1)]while True:if len(s) == 1:breakprint(s)x = E.pop()for i in range(len(s)):if x[0] in s[i]:breakfor j in range(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
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。