3

谁能帮我在我的图表上实现 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算法，我理解它，但它适用于一般情况，我不知道如何使其适应我的图表

4

1 回答 1

6

这是解决您的问题的方法。我更喜欢只粘贴最终解决方案而不重复整个代码，以使您更容易阅读。如果您有兴趣了解代码之前的情况，请查看编辑历史记录。

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我为您提供了一个完整的示例中，因此，如果您尝试一些更改，请确保您获得与我在此处发布的相同的结果。当然，所有课程都可以写得更好，但是根据您的经验，最好让事情变得简单。

于 2013-11-03T23:49:32.983 回答