breadth first path. java here is the question I need to answer correctly. here b
ID: 3604292 • Letter: B
Question
breadth first path. java
here is the question I need to answer correctly. here below I am also attaching the pictures of related content so that it could be useful for u to answer. please post the picture of output with answer
The Wiener index of a vertex is the sum of the shortest path distances between v and all other vertices. The Wiener index of a graph G is the sum of the shortest path distances over all pairs of vertices. It's used by mathematical chemists (vertices atoms, edges bonds) Modify BreadthFirstPaths.java to return the Wiener index of a graph. Find the shortest path distance for each pair of vertices, and sum all the paths. Start with tinyCG.txt, an easy graph, which you can do by hand to check your algorithm. Then generate the Wiener Index for Wiener.txt. Submit your .java program and the Index. The files are on BlackboardExplanation / Answer
1.
import java.util.InputMismatchException;
2.import java.util.LinkedList;
3.import java.util.Queue;
4.import java.util.Scanner;
5.
6.public class BFS
7.{
8.
9. private Queue<Integer> queue;
10.
11. public BFS()
12. {
13. queue = new LinkedList<Integer>();
14. }
15.
16. public void bfs(int adjacency_matrix[][], int source)
17. {
18. int number_of_nodes = adjacency_matrix[source].length - 1;
19.
20. int[] visited = new int[number_of_nodes + 1];
21. int i, element;
22.
23. visited[source] = 1;
24. queue.add(source);
25.
26. while (!queue.isEmpty())
27. {
28. element = queue.remove();
29. i = element;
30. System.out.print(i + " ");
31. while (i <= number_of_nodes)
32. {
33. if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
34. {
35. queue.add(i);
36. visited[i] = 1;
37. }
38. i++;
39. }
40. }
41. }
42.
43. public static void main(String... arg)
44. {
45. int number_no_nodes, source;
46. Scanner scanner = null;
47.
48. try
49. {
50. System.out.println("Enter the number of nodes in the graph");
51. scanner = new Scanner(System.in);
52. number_no_nodes = scanner.nextInt();
53.
54. int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
55. System.out.println("Enter the adjacency matrix");
56. for (int i = 1; i <= number_no_nodes; i++)
57. for (int j = 1; j <= number_no_nodes; j++)
58. adjacency_matrix[i][j] = scanner.nextInt();
59.
60. System.out.println("Enter the source for the graph");
61. source = scanner.nextInt();
62.
63. System.out.println("The BFS traversal of the graph is ");
64. BFS bfs = new BFS();
65. bfs.bfs(adjacency_matrix, source);
66.
67. } catch (InputMismatchException inputMismatch)
68. {
69. System.out.println("Wrong Input Format");
70. }
71. scanner.close();
72. }
73.}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.