//Quick_sort

package first_project;

import java.util.*;

public class Quicksort {

public static void quicksort(int[] arr, int low,

int high) {
if (low < high) {
int pindex = partition(arr, low, high);
quicksort(arr, low, pindex-1);
quicksort(arr, pindex + 1, high);

}
}

public static int partition(int[] arr, int low,

int high) {

int p,i,j,temp;
p=arr[low];
i=low+1;
j=high;

while(low<high)
{
while(arr[i]<=p && i<high)
i++;

while(arr[j]>p)
j--;

if(i<j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
else
{
temp=arr[low];
arr[low]=arr[j];
 arr[j]=temp;
return j;
}
}
return j;
}

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);
System.out.println("Eneter number of
elements");
int n = scan.nextInt();
int[] arr = new int[n];
System.out.println("Enter the elments");
for (int i = 0; i < n; i++) {
arr[i] = scan.nextInt();
}
System.out.println("original array" +
Arrays.toString(arr));
long starttime = System.nanoTime();
quicksort(arr, 0, arr.length - 1);
long endtime = System.nanoTime();
System.out.println("sorted array" +
Arrays.toString(arr));
double timeElapsed = (endtime - starttime) /
1e6;
System.out.println("Time complexity:" +
timeElapsed + " milliseconds");
scan.close();

//Flyoids ALgorithm

package first_project;

import java.util.Scanner;

public class floyd {

 public static void main(String[] args) {
int a[][] = new int[10][10];
int n, i, j;
System.out.println("enter the number of
vertices");
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
System.out.println("Enter the weighted
matrix");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = sc.nextInt();

for (int k = 1; k <= n; k++)

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = Math.min(a[i][j], a[i]
[k] + a[k][j]);

System.out.println("The shortest path matrix

is");
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
System.out.print(a[i][j] + " ");
}

System.out.println();
}
sc.close();
}}

//BFS traversal

package second_project;

import java.util.LinkedList;

//import java.util.*;

import java.util.Queue;
import java.util.Scanner;

//Bfs traversal using adj matrix

//it is also called level order travesal of tree

public class Bfs_traversal {

public static void main(String args[]) {

Scanner scan = new Scanner(System.in);

System.out.println("Enter the number of vertices:");

int v = scan.nextInt();

int[][] adj = new int[v][v];

System.out.println("Enter the adj maatrix:");

for (int i = 0; i < v; i++)

for (int j = 0; j < v; j++)

adj[i][j] = scan.nextInt();

System.out.println("Enter the start vertex:");

int s = scan.nextInt();

boolean[] vis = new boolean[v];

vis[s] = true;

Queue<Integer> queue = new LinkedList<>();

queue.add(s);

while (!queue.isEmpty()) {

int cv = queue.poll();

System.out.print(cv + " ");

for (int i = 0; i < v; i++) {

if (adj[cv][i] == 1 && !vis[i]) {

vis[i] = true;

queue.add(i);

}
 }

}
//DFS
package second_project;

import java.util.*;

//Implemetation of DFS traversal using adjacency

matrix.
//it gives preorder raversal of the graph.
public class Dfs_traversal {
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of
vertices");
int v = scan.nextInt();
int[][] adj = new int[v][v];
System.out.println("Enter the adj matrix");
for (int i = 0; i < v; i++) {
for (int j = 0; j < v; j++) {
adj[i][j] = scan.nextInt();
}
}
System.out.println("Enter the start vertex");
int s = scan.nextInt();
boolean[] vis = new boolean[v];
for (int i = 0; i < v; i++) {
if (!vis[i])
dfs(i, v, adj, vis);
}
scan.close();

public static void dfs(int s, int v, int[][] adj,

boolean[] vis) {
vis[s] = true;
for (int i = 0; i < v; i++) {
if (adj[s][i] == 1 && !vis[i]) {
dfs(i, v, adj, vis);
}
 }
System.out.print(s + " ");
}

//Below code gives postoreder traversal of the

graaph;
//reversing the postorder traversal gives
tropological sort of thr graph;
//code is below
//public static void dfs(int s,int v,int[][]
adj,boolean[] vis)
//{
// vis[s]=true;
// for(int i=0;i<v;i++)
// {
// if(adj[s][i]==1&&!vis[i])
// {
// dfs(i,v,adj,vis);
// }
// System.out.print(s+" ");
// }
//}

//PRIMS

package first_project;

import java.util.Scanner;

public class prims {

public static void main(String[] args) {

int w[][] = new int[10][10];
int n, i, j, s, k = 0;
int min;
int sum = 0;
int u = 0, v = 0;
 boolean flag = false;
int sol[] = new int[10];

System.out.println("Enter the number of

vertices");
Scanner sc = new Scanner(System.in);
n = sc.nextInt();

for (i = 1; i <= n; i++)

sol[i] = 0;

System.out.println("Enter the weighted

graph");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
w[i][j] = sc.nextInt();

System.out.println("Enter the source

vertex");
s = sc.nextInt();
sol[s] = 1;
k = 1;

while (k <= n - 1) {
min = Integer.MAX_VALUE;

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)
if (sol[i] == 1 && sol[j] == 0
&& w[i][j] != 0) // Check if weight is not zero
if (i != j && min > w[i][j])
{
min = w[i][j];
u = i;
v = j;
}

if (min == Integer.MAX_VALUE) {
System.out.println("No spanning
tree");
return; // Exit the program
}

sol[v] = 1;
 sum = sum + min;
k++;
System.out.println(u + "->" + v + "=" +
min);
}

for (i = 1; i <= n; i++)

if (sol[i] == 0)
flag = true;

if (flag)
System.out.println("No spanning tree");
else
System.out.println("The cost of minimum
spanning tree is " + sum);

sc.close();
}
}

//Krushkals

package first_project;

import java.util.Scanner;

public class kruskal {

int parent[] = new int[10];

int find(int m) {
int p = m;
while (parent[p] != 0)
p = parent[p];
return p;
}

void union(int i, int j) {

if (i < j)
parent[i] = j;
else
parent[j] = i;
 }

void krkl(int[][] a, int n) {

int u = 0, v = 0, min, k = 0, i, j, sum = 0;
while (k < n - 1) {

min = 99;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (a[i][j] < min && i != j) {
min = a[i][j];
u = i;
v = j;
}
i = find(u);
j = find(v);
if (i != j) {
union(i, j);
System.out.println("(" + u + "," + v
+ ")" + "=" + a[u][v]);
sum = sum + a[u][v];
k++;
}
a[u][v] = a[v][u] = 99;
}
System.out.println("The cost of minimum
spanning tree = " + sum);
}

public static void main(String[] args) {

int a[][] = new int[10][10];
int i, j;
System.out.println("Enter the number of
vertices of the graph");
Scanner sc = new Scanner(System.in);
int n;
n = sc.nextInt();
System.out.println("Enter the wieghted
matrix");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = sc.nextInt();
kruskal k = new kruskal();
k.krkl(a, n);
 sc.close();
}
}