Код поиска в ширину (BFS) и поиск в глубину (DFS) - нужно предложение, как я могу улучшить его

Question

Я написал код BFS и DFS исключительно с моим пониманием, как показано ниже. Что вместе с тестовым примером. Ищите вход - как я могу сделать это лучше с точки зрения логики c и структуры данных. Я знаю, что они уже приготовлены и могут быть идеальным кодом в inte rnet, но я попытаюсь использовать мой sh.

PS: Код не идеален, однако я протестировал на данном примере. Извинения, если вы находите это грязным. Ваши комментарии будут приветствоваться.

package com.company.graph;

import java.util.*;

public class BrethFirstSearch {


    public static void main(String...args){


        /*
         Input Undirected Graph -

            2      4       1
        A-------B-------C-------D
        | \             |   \   |
      7 |  \9         13|   3\  |6
        |   \           |     \ |
        E----F----------G-------H
          1      8         13

        Task 1 - Represent this graph as Data Structure that have optimal Space & Time complexity for store & traversal
        Task 2 - Perform "Breadth First Search"


        Simplified Representation of Graph where replaced vertex names with numbers..
             2      4       1
        0-------1-------2-------3
        | \             |   \   |
      7 |  \9         13|   3\  |6
        |   \           |     \ |
        4----5----------6-------7
          1      8         13

        */


        // We store number instated of letters since in real world every vertex may have full qualified name ex - "LasVegas" instead of just "A"
        Map<Integer,String> vertices = new HashMap<>();
        vertices.put(0,"A");
        vertices.put(1,"B");
        vertices.put(2,"C");
        vertices.put(3,"D");
        vertices.put(4,"E");
        vertices.put(5,"F");
        vertices.put(6,"G");
        vertices.put(7,"H");

        Map<Edge, Integer> edges = new HashMap<>();

        //Note - I have store both the side to make Graph search simpler. Comments will be welcomed!!
        edges.put(new Edge(0,1), 2);
        edges.put(new Edge(0,4), 7);
        edges.put(new Edge(0,5), 9);
        edges.put(new Edge(1,0), 2);
        edges.put(new Edge(1,2), 4);
        edges.put(new Edge(2,1), 4);
        edges.put(new Edge(2,3), 1);
        edges.put(new Edge(2,6), 13);
        edges.put(new Edge(2,7), 3);
        edges.put(new Edge(3,2), 1);
        edges.put(new Edge(3,7), 6);
        edges.put(new Edge(4,0), 7);
        edges.put(new Edge(4,5), 1);
        edges.put(new Edge(5,0), 9);
        edges.put(new Edge(5,4), 1);
        edges.put(new Edge(5,6), 8);
        edges.put(new Edge(6,2), 13);
        edges.put(new Edge(6,5), 8);
        edges.put(new Edge(6,7), 13);
        edges.put(new Edge(7,2), 3);
        edges.put(new Edge(7,3), 6);
        edges.put(new Edge(7,6), 13);


        breadthFirstSearch(vertices, edges);
        depthFirstSearch(vertices,edges);

    }


    static void depthFirstSearch(Map<Integer,String> vertices, Map<Edge, Integer> edges){

        System.out.format("%n%n%n%n************  Depth First Search - DFS ***********%n%n");

        LinkedList<Integer> listOfVertex = new LinkedList<>(vertices.keySet());
        List<Edge> listOfEdges = new ArrayList<>(edges.keySet());

        Stack<Integer> dfsStack = new Stack<>();


        while (!listOfVertex.isEmpty()){

            Integer v = listOfVertex.getFirst();
            dfsStack.push(listOfVertex.remove());

            System.out.format("*** Start DFS from Vertex %S ***%n", vertices.get(v));

            while(!dfsStack.empty()){
                Integer vO = v;
                for (Edge edge: listOfEdges) {
                    if (v.equals(edge.getV1()) && listOfVertex.indexOf(edge.getV2()) != -1){  // found new vertex
                        Integer nextV = edge.getV2();
                        System.out.format("  Searching from Vertex %S -----> %S%n", vertices.get(edge.getV1()), vertices.get(nextV));
                        dfsStack.push(nextV);
                        listOfVertex.remove(nextV);
                        v = nextV;
                        break;
                    }
                }
                if(vO.equals(v)){   //means not new vertex found from current vertex
                    v = dfsStack.pop();     //Search for previous vertex
                    System.out.format("Vertex %S has been conquered %n", vertices.get(v));
                }
            }

        }

    }



