java - 查找加权有向图中两个指定顶点之间是否存在任何路径

Question

我正在尝试实现一种方法 isReachable(E fromKey, E toKey)以确定图中两个指定顶点之间是否存在任何路径。我有一个通用类 Graph<E>使用两个内部数据结构，Vertex和 Edge , 来表示图的顶点和边。这是相关代码:

public class Graph<E extends Comparable<E>> implements GraphAPI<E>
{
    /*
     * number of vertices (size of this graph)
     */
    private long order;
    /**
     * pointer to the list of vertices
     */
    private Vertex first;

    /**
     * A vertex of a graph stores a data item and references
     * to its edge list and the succeeding vertex. The data
     * object extends the comparable interface.
     */
    private class Vertex
    {
        /**
         * pointer to the next vertex
         */
        public Vertex pNextVertex;
        /**
         * the data item
         */
        public E data;
        /**
         * indegree
         */
        public long inDeg;
        /**
         * outdegree
         */
        public long outDeg;
        /**
         * pointer to the edge list
         */
        public Edge pEdge;
        /**
         * Field for tracking vertex accesses
         */
        public long processed;
    }

    /**
     * An edge of a graph contains a reference to the destination
     * vertex, a reference to the succeeding edge in the edge list and
     * the weight of the directed edge.
     */
    private class Edge
    {
        /**
         * pointer to the destination vertex
         */
        public Vertex destination;
        /**
         * weight on this edge
         */
        public Double weight;
        /**
         * pointer to the next edge
         */
        public Edge pNextEdge;
    }
    /**
     * Constructs an empty weighted directed graph
     */
    public Graph()
    {
        first = null;
        order = 0;
    }
}

这是我的思考过程: (1)遍历顶点列表直到到达包含指定fromKey的顶点; (2) 将每个相邻的 Vertex 添加到 fromKey排队； (3) 当队列不为空时，检索并移除队列头部的 Vertex 并将其与 toKey 的键进行比较; (4) 如果匹配则返回真，否则继续搜索每个相邻顶点的边列表。

到目前为止，这是我的方法代码:

/**
 * Determines whether there is an outdirected path between two
 * vertices.
 * @param fromKey - search key of the originating vertex.
 * @param toKey - search key of the destination vertex.
 * @return true on success or false on failure.
 */
public boolean isReachable(E fromKey, E toKey)
{
    ArrayList<Vertex> queue = new ArrayList<Vertex>();
    E tmpKey = fromKey;
    Edge tmpEdge;
    Vertex tmp = first;
    while (tmp != null)
    {
        if (tmp.data.equals(tmpKey))
        {
            tmpEdge = tmp.pEdge;
            while (tmpEdge != null)
            {
                queue.add(tmpEdge.destination);
                tmpEdge = tmpEdge.pNextEdge;
            }
            tmp = first;
            tmpKey = queue.remove(0).data;
            if (tmpKey.equals(toKey))
                return true;
        }
        tmp = tmp.pNextVertex;
    }
    return false;
}

当两个指定键之间的路径存在时它起作用，但当不存在时抛出索引越界错误。

这是我为样本数据追踪的邻接表:

1  -> null
2  -> 1 -> 11 -> 12 -> null
3  -> 2 -> 4 -> null
4  -> null
5  -> 4 -> null
6  -> 5 -> 7 -> 13 -> 14 -> 15 -> null
7  -> 12 -> null
8  -> 7 -> 9 -> 10 -> 11 -> 12 -> null
9  -> 1 -> null
10 -> null
11 -> 1 -> 12 -> null
12 -> null
13 -> null
14 -> 2 -> 3 -> null
15 -> 3 -> 5 -> 14 -> null

当我调用 isReachable(5, 3) ，例如，我得到一个索引越界异常。但是，如果我在 (15, 2) 上调用该方法，它会返回 true。

我不太确定从这里到哪里去。一位 friend 建议尝试使用 BFS 方法来解决这个问题，但我并没有真正听从他的解释。我在正确的轨道上吗？感谢您的帮助。

Answer 1

这是一个基本的图搜索算法，以google“广度优先搜索”为起点。您需要跟踪您访问过的节点，我认为您还没有这样做。

此外，正如我在评论中所说，不要使用 ArrayList 来维护队列，remove 操作很慢，尤其是在开头删除元素数组，因为您必须将所有内容复制 1。直接使用 Queue ( https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html )