Skip to content

Commit 95b633f

Browse files
darecoderdarecoder
committed
graph update
1 parent c125fc0 commit 95b633f

File tree

3 files changed

+35
-84
lines changed

3 files changed

+35
-84
lines changed

‎.idea/workspace.xml

Lines changed: 2 additions & 4 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/com/company/Lecture21/AdjListGraph.java

Lines changed: 31 additions & 75 deletions
Original file line numberDiff line numberDiff line change
@@ -3,55 +3,47 @@
33
import java.util.*;
44

55
public class AdjListGraph <E> {
6-
76
private Map<E, Vertex> vertices = new HashMap<E, Vertex>();
87

98
private class Vertex{
109
E value;
1110
List<Vertex> neighbours = new LinkedList<Vertex>();
12-
1311
public Vertex(E value){
1412
this.value = value;
1513
}
16-
1714
@Override
1815
public String toString() {
1916
return value.toString();
2017
}
2118
}
2219

23-
public void addVertex(E value){
24-
if(vertices.get(value) == null){
25-
vertices.put(value, new Vertex(value));
26-
}
27-
28-
}
29-
3020
public void addEdge(E first, E second){
3121
Vertex f = vertices.get(first);
3222
Vertex s = vertices.get(second);
33-
3423
if(f != null && s != null){
3524
f.neighbours.add(s);
3625
s.neighbours.add(f);
3726
}
3827
}
3928

29+
public void addVertex(E value){
30+
if(vertices.get(value) == null){
31+
vertices.put(value, new Vertex(value));
32+
}
33+
}
34+
4035
public void DFT(E start){
4136
Vertex v = vertices.get(start);
42-
4337
Stack<Vertex> stack = new Stack<Vertex>();
4438
Set<Vertex> set = new HashSet<Vertex>();
45-
4639
stack.push(v);
4740
set.add(v);
48-
4941
while (!stack.empty()){
5042
Vertex top = stack.pop();
5143
System.out.print(top.value + " ");
52-
5344
for(Vertex padosi : top.neighbours){
54-
if(!set.contains(padosi)){ //agar set mein nhi hai toh hi stack mein daalo aur set mein daalo
45+
//agar set mein nhi hai toh hi stack mein daalo aur set mein daalo
46+
if(!set.contains(padosi)){
5547
stack.push(padosi);
5648
set.add(padosi);
5749
}
@@ -61,133 +53,108 @@ public void DFT(E start){
6153

6254
public void BFT(E start){
6355
Vertex v = vertices.get(start);
64-
6556
Queue<Vertex> queue = new LinkedList<Vertex>();
6657
Set<Vertex> set = new HashSet<Vertex>();
67-
6858
queue.add(v);
6959
set.add(v);
70-
7160
while (!queue.isEmpty()){
7261
Vertex top = queue.remove();
7362
System.out.print(top.value + " ");
74-
7563
for(Vertex padosi : top.neighbours){
7664
if(!set.contains(padosi)){
7765
queue.add(padosi);
7866
set.add(padosi);
7967
}
8068
}
8169
}
82-
8370
}
8471

8572
public boolean DFS(E start,E target){
8673
Vertex v = vertices.get(start);
87-
8874
Stack<Vertex> stack = new Stack<Vertex>();
8975
Set<Vertex> set = new HashSet<Vertex>();
90-
9176
stack.push(v);
9277
set.add(v);
93-
9478
while (!stack.empty()){
9579
Vertex top = stack.pop();
9680
if(top.value.equals(target)){
9781
return true;
9882
}
99-
10083
for(Vertex padosi : top.neighbours){
101-
if(!set.contains(padosi)){ //agar set mein nhi hai toh hi stack mein daalo aur set mein daalo
84+
//agar set mein nhi hai toh hi stack mein daalo aur set mein daalo
85+
if(!set.contains(padosi)){
10286
stack.push(padosi);
10387
set.add(padosi);
10488
}
10589
}
10690
}
107-
10891
return false;
10992
}
11093

11194
public boolean BFS(E start, E target){
11295
Vertex v = vertices.get(start);
113-
11496
Queue<Vertex> queue = new LinkedList<Vertex>();
11597
Set<Vertex> set = new HashSet<Vertex>();
116-
11798
queue.add(v);
11899
set.add(v);
119-
120100
while (!queue.isEmpty()){
121101
Vertex top = queue.remove();
122102
if(top.value.equals(target)){
123103
return true;
124104
}
125-
126105
for(Vertex padosi : top.neighbours){
127106
if(!set.contains(padosi)){
128107
queue.add(padosi);
129108
set.add(padosi);
130109
}
131110
}
132111
}
133-
134112
return false;
135113
}
136114

137115
public List<LinkedList<E>> connectedComponent(){
138-
139116
List<LinkedList<E>> list = new LinkedList<LinkedList<E>>();
140-
141117
Stack<Vertex> stack = new Stack<Vertex>();
142118
Set<Vertex> set = new HashSet<Vertex>();
143-
144-
int i = 0;
145119
for (Vertex start : vertices.values()) {
146120
LinkedList<E> tempList = new LinkedList<E>();
147121
if(set.contains(start)){
148122
continue;
149123
}
150-
151124
stack.push(start);
152125
set.add(start);
153-
154126
while (!stack.empty()){
155127
Vertex top = stack.pop();
156-
// System.out.print(top.value + " ");
157128
tempList.add(top.value);
158-
159129
for(Vertex padosi : top.neighbours){
160-
if(!set.contains(padosi)){ //agar set mein nhi hai toh hi stack mein daalo aur set mein daalo
130+
//agar set mein nhi hai toh hi stack mein daalo aur set mein daalo
131+
if(!set.contains(padosi)){
161132
stack.push(padosi);
162133
set.add(padosi);
163134
}
164135
}
165136
}
166-
167-
// System.out.println();
168-
i++;
169137
list.add(tempList);
170138
}
171-
172139
return list;
173140
}
174141

175-
public boolean bipartiteGraph(){
142+
public boolean isConnected(){
143+
List<LinkedList<E>> list = this.connectedComponent();
144+
return list.size() < 2;
145+
}
176146

147+
public boolean bipartiteGraph(){
177148
Set<Vertex> red = new HashSet<Vertex>();
178149
Set<Vertex> black = new HashSet<Vertex>();
179150
Stack<Vertex> stack = new Stack<Vertex>();
180-
181151
for (Vertex v : vertices.values()){
182152
if (!red.contains(v) && ! black.contains(v)){
183153
stack.push(v);
184154
red.add(v);
185-
186155
while (!stack.empty()){
187156
Vertex top = stack.pop();
188-
189157
for (Vertex padosi : top.neighbours){
190-
191158
if (red.contains(top)){
192159
if (red.contains(padosi)) {
193160
return false;
@@ -211,37 +178,26 @@ public boolean bipartiteGraph(){
211178
}
212179
}
213180
}
214-
215181
return true;
216182
}
217183

218-
public boolean isConnected(){
219-
List<LinkedList<E>> list = this.connectedComponent();
220-
return list.size() < 2;
221-
}
222-
223184
public boolean isCyclic(E start){
224-
Vertex v = vertices.get(start);
225-
226-
Queue<Vertex> queue = new LinkedList<Vertex>();
227-
Set<Vertex> set = new HashSet<Vertex>();
228-
229-
queue.add(v);
230-
set.add(v);
231-
232-
while (!queue.isEmpty()){
233-
Vertex top = queue.remove();
234-
235-
for(Vertex padosi : top.neighbours){
236-
if(!set.contains(padosi)){
237-
queue.add(padosi);
238-
set.add(padosi);
239-
}else{
240-
return true;
241-
}
185+
Vertex v = vertices.get(start);
186+
Queue<Vertex> queue = new LinkedList<Vertex>();
187+
Set<Vertex> set = new HashSet<Vertex>();
188+
queue.add(v);
189+
set.add(v);
190+
while (!queue.isEmpty()){
191+
Vertex top = queue.remove();
192+
for(Vertex padosi : top.neighbours){
193+
if(!set.contains(padosi)){
194+
queue.add(padosi);
195+
set.add(padosi);
196+
}else{
197+
return true;
242198
}
243199
}
244-
200+
}
245201
return false;
246202
}
247203
}

‎src/com/company/Lecture21/EdgeListGraph.java

Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -3,13 +3,11 @@
33
import java.util.LinkedList;
44

55
public class EdgeListGraph <E> {
6-
76
public LinkedList<Vertex> vertices = new LinkedList<Vertex>();
87
public LinkedList<Edge> edges = new LinkedList<Edge>();
98

109
private class Vertex{
1110
private E value;
12-
1311
public Vertex(E value){
1412
this.value = value;
1513
}
@@ -25,10 +23,9 @@ public Edge(Vertex start, Vertex end){
2523
}
2624
}
2725

28-
//We need to traverse all edges to fint neighbours of a particular vertex
29-
// for adding a vertex we to traverse whole vertex list
26+
//We need to traverse all edges to find neighbours of a particular vertex
27+
// for adding a vertex we need to traverse whole vertex list
3028
// for adding edge we have to traverse both vertices and edge list
31-
3229
public void addVertex(E value){
3330
if(find(value) == null){
3431
vertices.add(new Vertex(value));

0 commit comments

Comments
 (0)