    static void breadthFirstSearch(Map<Integer,String> vertices, Map<Edge, Integer> edges){

        System.out.format("************  Breadth First Search - BFS ***********%n%n");

        LinkedList<Integer> listOfVertex = new LinkedList<>(vertices.keySet());
        List<Edge> listOfEdges = new ArrayList<>(edges.keySet());

        BfsQueue bfsQueue = new BfsQueue();
        bfsQueue.add(listOfVertex.remove());  //start from 1st vertex = 0 alias A

        while (!bfsQueue.isEmpty()){

            //remove and start search from this vertex
            Integer v = bfsQueue.remove();
            System.out.format("Vertex %S has been conquered %n", vertices.get(v));

            //Search the Vertices from v
            listOfEdges.
                    forEach(edge -> {
                        if(v.equals(edge.getV1()) && listOfVertex.indexOf(edge.getV2()) != -1){
                            bfsQueue.add(edge.getV2());
                        }});

            //Mark the Searched Vertex
            Iterator<Integer> i = bfsQueue.getIterator();
            while (i.hasNext()){
                Integer vertex = i.next();
                if (listOfVertex.remove(vertex)){
                    System.out.format("     Searching from Vertex %S ------> %S %n", vertices.get(v), vertices.get(vertex));
                }

            }
        }
    }




    static class BfsQueue {

        private LinkedList<Integer> list = new LinkedList<>();

        Iterator<Integer> getIterator(){
            return list.iterator();
        }


        Integer remove(){
            Integer v = null;
            if(!list.isEmpty()){
                v = list.getFirst();
                list.removeFirst();
            }
            return v;
        }

        void add(Integer v){
            list.add(v);
        }

        boolean isEmpty(){
            return list.isEmpty();
        }

        boolean isPresent(Integer v){
            return list.indexOf(v) != -1;
        }

    }


    static class Edge {

        int v1;   //1st vertex
        int v2;   //2nd vertex

        public Edge(int v1, int v2) {
            this.v1 = v1;
            this.v2 = v2;
        }


        public int getV1() {
            return v1;
        }

        public int getV2() {
            return v2;
        }
    }
}

Вывод:

"C:\Program Files\Java\jdk-11.0.4\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2018.3.4\lib\idea_rt.jar=64975:C:\Program Files\JetBrains\IntelliJ IDEA 2018.3.4\bin" -Dfile.encoding=UTF-8 -classpath C:\CodeBase\Test\out\production\Test com.company.graph.BrethFirstSearch
************  Breadth First Search - BFS ***********

Vertex A has been conquered 
     Searching from Vertex A ------> E 
     Searching from Vertex A ------> B 
     Searching from Vertex A ------> F 
Vertex E has been conquered 
Vertex B has been conquered 
     Searching from Vertex B ------> C 
Vertex F has been conquered 
     Searching from Vertex F ------> G 
Vertex C has been conquered 
     Searching from Vertex C ------> H 
     Searching from Vertex C ------> D 
Vertex G has been conquered 
Vertex H has been conquered 
Vertex D has been conquered 




************  Depth First Search - DFS ***********

*** Start DFS from Vertex A ***
  Searching from Vertex A -----> E
  Searching from Vertex E -----> F
  Searching from Vertex F -----> G
  Searching from Vertex G -----> H
  Searching from Vertex H -----> C
  Searching from Vertex C -----> D
Vertex D has been conquered 
Vertex C has been conquered 
  Searching from Vertex C -----> B
Vertex B has been conquered 
Vertex H has been conquered 
Vertex G has been conquered 
Vertex F has been conquered 
Vertex E has been conquered 
Vertex A has been conquered 

Process finished with exit code 0

Answer 1

Один из подходов, которые я попробовал, - реализовать ребра в виде карты, где каждая запись имеет ключ в качестве вершины и значение в виде списка, содержащего ребра, то есть все соединительные вершины вместе с весом. (Я вдохновился подходом со списком смежности к inte rnet и более эффективен, чем список ребер, в соответствии с моим предыдущим подходом, особенно при поиске соединительных вершин из заданной вершины. Сложность обхода может быть n (n-1), т.е. O ( n ^ 2) в подходе Edge List, предполагающем, что все вершины связаны со всеми вершинами. Где (n-1) т.е. O (n) в подходе со списком смежности, как в n вершинах, граф n может быть связан со всеми n-1 вершинами)

