Skip to content

Commit 4d7ee24

Browse files
EklavyaPrasadEklavyaPrasad
committed
Added graph algorithms in java folder
1 parent fd075fd commit 4d7ee24

4 files changed

Lines changed: 247 additions & 0 deletions

File tree

‎java/Graphs/articulationPoint.java‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package Graphs;
2+
3+
import java.util.*;
4+
5+
public class articulationPoint {
6+
7+
private static void findArticulationPoints(ArrayList<ArrayList<Integer>> adj, int N) {
8+
9+
boolean vis[] = new boolean[N];
10+
int time[] = new int[N];
11+
int low[] = new int[N];
12+
int timer = 0;
13+
14+
boolean articulationPoints[] = new boolean[N];
15+
16+
for (int i = 0; i < N; i++) {
17+
if (!vis[i]) {
18+
dfs(i, -1, adj, vis, time, low, timer, articulationPoints);
19+
}
20+
}
21+
for (int i = 0; i < N; i++) {
22+
if (articulationPoints[i] == true)
23+
System.out.println(i);
24+
}
25+
}
26+
27+
private static void dfs(int node, int par, ArrayList<ArrayList<Integer>> adj, boolean vis[], int time[], int low[], int timer, boolean[] articulationPoints) {
28+
29+
vis[node] = true;
30+
time[node] = low[node] = timer++;
31+
int child = 0;
32+
33+
for (Integer it : adj.get(node)) {
34+
if (it == par)
35+
continue;
36+
37+
if (!vis[it]) {
38+
39+
dfs(it, node, adj, vis, time, low, timer, articulationPoints);
40+
low[node] = Math.min(low[node], low[it]);
41+
42+
if (low[it] >= time[node] && par != -1) {
43+
articulationPoints[node] = true;
44+
}
45+
child++;
46+
} else {
47+
low[node] = Math.min(low[node], time[it]);
48+
}
49+
}
50+
if (par != -1 && child > 1)
51+
articulationPoints[node] = true;
52+
}
53+
54+
public static void main(String args[]) {
55+
int n = 5;
56+
ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
57+
58+
for (int i = 0; i < n; i++)
59+
adj.add(new ArrayList<Integer>());
60+
61+
adj.get(0).add(1);
62+
adj.get(1).add(0);
63+
64+
adj.get(0).add(2);
65+
adj.get(2).add(0);
66+
67+
adj.get(1).add(2);
68+
adj.get(2).add(1);
69+
70+
adj.get(1).add(3);
71+
adj.get(3).add(1);
72+
73+
adj.get(3).add(4);
74+
adj.get(4).add(3);
75+
76+
articulationPoint obj = new articulationPoint();
77+
obj.findArticulationPoints(adj, n);
78+
79+
}
80+
}

‎java/Graphs/bellmanfordAlgo.java‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
package Graphs;
2+
3+
import java.util.*;
4+
5+
public class bellmanfordAlgo {
6+
void isNegativeCycle(ArrayList<Node> adj, int N, int source) {
7+
8+
int dist[] = new int[N];
9+
10+
for (int i = 0; i < N; i++) {
11+
dist[i] = 1000000;
12+
}
13+
dist[source] = 0;
14+
15+
for (int i = 0; i < N - 1; i++) {
16+
for (Node node : adj) {
17+
if (dist[node.getU()] + node.getWeight() < dist[node.getV()]) {
18+
dist[node.getV()] = dist[node.getU()] + node.getWeight();
19+
}
20+
}
21+
}
22+
23+
boolean flag = false;
24+
for (Node node : adj) {
25+
if (dist[node.getU()] + node.getWeight() < dist[node.getV()]) {
26+
System.out.println("Graph contains negative cycle");
27+
flag = true;
28+
break;
29+
}
30+
}
31+
32+
if (!flag) {
33+
for (int i = 0; i < N; i++) {
34+
System.out.println(i + " " + dist[i]);
35+
}
36+
}
37+
}
38+
39+
public static void main(String args[]) {
40+
int n = 6;
41+
ArrayList<Node> adj = new ArrayList<Node>();
42+
43+
adj.add(new Node(3, 2, 6));
44+
adj.add(new Node(5, 3, 1));
45+
adj.add(new Node(0, 1, 5));
46+
adj.add(new Node(1, 5, -3));
47+
adj.add(new Node(1, 2, -2));
48+
adj.add(new Node(3, 4, -2));
49+
adj.add(new Node(2, 4, 3));
50+
51+
bellmanfordAlgo obj = new bellmanfordAlgo();
52+
obj.isNegativeCycle(adj, n, 0);
53+
54+
}
55+
}
56+
57+
class Node {
58+
private int u;
59+
private int v;
60+
private int weight;
61+
62+
Node(int _u, int _v, int _w) {
63+
u = _u;
64+
v = _v;
65+
weight = _w;
66+
}
67+
68+
Node() {
69+
}
70+
71+
int getV() {
72+
return v;
73+
}
74+
75+
int getU() {
76+
return u;
77+
}
78+
79+
int getWeight() {
80+
return weight;
81+
}
82+
83+
}

‎java/Graphs/cycleDetectionBfs.java‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package Graphs;
2+
3+
import java.util.*;
4+
5+
public class cycleDetectionBfs {
6+
7+
public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
8+
9+
boolean vis[] = new boolean[V + 1];
10+
boolean res = false;
11+
12+
for (int i = 1; i <= V; i++) {
13+
if (vis[i] == false) {
14+
res = isCycleDetected(i, vis, adj);
15+
}
16+
}
17+
18+
return res;
19+
}
20+
21+
public boolean isCycleDetected(int n, boolean vis[], ArrayList<ArrayList<Integer>> adj) {
22+
23+
Queue<Pair> q = new LinkedList<>();
24+
q.add(new Pair(n, -1));
25+
vis[n] = true;
26+
27+
while (!q.isEmpty()) {
28+
int node = q.peek().node;
29+
int par = q.peek().prev;
30+
q.remove();
31+
32+
for (Integer it : adj.get(node)) {
33+
if (vis[it] == false) {
34+
q.add(new Pair(it, node));
35+
vis[it] = true;
36+
} else if (it != par) {
37+
return true;
38+
}
39+
}
40+
}
41+
return false;
42+
}
43+
}
44+
45+
class Pair {
46+
int node, prev;
47+
48+
public Pair(int node, int prev) {
49+
this.node = node;
50+
this.prev = prev;
51+
}
52+
}

‎java/Graphs/cycleDetectionDfs.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package Graphs;
2+
3+
import java.util.*;
4+
5+
public class cycleDetectionDfs {
6+
7+
public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
8+
boolean vis[] = new boolean[V + 1];
9+
10+
for (int i = 1; i <= V + 1; i++) {
11+
if (vis[i] == false) {
12+
if (isCycleDetected(i, -1, vis, adj))
13+
return true;
14+
}
15+
}
16+
17+
return false;
18+
}
19+
20+
public boolean isCycleDetected(int n, int parent, boolean vis[], ArrayList<ArrayList<Integer>> adj) {
21+
vis[n] = true;
22+
for (Integer it : adj.get(n)) {
23+
if (vis[it] == false) {
24+
if (isCycleDetected(it, n, vis, adj))
25+
return true;
26+
} else if (it != parent)
27+
return true;
28+
}
29+
return false;
30+
}
31+
32+
}

0 commit comments

Comments
 (0)