From f83de5ee51c1985a5ee98a587416af142cbd1e2d Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Thu, 16 Jul 2020 21:51:36 -0500 Subject: Graph BFS distance done. --- sources/bfs.py | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 sources/bfs.py (limited to 'sources') diff --git a/sources/bfs.py b/sources/bfs.py new file mode 100644 index 0000000..5d28baa --- /dev/null +++ b/sources/bfs.py @@ -0,0 +1,39 @@ +# Uses python3 + +import sys +import queue + + +def bfs(adj, s, dist): + q = queue.Queue() + q.put(s) + + while not q.empty(): + u = q.get() + for i in adj[u]: + if dist[i] == -1: + q.put(i) + dist[i] = dist[u] + 1 + + +def distance(adj, s, t): + dist = [-1] * len(adj) + dist[s] = 0 + + bfs(adj, s, dist) + + return dist[t] + + +if __name__ == '__main__': + input = sys.stdin.read() + data = list(map(int, input.split())) + n, m = data[0:2] + data = data[2:] + edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2])) + adj = [[] for _ in range(n)] + for (a, b) in edges: + adj[a - 1].append(b - 1) + adj[b - 1].append(a - 1) + s, t = data[2 * m] - 1, data[2 * m + 1] - 1 + print(distance(adj, s, t)) -- cgit v1.2.3