java中的導向圖

Question

任何人都可以幫助我在我的圖上實現bfs嗎？我把我的圖形實現和bfs算法放到我的圖中。我只需要一些想法如何去做。

public class DiGraph<V> { 

     public static class Edge<V>{ 
      private V vertex; 
      private int cost; 

      public Edge(V v, int c){ 
       vertex = v; 
       cost = c; 
      } 
      @Override 
      public String toString() { 
       return "{" + vertex + ", " + cost + "}"; 
      } 
     } 

     private Map<V, List<Edge<V>>> inNeighbors = new HashMap<V, List<Edge<V>>>(); 
     private Map<V, List<Edge<V>>> outNeighbors = new HashMap<V, List<Edge<V>>>(); 
     public int nr_vertices; 
     public int nr_edges; 

     public String toString() { 
      StringBuffer s = new StringBuffer(); 
      for (V v: inNeighbors.keySet()) 
       s.append("\n " + v + " -> " + inNeighbors.get(v)); 
      return s.toString();     
     } 

     public void addIn (V vertex) { 
      if (inNeighbors.containsKey(vertex)) 
       return; 

      inNeighbors.put(vertex, new ArrayList<Edge<V>>()); 

     } 

     public void addOut(V vertex) { 
      if (outNeighbors.containsKey(vertex)) 
       return; 
      outNeighbors.put(vertex, new ArrayList<Edge<V>>()); 
     } 

     public boolean contains (V vertex) { 
      return inNeighbors.containsKey(vertex); 
     } 

     public void add (V from, V to, int cost) { 
      this.addIn(from); 
      this.addIn(to); 
      this.addOut(to); 
      this.addOut(from); 
      inNeighbors.get(from).add(new Edge<V>(to,cost)); 
      outNeighbors.get(to).add(new Edge<V>(from,cost)); 
     } 

     public int outDegree (V vertex) { 
      return inNeighbors.get(vertex).size(); 
     } 

     public int inDegree (V vertex) { 
      return inboundNeighbors(vertex).size(); 
     } 
    } 

    public void bfs() 
    { 
     // BFS uses Queue data structure 
     Queue queue = new LinkedList(); 
     queue.add(this.rootNode); 
     printNode(this.rootNode); 
     rootNode.visited = true; 
     while(!queue.isEmpty()) { 
      Node node = (Node)queue.remove(); 
      Node child=null; 
      while((child=getUnvisitedChildNode(node))!=null) { 
       child.visited=true; 
       printNode(child); 
       queue.add(child); 
      } 
     } 
     // Clear visited property of nodes 
     clearNodes(); 
    } 

的BFS算法我把它從互聯網上，我理解它，但它是爲一般情況下，我不知道如何使它適應我的圖表

Answer 1

這是怎麼解決你的問題。我更喜歡只粘貼最終解決方案，而不用重複整個代碼，以便於閱讀。如果您有興趣查看以前的代碼，請檢查編輯歷史記錄。

package stackoverflow.questions.q19757371; 

import java.io.IOException; 
import java.util.*; 

public class Digraph<V> { 

    public static class Edge<V>{ 
     private V vertex; 
     private int cost; 

     public Edge(V v, int c){ 
      vertex = v; cost = c; 
     } 

     public V getVertex() { 
      return vertex; 
     } 

     public int getCost() { 
      return cost; 
     } 

     @Override 
     public String toString() { 
      return "Edge [vertex=" + vertex + ", cost=" + cost + "]"; 
     } 

    } 

    /** 
    * A Map is used to map each vertex to its list of adjacent vertices. 
    */ 

    private Map<V, List<Edge<V>>> neighbors = new HashMap<V, List<Edge<V>>>(); 

    private int nr_edges; 

    /** 
    * String representation of graph. 
    */ 
    public String toString() { 
     StringBuffer s = new StringBuffer(); 
     for (V v : neighbors.keySet()) 
      s.append("\n " + v + " -> " + neighbors.get(v)); 
     return s.toString(); 
    } 

    /** 
    * Add a vertex to the graph. Nothing happens if vertex is already in graph. 
    */ 
    public void add(V vertex) { 
     if (neighbors.containsKey(vertex)) 
      return; 
     neighbors.put(vertex, new ArrayList<Edge<V>>()); 
    } 

    public int getNumberOfEdges(){ 
     int sum = 0; 
     for(List<Edge<V>> outBounds : neighbors.values()){ 
      sum += outBounds.size(); 
     } 
     return sum; 
    } 

