我完全根据自己的理解编写了BFS和DFS代码，如下所示。这是测试示例。寻找输入-我如何在逻辑方面做得更好&数据结构。我知道已经有现成的&可能是互联网上的完美代码，但我希望尝试一下我的代码。
附言：代码并不完美，但我已经测试了给定的例子。如果你觉得一团糟，请道歉。欢迎您的评论。
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 FilesJavajdk-11.0.4binjava.exe" "-javaagent:C:Program FilesJetBrainsIntelliJ IDEA 2018.3.4libidea_rt.jar=64975:C:Program FilesJetBrainsIntelliJ IDEA 2018.3.4bin" -Dfile.encoding=UTF-8 -classpath C:CodeBaseTestoutproductionTest 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
我尝试过的一种方法是将边实现为Map，其中每个条目都将键作为顶点，将值作为包含边的列表，即所有连接顶点和权重。(我的灵感来自互联网上的邻接列表方法，它比我以前的方法中的边列表更有效，特别是在从给定顶点。遍历的复杂度可以是n(n-1(，即假设所有顶点都连接到所有顶点，边列表方法中的O(n^2(。其中，如(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 FilesJavajdk-11.0.4binjava.exe" "-javaagent:C:Program FilesJetBrainsIntelliJ IDEA 2018.3.4libidea_rt.jar=50287:C:Program FilesJetBrainsIntelliJ IDEA 2018.3.4bin" -Dfile.encoding=UTF-8 -classpath C:CodeBaseTestoutproductionTest 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