Added Breadth First Search [Java] #190

jitendra3109 · 2017-05-28T19:43:58Z

Fixes #73

By submitting this pull request I confirm I've read and complied with the below declarations.

I have read the Contribution guidelines and I am confident that my PR reflects them.
I have followed the coding guidelines for this project.
My code follows the skeleton code structure.
This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.
This pull request will be closed if I fail to update it even once in a continuous timespan of 7 days.

Monal5031 · 2017-05-28T20:40:47Z

README.md

@@ -11,6 +11,7 @@ Community (college) maintained list of Algorithms and Data Structures implementa

 | Algorithm | C | CPP | Java | Python | Golang |
 |:--------------|:----------------:|:----------------:|:----------------:|:-----------------:|:-----------------:|
+| [Breadth First Traversal](https://en.wikipedia.org/wiki/Breadth-first_search) |  | | [\[X\]](breadth_first_traversal/BreadthFirstTraversal.java) |  | |


This entry will come after Binary Search

singhpratyush · 2017-05-29T07:21:13Z

breadth_first_traversal/BreadthFirstTraversal.java

+        addEdge(2, 1);
+        addEdge(2, 3);
+        addEdge(3, 3);
+        System.out.println("Breadth First Traversal starting from vertex 0");


What would this function be searching for?

@singhpratyush not searching. It would give you the path of BFT from root 0 to all node.

But since we are searching for things, there should be a target node.

@singhpratyush Is that okay?

jitendra3109 · 2017-05-31T05:31:47Z

@aviaryan Please can check why travis-ci fail?

singhpratyush · 2017-05-31T06:05:29Z

breadth_first_traversal/BreadthFirstTraversal.java

+        System.out.println("Breadth First Traversal starting from source to destination");
+        breadthFirstTraversal(1,3);
+    }
+}


What would be the output of this program?

It gives the BFT path from source to destination.

aviaryan · 2017-05-31T07:23:20Z

@jsroyal Build fixed now. It was a coala problem, nothing wrong with your code.

singhpratyush

Pleasse see comments.

singhpratyush · 2017-06-02T05:45:05Z

breadth_first_traversal/BreadthFirstTraversal.java

@@ -0,0 +1,64 @@
+import java.util.HashSet;


Inconsistent file and class names.

singhpratyush · 2017-06-02T05:45:37Z

breadth_first_traversal/BreadthFirstTraversal.java

