Graph, BFS, DFS的总结

HackerRank中对Graph的BFS跟DFS讲的不错,再次做个简短总结.
如下图所示
DFS: Go Deep. recursive的过程,需要flag,用来避免陷入infinite loop.
BFS: Go BOARD. iterative的过程, 需要用queue,来记录nextToVisit的点.
bfs-dfs
代码部分:

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * Created by dylan on 10/29/16.
 * Reference: https://www.youtube.com/watch?v=zaBhtODEL0w
 */
public class Graph {
    private HashMap<Integer, Node> nodeLookup = new HashMap<Integer, Node>();


    public Node getNode(int id) {
        if (!nodeLookup.containsKey(id)) return null;
        return nodeLookup.get(id);
    }

    private void addEdge(int source, int destination) {

    }

    public boolean hasPathDFS(int source, int destination) {
        Node s = getNode(source);
        Node d = getNode(destination);
        HashSet<Integer> visited = new HashSet<Integer>();
        return hasPathDFS(s, d, visited);
    }

    private boolean hasPathDFS(Node source, Node destination, HashSet visited) {
        if (visited.contains(source.id)) return false;
        visited.add(source.id);
        if (source == destination) {
            return true;
        }

        for (Node child: source.adjacent) {
            if (hasPathDFS(child, destination, visited)){
                return true;
            }
        }
        return false;
    }

    public boolean hashPathBFS(int source, int destination) {
        return hasPathBFS(this.getNode(source), this.getNode(destination));
    }

    private boolean hasPathBFS(Node source, Node destination) {
        LinkedList<Node> nextToVisit = new LinkedList<Node>();
        HashSet<Integer> visited = new HashSet<Integer>();
        nextToVisit.add(source);
        while(!nextToVisit.isEmpty()) {
            Node node = nextToVisit.remove();
            if (node == destination) {
                return true;
            }

            if (visited.contains(node.id)) {
                continue;
            }
            visited.add(node.id);

            for (Node child: node.adjacent) {
                nextToVisit.add(child);
            }
        }
        return false;

    }


    public static class Node {
        private int id;
        LinkedList<Node> adjacent = new LinkedList<Node>();
        private Node(int id) {
            this.id = id;
        }
    }

}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s