如何找到两个给定顶点之间的路径

我试图写一个方法来找出一个无向图的顶点之间是否存在一条路径，这个无向图用邻接矩阵来表示。
这是我得到的邻接矩阵：

int[][] adj_matrix ={{0,1,0,0},
                     {1,0,1,0},
                     {0,1,0,1},
                     {0,0,0,0}};

这就是我迄今为止所尝试的：

public boolean isPath(int vorigin, int vdestiny)
{

    boolean result = false;
    ArrayList path = new ArrayList<Integer>();
    for (int i = 0; i < adj_matrix.length; i++) {
        for (int j = 0; j < adj_matrix.length; j++) {
            if(adj_matrix[vorigin][j]>0){
                path.add(vorigin);
            }
            if(adj_matrix[vdestiny][j]>0){
                path.add(vdestiny);
                break;
            }
        }
    }
    if(path.contains(vorigin) && path.contains(vdestiny)){
        System.out.println("There is a path");
    }

    return result;
}

如您所见，我的方法只检查每个vertix所在的行，因此它实际上不起作用。我不知道该怎么办。我真的不知道如何检查顶点，它确实是路径的一部分。
我已经对此做了很多研究，但是我找到的大多数方法都实现了邻接列表，这是我不想在本例中使用的。其他一些方法使用递归，这是一个很好的选择，但我想用一种迭代的方式。提前谢谢。

下面是java程序的源代码，用于查找两个给定节点之间是否存在路径。该java程序已在windows系统上成功编译并运行。程序输出如下所示。

public class Path_Between_Nodes
{
    private Map<String, LinkedHashSet<String>> map = new HashMap();

    public void addEdge(String node1, String node2)
    {
        LinkedHashSet<String> adjacent = map.get(node1);
        if (adjacent == null)
        {
            adjacent = new LinkedHashSet();
            map.put(node1, adjacent);
        }
        adjacent.add(node2);
    }

    public void addTwoWayVertex(String node1, String node2)
    {
        addEdge(node1, node2);
        addEdge(node2, node1);
    }

    public boolean isConnected(String node1, String node2)
    {
        Set adjacent = map.get(node1);
        if (adjacent == null)
        {
            return false;
        }
        return adjacent.contains(node2);
    }

    public LinkedList<String> adjacentNodes(String last)
    {
        LinkedHashSet<String> adjacent = map.get(last);
        if (adjacent == null)
        {
            return new LinkedList();
        }
        return new LinkedList<String>(adjacent);
    }

    private static String  START;
    private static String  END;
    private static boolean flag;

    public static void main(String[] args)
    {
        // this graph is directional
        Path_Between_Nodes graph = new Path_Between_Nodes();
        // graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "A");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E"); 
        graph.addEdge("B", "F");
        graph.addEdge("C", "A");
        graph.addEdge("C", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "B");
        graph.addEdge("E", "C");
        graph.addEdge("E", "F");
        // graph.addEdge("F", "B");
        graph.addEdge("F", "C");
        graph.addEdge("F", "E");
        LinkedList<String> visited = new LinkedList();
        System.out.println("Enter the source node:");
        Scanner sc = new Scanner(System.in);
        START = sc.next();
        System.out.println("Enter the destination node:");
        END = sc.next();

        visited.add(START);
        new Path_Between_Nodes().breadthFirst(graph, visited);
        sc.close();
    }

    private void breadthFirst(Path_Between_Nodes graph,
            LinkedList<String> visited)
    {
        LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());

        for (String node : nodes)
        {
            if (visited.contains(node))
            {
                continue;
            }
            if (node.equals(END))
            {
                visited.add(node);
                printPath(visited);
                flag = true;
                visited.removeLast();
                break;
            }
        }

        for (String node : nodes)
        {
            if (visited.contains(node) || node.equals(END))
            {
                continue;
            }
            visited.addLast(node);
            breadthFirst(graph, visited);
            visited.removeLast();
        }
        if (flag == false)
        {
            System.out.println("No path Exists between " + START + " and "
                    + END);
            flag = true;
        }

    }

    private void printPath(LinkedList<String> visited)
    {
        if (flag == false)
            System.out.println("Yes there exists a path between " + START
                    + " and " + END);

        for (String node : visited)
        {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }
}

输出：

$ javac Path_Between_Nodes.java
$ java Path_Between_Nodes

Enter the source node:
E
Enter the destination node:
B
No path Exists between E and B

Enter the source node:
A
Enter the destination node:
E
Yes there exists a path between A and E
A C E 
A C F E

如何找到两个给定顶点之间的路径

1条答案

相关问题

热门标签

最新问答