How to get path-count from source to destination in Un-directed Graph (Non-zero based)?

102 Views Asked by At

I've tried the below code to find possible paths count in an undirected Graph.? But it gave me an error. If I tried with the commented section it works fine. If it supported only for zero-index-based structure, then what is the alternative approach for overcoming this issue.?

import java.util.LinkedList;

public class CountPaths {

static int paths = 0;

static class Graph {
    int vertices;
    LinkedList<Integer>[] adjList;

    Graph(int vertices) {
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEgde(int source, int destination) {
        adjList[source].addFirst(destination);
    }

    public void countPaths(int source, int destination) {
        count(source, destination);
        System.out.println("Source : " + source + " & Destination : " + destination + " Paths :" + paths);
    }

    public void count(int start, int destination) {
        if (start == destination) {
            paths++;
        } else {
            for (int i = 0; i < adjList[start].size(); i++) {
                int ajdacentVertex = adjList[start].get(i);
                count(ajdacentVertex, destination);
            }
        }
    }
}

public static void main(String[] args) {
    /** 
    //This section is works fine
    int vertices = 6;
    
    Graph graph = new Graph(vertices);
    graph.addEgde(0, 1);
    graph.addEgde(0, 2);
    graph.addEgde(1, 2);
    graph.addEgde(1, 3);
    graph.addEgde(3, 4);
    graph.addEgde(2, 3);
    graph.addEgde(4, 5);
    
    int source = 0;
    int destination = 5;
    */
    int vertices = 4;
    
    Graph graph = new Graph(vertices);
    graph.addEgde(1, 2);
    graph.addEgde(2, 3);
    graph.addEgde(4, 1);
    graph.addEgde(4, 3);
    graph.addEgde(3, 1);
    
    int source = 1;
    int destination = 4;
    
    
    graph.countPaths(source, destination);
}

}

Error says as per the below

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
    at CountPaths$Graph.addEgde(CountPaths.java:22)
    at CountPaths.main(CountPaths.java:63)
0

There are 0 best solutions below