Depth First Search and the Longest Path in a Graph

Question

I am working on a problem in which you have to find the longest path in a graph. The graph is unique in that it is directed (traffic only goes one way) and you can travel from a node to only one other node in the graph. I wrote some code using a depth first search algorithm to find the answer. My algorithim gives the correct answer for certain graphs and an incorrect answer for others. It also is taking longer than I would like to run.

Here's the code.

import java.util.ArrayList;
import java.util.Scanner;

public class Martians { // 12442

    static int max = 0; // longest chain length
    static int tMax = 0; // longest current chain
    static int starter = 0; // starting Martian of longest length
    static int tStarter = 0;
    static boolean[] visited;
    static boolean[] tVisited;
    static ArrayList<Edge>[] graph;

    static class Edge {
        public int dest = -1; // destination

        public Edge() {
        }

        public Edge(int v) {
            dest = v;
        }
    }

    public static void dfs(int start) { // RECURSIVEEEEE!!!!
        tVisited[start] = true;
        visited[start] = true;
        tMax++;
        if (tMax > max) {
            max = tMax;
            starter = tStarter;
        } 
        else if (tMax == max && tStarter < starter) {
            max = tMax;
            starter = tStarter;
        }

        ArrayList<Edge> edges = graph[start];

        for (Edge e : edges) {
            if (!tVisited[e.dest] && !visited[e.dest]) {// propagates out into graph if the current
                                    // // node has not been visited
                dfs(e.dest);
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int r = in.nextInt();
        for (int q = 1; q <= r; ++q) {
            tMax = 0;
            tStarter = 0;
            int N = in.nextInt();
            graph = new ArrayList[N + 1];
            visited = new boolean[N + 1];
            tVisited = new boolean[N + 1];
            for (int i = 1; i <= N; ++i) {
                graph[i] = new ArrayList<Edge>();
                visited[i] = false;
                tVisited[i] = false;
            }

            for (int i = 1; i <= N; ++i) {
                int u = in.nextInt();
                int v = in.nextInt();
                graph[u].add(new Edge(v));
            }

            for (int i = 1; i <= N; ++i) {
                if (!visited[i]) {
                    tStarter = i;
                    dfs(i);
                }
            }

            System.out.println("Case " + q + ": " + starter);
        }
        in.close();
    }

}

Input looks like this:

The first integer is the number of graphs. After that each lone integer is the number of nodes and the paired integers are the node and the node traveled to respectively. Output is the node at which one should start in order to travel the longest distance in the graph without visiting any nodes more than once (no repeats).

Output:

Case 1: 1
Case 2: 4
Case 3: 3

Does anybody have any advice on what I am doing wrong here?

Get rid of the System.in for your input. It's annoying for us, if we want to reproduce your problem, but I can't imagine it's not annoying for yourself as well when testing. And just checking: you do realize that there is no efficient solution for this problem? — wvdz
Or is it an acyclic graph? In that case you can use topological ordering to find the longest path. — wvdz

Morgen Morgen · Accepted Answer · 2015-03-05T20:22:44

If you are getting incorrect values for some graphs, but not for others, your issue is likely related to how you are keeping track of what nodes you have visited.

I have 2 suggestions:

Give your variables more descriptive names. tVisited looks functionally equivalent to visited and makes reading your code more difficult.
Create a very, very simple graph and add instrumentation to print out the nodes that are visited so that you can track the behavior of your algorithm to make sure that it matches what you are expecting.

Depth First Search and the Longest Path in a Graph

1 Answers