summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorHaidong Ji2020-07-16 21:06:20 -0500
committerHaidong Ji2020-07-16 21:06:20 -0500
commitd4da45aaeb3799ca813819086c53790e6cb3527d (patch)
treea078b9ed719e03310d026a21302dae5ec2bb44ef /src
parentdaaaba9cd6dcaa885c18b7597e2cdc19c2be9726 (diff)
BFS distance done. Following pseudo code, not too bad.
Diffstat (limited to 'src')
-rw-r--r--src/main/BFS.java53
1 files changed, 53 insertions, 0 deletions
diff --git a/src/main/BFS.java b/src/main/BFS.java
new file mode 100644
index 0000000..d56c134
--- /dev/null
+++ b/src/main/BFS.java
@@ -0,0 +1,53 @@
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.LinkedList;
+import java.util.Queue;
+import java.util.Scanner;
+
+public class BFS {
+ private static int distance(ArrayList<Integer>[] adj, int s, int t) {
+ int[] dist = new int[adj.length];
+ Arrays.fill(dist, -1);
+ dist[s] = 0;
+
+ bfs(adj, s, dist);
+
+ return dist[t];
+ }
+
+ private static void bfs(ArrayList<Integer>[] adj, int s, int[] dist) {
+ Queue<Integer> vertexQ = new LinkedList<>();
+ vertexQ.add(s);
+
+ while (!vertexQ.isEmpty()) {
+ int u = vertexQ.remove();
+ for (int i : adj[u]) {
+ if (dist[i] == -1) {
+ vertexQ.add(i);
+ dist[i] = dist[u] + 1;
+ }
+ }
+ }
+ }
+
+ public static void main(String[] args) {
+ Scanner scanner = new Scanner(System.in);
+ int n = scanner.nextInt();
+ int m = scanner.nextInt();
+ ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n];
+ for (int i = 0; i < n; i++) {
+ adj[i] = new ArrayList<Integer>();
+ }
+ for (int i = 0; i < m; i++) {
+ int x, y;
+ x = scanner.nextInt();
+ y = scanner.nextInt();
+ adj[x - 1].add(y - 1);
+ adj[y - 1].add(x - 1);
+ }
+ int x = scanner.nextInt() - 1;
+ int y = scanner.nextInt() - 1;
+ System.out.println(distance(adj, x, y));
+ }
+}
+