т.е. если ниже приведен график -

             2      4       1
        0-------1-------2-------3
        | \             |   \   |
      7 |  \9         13|   3\  |6
        |   \           |     \ |
        4----5----------6-------7
          1      8         13

, то карта выглядит так -

        Map<Integer, List<Edge>> verticesEdges = new HashMap<>();
        verticesEdges.put(0, new LinkedList<>(List.of(new Edge(1,2), new Edge(4,7),new Edge(5,9) )));
        verticesEdges.put(1, new LinkedList<>(List.of(new Edge(0,2),new Edge(2,4))) );
        verticesEdges.put(2, new LinkedList<>(List.of(new Edge(1,4),new Edge(3,1),new Edge(6,13), new Edge(7,3))));
        verticesEdges.put(3,new LinkedList<>(List.of( new Edge(2,1), new Edge(7,6))));
        verticesEdges.put(4, new LinkedList<>(List.of(new Edge(0,7),new Edge(5,1) )));
        verticesEdges.put(5, new LinkedList<>(List.of(new Edge(0,9), new Edge(4,1),new Edge(6,8) )));
        verticesEdges.put(6, new LinkedList<>(List.of(new Edge(2,13), new Edge(5,8), new Edge(7,13))));
        verticesEdges.put(7, new LinkedList<>(List.of(new Edge(2,3),new Edge(3,6),new Edge(6,13))));

Теперь код BFS и DFS требуют незначительной модификации. Я представил ниже только для перспективы проверки -

package com.company.graph;

import java.util.*;

public class GraphSearch {

    public static void main(String...args){


        /*
         Input Undirected Graph -

            2      4       1
        A-------B-------C-------D
        | \             |   \   |
      7 |  \9         13|   3\  |6
        |   \           |     \ |
        E----F----------G-------H
          1      8         13

        Task 1 - Represent this graph as Data Structure that have optimal Space & Time complexity for store & traversal
        Task 2 - Perform "Breadth First Search"


        Simplified Representation of Graph where replaced vertex names with numbers..
             2      4       1
        0-------1-------2-------3
        | \             |   \   |
      7 |  \9         13|   3\  |6
        |   \           |     \ |
        4----5----------6-------7
          1      8         13

        */


        // We store number instated of letters since in real world every vertex may have full qualified name ex - "LasVegas" instead of just "A"
        Map<Integer,String> vertices = new HashMap<>();
        vertices.put(0,"A");
        vertices.put(1,"B");
        vertices.put(2,"C");
        vertices.put(3,"D");
        vertices.put(4,"E");
        vertices.put(5,"F");
        vertices.put(6,"G");
        vertices.put(7,"H");

        //Implemented edges as a Map where for each entry -  key is a vertex and value is List containing edges i.e. all connecting vertices along with the weight !!
        Map<Integer, List<Edge>> verticesEdges = new HashMap<>();
        verticesEdges.put(0, new LinkedList<>(List.of(new Edge(1,2), new Edge(4,7),new Edge(5,9) )));
        verticesEdges.put(1, new LinkedList<>(List.of(new Edge(0,2),new Edge(2,4))) );
        verticesEdges.put(2, new LinkedList<>(List.of(new Edge(1,4),new Edge(3,1),new Edge(6,13), new Edge(7,3))));
        verticesEdges.put(3,new LinkedList<>(List.of( new Edge(2,1), new Edge(7,6))));
        verticesEdges.put(4, new LinkedList<>(List.of(new Edge(0,7),new Edge(5,1) )));
        verticesEdges.put(5, new LinkedList<>(List.of(new Edge(0,9), new Edge(4,1),new Edge(6,8) )));
        verticesEdges.put(6, new LinkedList<>(List.of(new Edge(2,13), new Edge(5,8), new Edge(7,13))));
        verticesEdges.put(7, new LinkedList<>(List.of(new Edge(2,3),new Edge(3,6),new Edge(6,13))));


        breadthFirstSearch(vertices, verticesEdges);
        //depthFirstSearch(vertices,verticesEdges);

    }


