How to find if a path exists between two given vertex JAVA

Question

Im trying to write a method to find whether or not a path exists between to vertex in an undirected graph that is representned in an adjacency matrix.

This is the adjacency matrix that I have:

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

And this is what I have tried so far:

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;
}

As you can see, my method only check the row where each vertix is located, so it wouldn't be really functional. And I'm on a loss on how to proceed here. I don't really know how to check for the vertex that would indeed be part of the path.

I have been doing quite a bit of research on this, but most of the methods that I have been able to find implement adjacency lists, which is something I dont want to use in this case. And some other methods use recursion, which is a good alternative but I would like to do it on an iterative way. Thanks in advance.

Answer 1

Here is the source code of the Java Program to Find Whether a Path Exists Between 2 Given Nodes. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

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();
    }
}

Output:

$ 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