遍历HashMap

Question

package sx1;

import java.util.*;

public class Graph<V> {
    // map : key = vertex, value = set of neighboring vertices
    private HashMap<V, HashSet<V>> map;

    // number of edges
    private int edgeCount;


    public int count2Neighbors(V v) {
        //count the number of nodes that are within 2 distances

    }


    /**
     * Creates an empty graph
     */
    public Graph() {
        map = new HashMap<V, HashSet<V>>();
    }

    /**
     * Return number of vertices
     */
    public int numV() {
        return map.keySet().size();
    }

    /**
     * Return number of edges
     */
    public int numE() {
        return edgeCount;
    }

    /**
     * Return the degree of vertex
     * 
     * @param v
     * - the data of the vertex to get the degree of
     * 
     * @return the degree of v, 0 if v does not exist in the Graph
     */
    public int degree(V v) {
        if (!map.containsKey(v))
            return 0;
        else
            return map.get(v).size();
    }

    /**
     * Adds an undirected edge between vertices u and v adding new vertices they
     * do not exist in the Graph already.
     * 
     * @param u
     * - the data of the first vertex
     * 
     * @param v
     * - the data of the second vertex
     * 
     * @throws NullPointerException
     * - if u or v is null
     * 
     * @throws IllegalArgumentException
     * - if u.equals(v) is true
     */
    public void addEdge(V u, V v) {
        if (u == null || v == null)
            throw new NullPointerException("Vertices may not be null.");

        if (u.equals(v))
            throw new IllegalArgumentException("Self loops are not allowed.");

        addVertex(u);
        addVertex(v);

        if (!hasEdge(u, v))
            edgeCount++;

        map.get(u).add(v);
        map.get(v).add(u);
    }

    /**
     * Add a new vertex with no neighbors (if it does not yet exist)
     * 
     * @param v
     * - the data of the new vertex
     */
    public void addVertex(V v) {
        if (hasVertex(v))
            return;

        map.put(v, new HashSet<V>());
    }

    /**
     * Returns an Iterable set of all vertices in the Graph
     */
    public Iterable<V> vertices() {
        return map.keySet();
    }

    /**
     * Returns an Iterable set of the neighbors of the given vertex
     * 
     * @param v
     * - the vertex to to Iterate over
     * @return an Iterator over the neighbors of v, Iterator over an empty set
     * if v does not exist in the Graph
     */
    public Iterable<V> adjacentTo(V v) {
        // return empty set iterator if v isn't in graph
        if (!hasVertex(v))
            return new HashSet<V>();
        else
            return map.get(v);
    }

    /**
     * Test if a vertex in the graph
     * 
     * @param v
     * - the data of the vertex to search for
     * @return true if v was found, false otherwise
     */
    public boolean hasVertex(V v) {
        return map.containsKey(v);
    }

    /**
     * Test if (u, v) an edge in the graph
     * 
     * @param u
     * - the data of the first vertex in the Edge
     * @param v
     * - the data of the second vertex in the Edge
     * @return true if (u, v) exists in the Graph, false otherwise
     */
    public boolean hasEdge(V u, V v) {
        if (!hasVertex(u))
            return false;

        return map.get(u).contains(v);
    }

    /**
     * Removes the given vertex from the Graph
     * 
     * @param v
     * - that data of the vertex to remove
     */
    public void removeVertex(V v) {
        if (!hasVertex(v))
            return;

        edgeCount -= degree(v);

        // Remove v from the vertex list
        map.remove(v);

        // Remove all incoming edges to v
        for (V other : map.keySet())
            map.get(other).remove(v);
    }

    /**
     * Removes the given edge from the Graph
     * 
     * @param u
     * - the data of the first vertex in the Edge
     * @param v
     * - the data of the second vertex in the Edge
     */
    public void removeEdge(V u, V v) {
        if (!hasVertex(u) || !hasVertex(v))
            return;

        map.get(u).remove(v);
        map.get(v).remove(u);

        edgeCount--;
    }

    /**
     * Returns a String representation of the Graph - Not very efficient,
     * intended for debugging
     */
    public String toString() {
        String s = "";
        for (V f : map.keySet()) {
            s += f.toString() + ": ";
            for (V e : map.get(f)) {
                s += e.toString() + " ";
            }
            s += "\n";
        }
        return s;
    }
}

我正在尝试编写一种方法count2Neighbors(V v)以计算距离在2或更短距离内的所有节点，包括我调用它的节点。你们到底会怎么做？我当时在想，也许遍历后序遍历可能是遍历而不是重复计算事物的最佳方法，等等……我可以制作一个新的哈希图，并向其中添加所有邻居，然后返回它的大小。听起来合理吗？

Answer 1

您可以尝试使用BFS

public int count2Neighbors(int vertex) {
        boolean visited[] = new boolean[map.size()];
        Queue<Integer> queue = new ArrayDeque<>();

        visited[vertex] = true;
        queue.add(vertex);

        int distance = 0;
        int count = 0;
        while (!queue.isEmpty()) {
            int v = queue.poll();
            Set<Integer> adj = map.get(v);
            distance++;
            if (distance <= 2) {
                for (Integer w : adj) {
                    if (!visited[w]) {
                        visited[w] = true;
                        queue.add(w);
                        count++;
                    }
                }
            }
        }
        return count;
    }