Skip to content

Commit 660653d

Browse files
giaunvgiaunv
committed
Graph in Data Structure
1 parent 421be35 commit 660653d

4 files changed

Lines changed: 98 additions & 22 deletions

File tree

datastructure-algorithm-java-examples/src/main/java/com/hellokoding/algorithm/BreadthFirstSearchOnGraph.java renamed to datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/BreadthFirstSearchOnGraph.java

Lines changed: 11 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,15 @@
1-
package com.hellokoding.algorithm;
2-
3-
import com.hellokoding.datastructure.GraphUndirectedByAdjacencyList;
1+
package com.hellokoding.datastructure;
42

53
import java.util.ArrayDeque;
64
import java.util.Queue;
75

8-
public class BreadthFirstSearchOnGraph {
9-
public void breadthFirstSearch(GraphUndirectedByAdjacencyList g, int startingVertex) {
10-
boolean[] visited = new boolean[g.getV()];
6+
public class BreadthFirstSearchOnGraph extends GraphUndirectedByAdjacencyList {
7+
public BreadthFirstSearchOnGraph(int V) {
8+
super(V);
9+
}
10+
11+
public void breadthFirstSearch(int startingVertex) {
12+
boolean[] visited = new boolean[V];
1113
Queue<Integer> queue = new ArrayDeque<>();
1214

1315
visited[startingVertex] = true;
@@ -17,7 +19,7 @@ public void breadthFirstSearch(GraphUndirectedByAdjacencyList g, int startingVer
1719
Integer currentVertex = queue.poll();
1820
System.out.printf("%d ", currentVertex);
1921

20-
for(Integer vertex : g.getAdjacencyList(currentVertex)) {
22+
for(Integer vertex : adjacencyList.get(currentVertex)) {
2123
if (!visited[vertex]) {
2224
visited[vertex] = true;
2325
queue.offer(vertex);
@@ -27,13 +29,13 @@ public void breadthFirstSearch(GraphUndirectedByAdjacencyList g, int startingVer
2729
}
2830

2931
public static void main(String[] args) {
30-
GraphUndirectedByAdjacencyList graph = new GraphUndirectedByAdjacencyList(5);
32+
BreadthFirstSearchOnGraph graph = new BreadthFirstSearchOnGraph(5);
3133
graph.addEdge(0, 1);
3234
graph.addEdge(1, 2);
3335
graph.addEdge(2, 0);
3436
graph.addEdge(1, 3);
3537
graph.addEdge(2, 4);
3638

37-
new BreadthFirstSearchOnGraph().breadthFirstSearch(graph, 0);
39+
graph.breadthFirstSearch(0);
3840
}
3941
}

datastructure-algorithm-java-examples/src/main/java/com/hellokoding/algorithm/DepthFirstSearchOnGraph.java renamed to datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/DepthFirstSearchOnGraph.java

Lines changed: 11 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,15 @@
1-
package com.hellokoding.algorithm;
2-
3-
import com.hellokoding.datastructure.GraphUndirectedByAdjacencyList;
1+
package com.hellokoding.datastructure;
42

53
import java.util.ArrayDeque;
64
import java.util.Deque;
75

8-
public class DepthFirstSearchOnGraph {
9-
public void depthFirstSearch(GraphUndirectedByAdjacencyList g, int startingVertex) {
10-
boolean[] visited = new boolean[g.getV()];
6+
public class DepthFirstSearchOnGraph extends GraphUndirectedByAdjacencyList {
7+
public DepthFirstSearchOnGraph(int V) {
8+
super(V);
9+
}
10+
11+
public void depthFirstSearch(int startingVertex) {
12+
boolean[] visited = new boolean[V];
1113
Deque<Integer> stack = new ArrayDeque<>();
1214

1315
visited[startingVertex] = true;
@@ -17,7 +19,7 @@ public void depthFirstSearch(GraphUndirectedByAdjacencyList g, int startingVerte
1719
Integer currentVertex = stack.pop();
1820
System.out.printf("%d ", currentVertex);
1921

20-
for(Integer vertex : g.getAdjacencyList(currentVertex)) {
22+
for(Integer vertex : adjacencyList.get(currentVertex)) {
2123
if (!visited[vertex]) {
2224
visited[vertex] = true;
2325
stack.push(vertex);
@@ -27,13 +29,13 @@ public void depthFirstSearch(GraphUndirectedByAdjacencyList g, int startingVerte
2729
}
2830

2931
public static void main(String[] args) {
30-
GraphUndirectedByAdjacencyList graph = new GraphUndirectedByAdjacencyList(5);
32+
DepthFirstSearchOnGraph graph = new DepthFirstSearchOnGraph(5);
3133
graph.addEdge(0, 2);
3234
graph.addEdge(1, 2);
3335
graph.addEdge(1, 0);
3436
graph.addEdge(1, 3);
3537
graph.addEdge(2, 4);
3638

37-
new DepthFirstSearchOnGraph().depthFirstSearch(graph, 0);
39+
graph.depthFirstSearch(0);
3840
}
3941
}

datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/GraphDirectedDetectCycle.java renamed to datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/GraphDirectedDetectCycleByDFS.java

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,9 @@
11
package com.hellokoding.datastructure;
22

3-
import java.util.ArrayList;
43
import java.util.List;
54

6-
public class GraphDirectedDetectCycle extends GraphDirectedByAdjacencyList {
7-
public GraphDirectedDetectCycle(int V) {
5+
public class GraphDirectedDetectCycleByDFS extends GraphDirectedByAdjacencyList {
6+
public GraphDirectedDetectCycleByDFS(int V) {
87
super(V);
98
}
109

@@ -40,7 +39,7 @@ public boolean hasCycle() {
4039
}
4140

4241
public static void main(String[] args) {
43-
GraphDirectedDetectCycle graph = new GraphDirectedDetectCycle(3);
42+
GraphDirectedDetectCycleByDFS graph = new GraphDirectedDetectCycleByDFS(3);
4443
graph.addEdge(0, 1);
4544
graph.addEdge(1, 2);
4645
graph.addEdge(2, 0);

‎datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/GraphDirectedDetectCycleByDFSColor.java‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package com.hellokoding.datastructure;
2+
3+
import java.util.ArrayDeque;
4+
import java.util.Deque;
5+
6+
public class GraphDirectedDetectCycleByDFSColor extends GraphDirectedByAdjacencyList {
7+
static final int WHITE = 0, GRAY = 1, BLACK = 2;
8+
public GraphDirectedDetectCycleByDFSColor(int V) {
9+
super(V);
10+
}
11+
12+
public boolean dfsWithColor(int startingVertex) {
13+
int[] color = new int[V];
14+
color[startingVertex] = GRAY;
15+
16+
Deque<Integer> stack = new ArrayDeque<>(V);
17+
stack.push(startingVertex);
18+
19+
while (!stack.isEmpty()){
20+
int v = stack.peek();
21+
for (int adj : adjacencyList.get(v)) {
22+
if (color[adj] == GRAY) {
23+
return true;
24+
} else if (color[adj] == WHITE) {
25+
color[adj] = GRAY;
26+
stack.push(adj);
27+
} else {
28+
color[adj] = BLACK;
29+
stack.pop();
30+
}
31+
}
32+
}
33+
34+
return false;
35+
}
36+
37+
private boolean dfsWithColorByRecursion(int v, int[] color) {
38+
color[v] = GRAY;
39+
40+
for (Integer adj : adjacencyList.get(v)) {
41+
if (color[v] == GRAY) {
42+
return true;
43+
}
44+
45+
if (color[v] == WHITE && dfsWithColorByRecursion(adj, color)){
46+
return true;
47+
}
48+
}
49+
50+
color[v] = BLACK;
51+
return false;
52+
}
53+
54+
public boolean hasCycleByRecursion() {
55+
int[] color = new int[V];
56+
57+
for (int i = 0; i < V; i++) {
58+
if (color[i] == WHITE && dfsWithColorByRecursion(i, color)) {
59+
return true;
60+
}
61+
}
62+
63+
return false;
64+
}
65+
66+
public static void main(String[] args) {
67+
GraphDirectedDetectCycleByDFSColor graph = new GraphDirectedDetectCycleByDFSColor(3);
68+
graph.addEdge(0, 1);
69+
graph.addEdge(1, 2);
70+
graph.addEdge(2, 0);
71+
System.out.println(graph.dfsWithColor(0));
72+
}
73+
}

0 commit comments

Comments
 (0)