-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMyGraph.java
More file actions
120 lines (106 loc) · 3.08 KB
/
Copy pathMyGraph.java
File metadata and controls
120 lines (106 loc) · 3.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
package graph.base;
import java.util.*;
public class MyGraph {
private HashMap<Integer, Vertex> vertDictionary;
private int numVertices = 0;
private boolean directed = false;
public MyGraph() {
vertDictionary = new HashMap<>();
}
public void addVertex(boolean directed) {
this.directed = directed;
}
public boolean isDirected() {
return directed;
}
public int getNumVertices() {
return numVertices;
}
public void addVertex(int node) {
vertDictionary.put(node, new Vertex(node));
numVertices++;
}
public void addEdge(int from, int to, int cost) {
if (!vertDictionary.containsKey(from)) {
addVertex(from);
}
if (!vertDictionary.containsKey(to)) {
addVertex(to);
}
vertDictionary.get(from).addNeighbor(vertDictionary.get(to), cost);
}
/**
* dfs (recusion)
*
* @param start
* @param end
*/
public void dfs(Vertex start, Vertex end) {
dfsHelper(start, end, new HashSet<Vertex>(), new HashMap<Vertex, Vertex>());
}
public void dfsHelper(Vertex start, Vertex end, HashSet<Vertex> visited, HashMap<Vertex, Vertex> parents) {
if (end == start) {
return;
}
HashMap<Vertex, Integer> neighbor = start.getNeighbor();
for (Vertex node : neighbor.keySet()) {
if (!visited.contains(node)) {
visited.add(node);
parents.put(node, start);
dfsHelper(node, end, visited, parents);
}
}
}
/**
* dfs (algorithm)
*
* @param start
* @param end
*/
public void dfs2(Vertex start, Vertex end) {
Stack<Vertex> stack = new Stack<>();
HashSet<Vertex> visited = new HashSet<>();
HashMap<Vertex, Vertex> parents = new HashMap<>();
stack.add(start);
visited.add(start);
while (!stack.isEmpty()) {
Vertex curr = stack.pop();
if (curr == end) {
return;
}
for (Vertex node : curr.getNeighbor().keySet()) {
if (!visited.contains(node)) {
visited.add(node);
stack.push(node);
parents.put(node, curr);
}
}
}
}
/**
* bfs
*
* @param start
* @param end
*/
public void bfs(Vertex start, Vertex end) {
Queue<Vertex> queue = new LinkedList<>();
HashSet<Vertex> visited = new HashSet<>();
HashMap<Vertex, Vertex> parents = new HashMap<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
Vertex curr = queue.poll();
if (curr == end) {
return;
}
for (Vertex node : curr.getNeighbor().keySet()) {
if (!visited.contains(node)) {
visited.add(node);
parents.put(node, curr);
queue.offer(node);
}
}
}
}
}