    /** 
    * True iff graph contains vertex. 
    */ 
    public boolean contains(V vertex) { 
     return neighbors.containsKey(vertex); 
    } 

    /** 
    * Add an edge to the graph; if either vertex does not exist, it's added. 
    * This implementation allows the creation of multi-edges and self-loops. 
    */ 
    public void add(V from, V to, int cost) { 
     this.add(from); 
     this.add(to); 
     neighbors.get(from).add(new Edge<V>(to, cost)); 
    } 

    public int outDegree(int vertex) { 
     return neighbors.get(vertex).size(); 
    } 

    public int inDegree(V vertex) { 
     return inboundNeighbors(vertex).size(); 
    } 

    public List<V> outboundNeighbors(V vertex) { 
     List<V> list = new ArrayList<V>(); 
     for(Edge<V> e: neighbors.get(vertex)) 
      list.add(e.vertex); 
     return list; 
    } 

    public List<V> inboundNeighbors(V inboundVertex) { 
     List<V> inList = new ArrayList<V>(); 
     for (V to : neighbors.keySet()) { 
      for (Edge e : neighbors.get(to)) 
       if (e.vertex.equals(inboundVertex)) 
        inList.add(to); 
     } 
     return inList; 
    } 

    public boolean isEdge(V from, V to) { 
     for(Edge<V> e : neighbors.get(from)){ 
      if(e.vertex.equals(to)) 
       return true; 
     } 
     return false; 
    } 

    public int getCost(V from, V to) { 
     for(Edge<V> e : neighbors.get(from)){ 
      if(e.vertex.equals(to)) 
       return e.cost; 
     } 
     return -1; 
    } 

    public static void main(String[] args) throws IOException { 

     Digraph<Integer> graph = new Digraph<Integer>(); 

     graph.add(0); 
     graph.add(1); 
     graph.add(2); 
     graph.add(3); 

     graph.add(0, 1, 1); 
     graph.add(1, 2, 2); 
     graph.add(2, 3, 2); 
     graph.add(3, 0, 2); 
     graph.add(1, 3, 1); 
     graph.add(2, 1, 5); 


     System.out.println("The nr. of vertices is: " + graph.neighbors.keySet().size()); 
     System.out.println("The nr. of edges is: " + graph.getNumberOfEdges()); // to be fixed 
     System.out.println("The current graph: " + graph); 
     System.out.println("In-degrees for 0: " + graph.inDegree(0)); 
     System.out.println("Out-degrees for 0: " + graph.outDegree(0)); 
     System.out.println("In-degrees for 3: " + graph.inDegree(3)); 
     System.out.println("Out-degrees for 3: " + graph.outDegree(3)); 
     System.out.println("Outbounds for 1: "+ graph.outboundNeighbors(1)); 
     System.out.println("Inbounds for 1: "+ graph.inboundNeighbors(1)); 
     System.out.println("(0,2)? " + (graph.isEdge(0, 2) ? "It's an edge" : "It's not an edge")); 
     System.out.println("(1,3)? " + (graph.isEdge(1, 3) ? "It's an edge" : "It's not an edge")); 

     System.out.println("Cost for (1,3)? "+ graph.getCost(1, 3)); 


    } 
} 

This is my result: 
The nr. of vertices is: 4 
The nr. of edges is: 6 
The current graph: 
    0 -> [Edge [vertex=1, cost=1]] 
    1 -> [Edge [vertex=2, cost=2], Edge [vertex=3, cost=1]] 
    2 -> [Edge [vertex=3, cost=2], Edge [vertex=1, cost=5]] 
    3 -> [Edge [vertex=0, cost=2]] 
In-degrees for 0: 1 
Out-degrees for 0: 1 
In-degrees for 3: 2 
Out-degrees for 3: 1 
Outbounds for 1: [2, 3] 
Inbounds for 1: [0, 2] 
(0,2)? It's not an edge 
(1,3)? It's an edge 
Cost for (1,3)? 1 

編輯 我有固定inboundNeighbors(V vertex)和實施getCost(V from, V to)。請注意，只有當你有優勢時，第二個功能纔有意義，並且我們假設成本爲正。否則，我們需要其他考慮，但我認爲你最好發表另外一個問題。

在main我給你提供了一個完整的例子，所以，如果你實驗一些改變，確保你有我在這裏發佈的相同結果。當然，所有的班級都可以寫得更好，但是根據你的經驗，最好簡單一些。