java - 无向图上的DFS？

Question

我正在研究一个由在特定学校成为朋友的学生组成的无向友谊图。我想使用 dfs 获得派系（图中的所有连接子图）。但由于某种原因，我的 dfs 无法正常工作。对算法或代码的任何建议表示赞赏

这是手动创建的示例图..

import java.util.LinkedHashMap;


public class DFS {

    /**
     * @param args
     */

    class Node {

        String personName, schoolName;
        Node next;

        public Node(String personName, String schoolName, Node next) {

            this.personName = personName;
            this.schoolName = schoolName;
            this.next = next;
        }

        public String toString() {

            return this.personName + " " + this.schoolName;

        }

    }

    public Node[] build() {

        Node[] graph = new Node[6];

        for (int i = 0; i < graph.length; i++) {

            Node temp = new Node(Integer.toString(i + 1), "MIT", null);
            graph[i] = temp;

        }

        graph[0].next = new Node("2", "MIT", null);

        graph[1].next = new Node("1", "MIT", null);
        graph[1].next.next = new Node("3", "MIT", null);
        graph[1].next.next.next = new Node("4", "MIT", null);

        graph[2].next = new Node("2", "MIT", null);
        graph[2].next.next = new Node("4", "MIT", null);

        graph[3].next = new Node("3", "MIT", null);
        graph[3].next.next = new Node("2", "MIT", null);    

        graph[4].next = new Node("6", "MIT", null);
        graph[5].next = new Node("5", "MIT", null);

        printGraph(graph);

        return graph;

    }

    public void dfsDriver() {

        Node[] graph = build();

        LinkedHashMap<String, Integer> names = new LinkedHashMap<String, Integer>();

        int count = 0;

        for (int i = 0; i < graph.length; i++) {

            if (graph[i] != null) {

                names.put(graph[i].personName, count);

                count++;
            }               
        }

        boolean[] visited = new boolean[graph.length];

        for (int v = 0; v < visited.length; v++) {

            visited[v] = false;
        }


        for (int i = 0; i < graph.length; i++) {

            if (graph[i] != null) {

                if (!visited[i]) {

                        System.out.println("Starting at " + graph[i].personName);

                        dfs(i, visited, names, graph);                      
                }               
            }               
        }

    }

    private void dfs(int i, boolean[] visited, LinkedHashMap<String, Integer> names, Node[] subGraph) {

        visited[i] = true;

        for (Node e = subGraph[i].next; e != null; e = e.next) {

            System.out.println("visiting " + e.personName);

            int index = names.get(e.personName);

            if (!visited[index]) {

                dfs(index, visited, names, subGraph);

            }           
        }

    }   

    public void printGraph(Node[] list) {

        System.out.println();

        for (int i = 0; i < list.length; i++) {

            if (list[i] != null) {

                System.out.print(list[i]);

                for (Node a = list[i].next; a != null; a = a.next) {

                    System.out.print(" " + a);

                }

                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        DFS a = new DFS();

        a.dfsDriver();

    }

}

Answer 1

#1 : The graph creation is inefficient. See this method in your code:

public Node[] build() {

There are 6 nodes that you wanted and look how many times are you calling "new Node". Its 6 + 10 times..Try to modify your data structures so that they suit to the inputs. The current DS is :

class Node {
    String personName, schoolName;
    Node next;

Think about modifying this so that each node can "point" to multiple other nodes without creating new object for its frends every time.

#2 Confusing print statement in dfs method()

It should be like this:

private void dfs(int i, boolean[] visited, 
                 LinkedHashMap<String, Integer> names, Node[] subGraph) {
    visited[i] = true;
    for (Node e = subGraph[i].next; e != null; e = e.next) {
        int index = names.get(e.personName);
        if (!visited[index]) {
            System.out.println("visiting " + e.personName);
            dfs(index, visited, names, subGraph);
        }           
    }
}  

#3: There is no mechanism to store the end results

You want all connected subgraphs from the main graph. However I dont see any provision to store/ mark the graph. You can modify the 2nd for loop inside public void dfsDriver() method so that it will create a new graph from the NEW nodes visited after each iteration.