    static void depthFirstSearch(Map<Integer,String> vertices, Map<Integer, List<Edge>> verticesEdges ){

        System.out.format("%n%n%n%n************  Depth First Search - DFS ***********%n%n");

        LinkedList<Integer> listOfVertex = new LinkedList<>(vertices.keySet());

        Stack<Integer> dfsStack = new Stack<>();


        while (!listOfVertex.isEmpty()){

            Integer v = listOfVertex.getFirst();
            dfsStack.push(listOfVertex.remove());

            System.out.format("*** Start DFS from Vertex %S ***%n", vertices.get(v));

            while(!dfsStack.empty()){
                Integer vO = v;
                for (Edge edge: verticesEdges.get(v)) {
                    if (listOfVertex.indexOf(edge.getV()) != -1){  // found new vertex
                        Integer nextV = edge.getV();
                        System.out.format("  Searching from Vertex %S -----> %S%n", vertices.get(v), vertices.get(nextV));
                        dfsStack.push(nextV);
                        listOfVertex.remove(nextV);
                        v = nextV;
                        break;
                    }
                }
                if(vO.equals(v)){   //means not new vertex found from current vertex
                    v = dfsStack.pop();     //Search for previous vertex
                    System.out.format("Vertex %S has been conquered %n", vertices.get(v));
                }
            }

        }

    }



    static void breadthFirstSearch(Map<Integer,String> vertices, Map<Integer, List<Edge>> verticesEdges){

        System.out.format("************  Breadth First Search - BFS ***********%n%n");

        LinkedList<Integer> listOfVertex = new LinkedList<>(vertices.keySet());

        BfsQueue bfsQueue = new BfsQueue();
        bfsQueue.add(listOfVertex.remove());  //start from 1st vertex = 0 alias A

        while (!bfsQueue.isEmpty()){

            //remove and start search from this vertex
            Integer v = bfsQueue.remove();
            System.out.format("Vertex %S has been conquered %n", vertices.get(v));

            //Search the Vertices from v
            verticesEdges.get(v).forEach(edge -> {
                if(listOfVertex.indexOf(edge.getV()) != -1){
                    bfsQueue.add(edge.getV());
                }});

            //Mark the Searched Vertex
            Iterator<Integer> i = bfsQueue.getIterator();
            while (i.hasNext()){
                Integer vertex = i.next();
                if (listOfVertex.remove(vertex)){
                    System.out.format("     Searching from Vertex %S ------> %S %n", vertices.get(v), vertices.get(vertex));
                }

            }
        }
    }




    static class BfsQueue {

        private LinkedList<Integer> list = new LinkedList<>();

        Iterator<Integer> getIterator(){
            return list.iterator();
        }


        Integer remove(){
            Integer v = null;
            if(!list.isEmpty()){
                v = list.getFirst();
                list.removeFirst();
            }
            return v;
        }

        void add(Integer v){
            list.add(v);
        }

        boolean isEmpty(){
            return list.isEmpty();
        }

        boolean isPresent(Integer v){
            return list.indexOf(v) != -1;
        }

    }


    static class Edge {

        int v;   //Connecting Vertex
        int w;   //weight Of edge

        public Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }

        public int getV() {
            return v;
        }

        public int getW() {
            return w;
        }
    }
}

Когда я запустил его -

"C:\Program Files\Java\jdk-11.0.4\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2018.3.4\lib\idea_rt.jar=50287:C:\Program Files\JetBrains\IntelliJ IDEA 2018.3.4\bin" -Dfile.encoding=UTF-8 -classpath C:\CodeBase\Test\out\production\Test com.company.graph.GraphSearch
************  Breadth First Search - BFS ***********

Vertex A has been conquered 
     Searching from Vertex A ------> B 
     Searching from Vertex A ------> E 
     Searching from Vertex A ------> F 
Vertex B has been conquered 
     Searching from Vertex B ------> C 
Vertex E has been conquered 
Vertex F has been conquered 
     Searching from Vertex F ------> G 
Vertex C has been conquered 
     Searching from Vertex C ------> D 
     Searching from Vertex C ------> H 
Vertex G has been conquered 
Vertex D has been conquered 
Vertex H has been conquered 




************  Depth First Search - DFS ***********

*** Start DFS from Vertex A ***
  Searching from Vertex A -----> B
  Searching from Vertex B -----> C
  Searching from Vertex C -----> D
  Searching from Vertex D -----> H
  Searching from Vertex H -----> G
  Searching from Vertex G -----> F
  Searching from Vertex F -----> E
Vertex E has been conquered 
Vertex F has been conquered 
Vertex G has been conquered 
Vertex H has been conquered 
Vertex D has been conquered 
Vertex C has been conquered 
Vertex B has been conquered 
Vertex A has been conquered 

Process finished with exit code 0