import java.util.*;
class grph {
int vrt;
List<Integer> adj[];
public grph(int vrt)
{
this.vrt = vrt;
adj = new ArrayList[vrt];
for (int p= 0; p < vrt; p++)
adj[p] = new ArrayList<Integer>();
}
public void add(int u, int v)
{
adj[u].add(v);
}
public void BfsTopologicalSort()
{
int Indegree[] = new int[vrt];
for (int p = 0; p < vrt; p++) {
ArrayList<Integer> temp
= (ArrayList<Integer>)adj[p];
for (int node : temp) {
Indegree[node]++;
}
}
Queue<Integer> q
= new LinkedList<Integer>();
for (int p = 0; p < vrt; p++) {
if (Indegree[p] == 0)
q.add(p);
}
int c = 0;
Vector<Integer> TopOrder = new Vector<Integer>();
while (!q.isEmpty()) {
int u = q.poll();
TopOrder.add(u);
for (int node : adj[u]) {
if (--Indegree[node] == 0)
q.add(node);
}
c++;
}
if (c != vrt) {
System.out.println(
"cycle iS PRESENT IN the graph");
return;
}
for (int p : TopOrder) {
System.out.print(p + " ");
}
}
}
class Main {
public static void main(String args[])
{
grph gp = new grph(14);
gp.add(12,9);
gp.add(10,13);
gp.add(9,11);
gp.add(9,10);
gp.add(8,7);
gp.add(6,5);
gp.add(5,12);
gp.add(5,8);
gp.add(4,7);
gp.add(3,13);
gp.add(3,6);
gp.add(3,2);
gp.add(2,6);
gp.add(2,9);
gp.add(2,5);
gp.add(1,8);
gp.add(1,4);
gp.add(1,2);
gp.add(0,11);
gp.add(0,4);
gp.add(0,5);
System.out.println(
"BFS _Topological Sort");
gp.BfsTopologicalSort();
}
}
As per the program i assigned
edge m is taken 0
edge n is taken 1
edge o is taken 2
edge p is taken 3
edge q is taken 4
edge r is taken 5
edge s is taken 6
edge t is taken 7
edge u is taken 8
edge v is taken 9
edge w is taken 10
edge x is taken 11
edge y is taken 12
edge z is taken 13
please take accordingly bro and give me thumbs up
Write a java program to do BFS topological sort . your program must be able to...
In the following graph, write a Java program using Topological Sort. please write java code and show me the output. Thank you :) b.
1) A Java program that implements an insertion sort algorithm. (InsertionSort.java): Must include the proper comments in the code. 2) A report in pdf. It contains: a) the pseudocode of the insertion sort algorithm and assertions between lines of the algorithm. b) As insertion sort has a nested-loop of two layers, you need to put one assertion in each loop. c) a proof of the partial correctness of the algorithm using mathematical induction c.1) prove the correctness of the two...
Write a Java program to implement Counting Sort and write a driver to test it. Note: use random number generator to generate your input with n = 10, 50, and 100. Verify that the running time is O(n).
Write a java program to sort arrays using 3 different methods: Bubble Sort, Selection Sort and Insertion Sort. The numbers to be sorted will be obtained using a library function which generates pseudo-random numbers. TO Do 1. Fill an array with 140 real numbers between 0.00 and 945.00. Generate the numbers using the subroutine that generates random numbers. Make a spare copy of the array; you will need it later. 2. Call a subroutine to print the contents of the...
JAVA question: Write a program to sort the following US States in their natural order : Missouri, Illinois, California, Washington, Maine. HINT : Create a List of the States and user the sort method of the Collections interface. Please copy and paste your code below.
need help!! java eclipse Write a program to implement bubble sort, insertion sort, selection sort, merge sort and quick sort (pivot - first index) algorithms. a) Compute the CPU processing time for all the algorithms for varying input sizes as follows: N-10, 103, 10, 10, and 106 b) Use a random number generator to generate the inputs. Obtain the inputs from the following input ranges: 1- 10, 1 -10, 1 - 10, 1 12 10 c) Write down your results...
Write a JAVA program to sort a given array of integers (1 Dimensional) in ascending order (from smallest to largest). You can either get the array as input or hardcode it inside your program.
Write a program in Java that obtains the execution time of selection sort, insertion sort, bubble sort, merge sort, quick sort, and radix sort. Your program should test all sort methods for input sizes of 10000, 20000, 30000, 40000, 50000, and 60000. The selection sort, bubble sort, and radix sort should also be tested for input sizes 100000 and 200000. Your program should create the data that is sorted from randomly generated integers and should output the results in a...
Write a Java program with a single-dimension array that holds 11 integer numbers and sort the array using a bubble sort. Next, identify the median value of the 11 integers. Here are the steps your program must accomplish. algorithm (either flowchart or pseudocode) that you will use to write the program Step 1. Create an Place the algorithm in a Word document. 6. Ste the Step 2. Code the program in Eclipse and ensure the following steps are accomplished. 1....
1. Write a Java program to implement Counting Sort and write a driver to test it. Note: use random number generator to generate your input with n = 10, 50, and 100. Verify that the running time is O(n). 2. Write a Java program to implement Bucket Sort and write a driver to test it. Note: use random number generator to generate your input with n = 10, 50, and 100. Verify that the running time is O(n). 3. In...