자바의 지시 그래프

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 몇 가지 변경 사항을 실험 해 본 결과 완전한 예제가 나와 있으므로 여기에 게시 한 것과 동일한 결과가 있는지 확인하십시오. 분명히 모든 수업은 더 잘 쓸 수 있지만, 경험상 단순하게 만드는 것이 낫습니다.