+            while (i.hasNext()) {
+                int n = i.next();
+                if (n == destination) {
+                    System.out.println(n);


Do not print anything in algorithm function.

singhpratyush · 2017-06-02T05:46:04Z

breadth_first_traversal/BreadthFirstTraversal.java

+        adj[source].add(w);
+    }
+
+    private static void breadthFirstTraversal(int source, int destination) {


How will other classes use this if it is private?

singhpratyush · 2017-06-02T05:46:28Z

breadth_first_traversal/BreadthFirstTraversal.java

+public class BreadthFirstSearch {
+
+    // Array  of lists for Adjacency List Representation
+    public static LinkedList<Integer>[] adj;


Why bound to int? This can be generic.

@singhpratyush Please, can you explain a little bit more?

You are saying that the adjacency list may contain only integer items, while they can be anything. They can be names, addresses, tweets, a state of N-Queen board, etc. You just need to define that they are somehow linked.

So, instead of using Integer, you can go with generic objects.

Thanks.
how should I go about? Can please write some code snippet?

Use templates.

Can please write some code snippet? I'm not getting, using the template in linked list.

@jsroyal For templates, refer to https://github.com/iiitv/algos/blob/master/linked_list/LinkedList.java for an example.

singhpratyush · 2017-06-03T11:33:31Z

breadth_first_traversal/BreadthFirstTraversal.java

@@ -2,7 +2,7 @@

 import java.util.*;

-public class breadthFirstTraversal {
+public class BreadthFirstTraversal {


Better change the names to BreadthFirstSearch instead of BreadthFirstTraversal.

mohitkyadav

Please see comments

mohitkyadav · 2017-06-03T11:41:24Z

README.md

@@ -12,6 +12,7 @@ Community (college) maintained list of Algorithms and Data Structures implementa
 | Algorithm | C | CPP | Java | Python | Golang |
 |:--------------|:----------------:|:----------------:|:----------------:|:-----------------:|:-----------------:|
 | [Binary Search](https://en.wikipedia.org/wiki/Binary_search_algorithm) | [\[X\]](binary_search/binary_search.c) | | [\[X\]](binary_search/BinarySearch.java) | [\[X\]](binary_search/binary_search.py) | |
+| [Breadth First Traversal](https://en.wikipedia.org/wiki/Breadth-first_search) |  | | [\[X\]](breadth_first_traversal/BreadthFirstTraversal.java) |  | |


@jsroyal Please take a look at space inconsistency in | | |.

aviaryan

Please indent using tabs. Related: Tabs vs Spaces - StackExchange

jitendra3109 · 2017-06-07T05:19:24Z

Hi! @aviaryan I think now indentation is consistant. I'm using IntelliJ IDE where the standard configuration of Java Coding Convention.

Okay. Let's go with spaces for now.

aviaryan · 2017-06-08T03:27:07Z

breadth_first_search/BreadthFirstSearch.java

+        addEdge(2, 3);
+        addEdge(3, 3);
+        System.out.println("Breadth First Search starting from source to destination");
+        ArrayList arrayList = breadthFirstSearch(1,3);


It would be great if you can make this 1, 3.

singhpratyush

#190 (comment) is still not solved.

You may refer to this implementation if you need something.

singhpratyush · 2017-06-10T06:14:00Z

@jsroyal: You have been inactive for 3 days now. Just as a reminder, this PR will be closed if you stay inactive for 7 days.

singhpratyush · 2017-06-11T13:53:55Z

README.md

@@ -14,6 +14,7 @@ Community (college) maintained list of Algorithms and Data Structures implementa
 |:--------------|:----------------:|:----------------:|:----------------:|:-----------------:|:-----------------:|
 | [Bin Sort](http://www.cdn.geeksforgeeks.org/bucket-sort-2/)| | |[\[X\]](bin_sort/BinSort.java)| | |
 | [Binary Search](https://en.wikipedia.org/wiki/Binary_search_algorithm) | [\[X\]](binary_search/binary_search.c) | | [\[X\]](binary_search/BinarySearch.java) | [\[X\]](binary_search/binary_search.py) | |
+| [Breadth First Traversal](https://en.wikipedia.org/wiki/Breadth-first_search) | | | [\[X\]](breadth_first_traversal/BreadthFirstTraversal.java) | | |


Change this to Breadth First Search.

aviaryan · 2017-06-24T07:08:45Z

@jsroyal Please fix the build.

breadth_first_search/BreadthFirstSearch.java
    [10:01] ❌️ unexpected trailing whitespace (EditorConfig trim_trailing_whitespace https://github.com/editorconfig/editorconfig/wiki/EditorConfig-Properties#trim_trailing_whitespace)
        10|
    d1e28750 (Jitendra Singh <jsroyal55@gmail.com> 6/22/2017, 7:00:11 AM)
    [25:01] ❌️ unexpected trailing whitespace (EditorConfig trim_trailing_whitespace https://github.com/editorconfig/editorconfig/wiki/EditorConfig-Properties#trim_trailing_whitespace)
        25|
    f782a94a (Jitendra Singh <jsroyal55@gmail.com> 6/22/2017, 6:59:00 AM)
�```

jitendra3109 · 2017-06-24T09:29:30Z

@aviaryan trim_trailing_whitespace I do not get it. Please mention .

aashutoshrathi · 2017-06-24T09:39:26Z

breadth_first_search/BreadthFirstSearch.java

+public class BreadthFirstSearch<T> {
+    // HasMap  of lists for Adjacency List Representation
+    public HashMap<T, ArrayList<T>> adj = new HashMap<T, ArrayList<T>> ();
+


@jsroyal Sir, It is about removing the unnecessary whitespaces from blank lines 10 and 25.

@jsroyal You have to remove whitespace after line 10 and 25 here.

the line has trailing whitespace this line does not this line has trailing whitespace

⬆️ Select the contents of block above to understand.

aviaryan · 2017-06-24T10:56:51Z

breadth_first_search/BreadthFirstSearch.java

+    public HashMap<T, ArrayList<T>> adj = new HashMap<T, ArrayList<T>> ();   
+    //Function to add an edge
+    public void addEdges (T source, T destination) {
+        if (adj.containsKey (source)) {


Please remove space between function name and parameters.

This issue is at a lot of places.

It is too much 🔢 70

aviaryan · 2017-06-27T07:50:23Z

README.md

-| [Binary Search](https://en.wikipedia.org/wiki/Binary_search_algorithm) | [:white_check_mark:](binary_search/binary_search.c) | | [:white_check_mark:](binary_search/BinarySearch.java) | [:white_check_mark:](binary_search/binary_search.py) | [:white_check_mark:](binary_search/binary_search.go) | [:white_check_mark:](binary_search/binarySearch.js) |
-| [Coin Change Problem](http://www.algorithmist.com/index.php/Coin_Change) | [:white_check_mark:](coin_change_problem/coin_change_problem.c) | | [:white_check_mark:](coin_change_problem/CoinChange.java) | [:white_check_mark:](coin_change_problem/coin_change_problem.py) | | [:white_check_mark:](coin_change_problem/coinChangeProblem.js) |
-| [Counting Sort](http://www.geeksforgeeks.org/counting-sort/)| [:white_check_mark:](counting_sort/counting_sort.c) | | [:white_check_mark:](counting_sort/CountingSort.java) | | [:white_check_mark:](counting_sort/counting_sort.go) | |
+| [Binary Search](https://en.wikipedia.org/wiki/Binary_search_algorithm) | [:white_check_mark:](binary_search/binary_search.c) | | [:white_check_mark:](binary_search/BinarySearch.java) | [:white_check_mark:](binary_search/binary_search.py) | [:white_check_mark:](binary_search/binary_search.go) | |


The code looks good now. Please fix this diff.

aviaryan · 2017-06-27T08:21:53Z

breadth_first_search/BreadthFirstSearch.java

+            for (int i = 0; i < temp.size(); i++) {
+                if (! visited.contains(temp.get(i))) {
+                    bfsPath.add(temp.get(i));
+                    if (temp.get(i) == destination) {


Please use .equals() for comparison here as == compares object references rather than what is needed to be compared.

Monal5031 · 2017-06-29T19:00:23Z

@jsroyal sir update README its showing some unnecessary diffs.

aviaryan · 2017-07-01T06:39:01Z

@jsroyal Thanks for this PR. It might have taken a long time but this was some quality code. Looking forward to more contributions from you.

aashutoshrathi · 2017-07-01T06:53:22Z

breadth_first_search/BreadthFirstSearch.java

+        bfsPath.add(source);
+        // mark as visited
+        visited.add(source);
+        int flag = 0;


If we only have to deal with 0 and 1 , we can use boolean here

added bfs

35b23d3

Monal5031 reviewed May 28, 2017

View reviewed changes

corrected the entery in readme

e3af626

singhpratyush reviewed May 29, 2017

View reviewed changes

update with source and destination

7e6b2b2

singhpratyush requested changes May 31, 2017

View reviewed changes

singhpratyush requested changes Jun 2, 2017

View reviewed changes

jsroyal added 2 commits June 3, 2017 12:02

minor fix

feee0a1

class name with uppercase -> by codacy

c8c1b5f

singhpratyush reviewed Jun 3, 2017

View reviewed changes

mohitkyadav reviewed Jun 3, 2017

View reviewed changes

changed the class name and removed space readme file

79e4480

aviaryan previously requested changes Jun 7, 2017

View reviewed changes

aviaryan approved these changes Jun 8, 2017

View reviewed changes

aviaryan reviewed Jun 8, 2017

View reviewed changes

singhpratyush reviewed Jun 8, 2017

View reviewed changes

Merge branch 'master' into master

c165247

singhpratyush added Algorithm lang-java labels Jun 10, 2017

Merge branch 'master' into master

408f2e6

iiitv deleted a comment Jun 11, 2017

singhpratyush reviewed Jun 11, 2017

View reviewed changes

Jitendra Singh added 2 commits June 11, 2017 23:41

Merge branch 'master' into master

7263cf7

give a space

0c386c5

aashutoshrathi reviewed Jun 24, 2017

View reviewed changes

remove a blank line above this.

2afa5a9

aviaryan requested changes Jun 24, 2017

View reviewed changes

jsroyal added 4 commits June 26, 2017 11:21

space remove

63d81e6

Merge branch 'master' into master

dec2cba

remove redudent type cast

1e6ee8e

Merge branch 'master' of github.com:jsroyal/algos

31f57c3

aviaryan requested changes Jun 27, 2017

View reviewed changes

jsroyal added 2 commits June 30, 2017 00:20

== to .equals()

aaff974

Merge branch 'master' into master

99e61f6

Update README.md

4509f7f

singhpratyush assigned aviaryan and unassigned singhpratyush Jul 1, 2017

singhpratyush requested review from aviaryan, yashLadha, Prakash2403, Monal5031, aashutoshrathi and mohitkyadav July 1, 2017 06:08

aviaryan added 2 commits July 1, 2017 11:58

Update BreadthFirstSearch.java

737247a

Merge branch 'master' into master

51e5c5e

aviaryan approved these changes Jul 1, 2017

View reviewed changes

aviaryan merged commit 800f1a8 into iiitv:master Jul 1, 2017

aashutoshrathi reviewed Jul 1, 2017

View reviewed changes

singhpratyush added the No activity label Dec 20, 2017

Added Breadth First Search [Java] #190

Added Breadth First Search [Java] #190

Conversation

jitendra3109 commented May 28, 2017

By submitting this pull request I confirm I've read and complied with the below declarations.

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jitendra3109 commented May 31, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

aviaryan commented May 31, 2017

singhpratyush left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

mohitkyadav left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

aviaryan left a comment • edited

Choose a reason for hiding this comment

jitendra3109 commented Jun 7, 2017

Choose a reason for hiding this comment

singhpratyush left a comment

Choose a reason for hiding this comment

singhpratyush commented Jun 10, 2017

Choose a reason for hiding this comment

aviaryan commented Jun 24, 2017

jitendra3109 commented Jun 24, 2017

Choose a reason for hiding this comment

aviaryan Jun 24, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jitendra3109 Jun 26, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Monal5031 commented Jun 29, 2017

aviaryan commented Jul 1, 2017

Choose a reason for hiding this comment

aviaryan left a comment •

edited

aviaryan Jun 24, 2017 •

edited

jitendra3109 Jun 26, 2017 •

edited