Merge branch 'main' into newyash

PrajaktaSathe · web-flow · commit edea301107c5 · 2021-10-31T21:40:58.000+05:30
diff --git a/Programs/BreathFirstSearch.java b/Programs/BreathFirstSearch.java
@@ -0,0 +1,61 @@
+// BFS algorithm in Java
+
+import java.util.*;
+
+public class Graph {
+  private int V;
+  private LinkedList<Integer> adj[];
+
+  // Create a graph
+  Graph(int v) {
+    V = v;
+    adj = new LinkedList[v];
+    for (int i = 0; i < v; ++i)
+      adj[i] = new LinkedList();
+  }
+
+  // Add edges to the graph
+  void addEdge(int v, int w) {
+    adj[v].add(w);
+  }
+
+  // BFS algorithm
+  void BFS(int s) {
+
+    boolean visited[] = new boolean[V];
+
+    LinkedList<Integer> queue = new LinkedList();
+
+    visited[s] = true;
+    queue.add(s);
+
+    while (queue.size() != 0) {
+      s = queue.poll();
+      System.out.print(s + " ");
+
+      Iterator<Integer> i = adj[s].listIterator();
+      while (i.hasNext()) {
+        int n = i.next();
+        if (!visited[n]) {
+          visited[n] = true;
+          queue.add(n);
+        }
+      }
+    }
+  }
+
+  public static void main(String args[]) {
+    Graph g = new Graph(4);
+
+    g.addEdge(0, 1);
+    g.addEdge(0, 2);
+    g.addEdge(1, 2);
+    g.addEdge(2, 0);
+    g.addEdge(2, 3);
+    g.addEdge(3, 3);
+
+    System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");
+
+    g.BFS(2);
+  }
+}
diff --git a/Programs/DepthFirstSearch.java b/Programs/DepthFirstSearch.java
@@ -0,0 +1,48 @@
+// DFS algorithm in Java
+
+import java.util.*;
+
+class Graph {
+  private LinkedList<Integer> adjLists[];
+  private boolean visited[];
+
+  // Graph creation
+  Graph(int vertices) {
+    adjLists = new LinkedList[vertices];
+    visited = new boolean[vertices];
+
+    for (int i = 0; i < vertices; i++)
+      adjLists[i] = new LinkedList<Integer>();
+  }
+
+  // Add edges
+  void addEdge(int src, int dest) {
+    adjLists[src].add(dest);
+  }
+
+  // DFS algorithm
+  void DFS(int vertex) {
+    visited[vertex] = true;
+    System.out.print(vertex + " ");
+
+    Iterator<Integer> ite = adjLists[vertex].listIterator();
+    while (ite.hasNext()) {
+      int adj = ite.next();
+      if (!visited[adj])
+        DFS(adj);
+    }
+  }
+
+  public static void main(String args[]) {
+    Graph g = new Graph(4);
+
+    g.addEdge(0, 1);
+    g.addEdge(0, 2);
+    g.addEdge(1, 2);
+    g.addEdge(2, 3);
+
+    System.out.println("Following is Depth First Traversal");
+
+    g.DFS(2);
+  }
+}
diff --git a/README.md b/README.md
@@ -101,6 +101,9 @@ It is very easy to contribute, you may follow these steps -
 74. [Huffman Coding](https://github.com/PrajaktaSathe/Java/blob/main/Programs/HuffmanCoding.java) - Program that demonstrates Huffman Coding for data compression.
 75. [ADT Fraction Program](https://github.com/PrajaktaSathe/Java/blob/main/Programs/ADTFractionApp.java) - Program to demontrate how to deal with numarators and denomenator
 76. [Number Array without duplicate elements](https://github.com/PrajaktaSathe/Java/blob/main/Programs/NoDupArray.java) - Program to demontrate Number array without duplicate elements
+77. [Depth First Search](https://github.com/PrajaktaSathe/Java/blob/main/Programs/Gssarray.java) - Program demonstrates Depth First Search algorithm
+78. [Breath First Search](https://github.com/PrajaktaSathe/Java/blob/main/Programs/Gssarray.java) - Program demonstrates Breath First Search algorithm
+
 
 # Contributors - 
 ## A big thank you to all our contributors!!!
