java - 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)ました。2 番目の関数は、優位性があり、正のコストを想定している場合にのみ意味があることに注意してください。それ以外の場合は、別の考慮事項が必要ですが、別の質問を投稿した方がよいと思います。

で完全な例を提供したので、いくつmainかの変更を試す場合は、ここに投稿したのと同じ結果が得られることを確認してください。確かに、すべてのクラスをより適切に記述することができますが、経験からすると、物事を単純にする方が優れています。