DFS,BFS 알고리즘 2

그래프에서 두개의 노드가 서로 찾아갈수 있는 경로가 있는지 확인할수 있는 함수를 구현하시오

class Graph {  
  
    class Node {  
  
        int data;  
        LinkedList<Node> adjacent;  
        boolean marked;  
  
        Node(int data) {  
            this.data = data;  
            this.marked = false;  
            this.adjacent = new LinkedList<Node>();  
        }  
    }  
  
    Node[] nodes;  
  
    Graph(int size) {  
        nodes = new Node[size];  
        for (int i = 0; i < size; i++) {  
            nodes[i] = new Node(i);  
        }  
    }  
  
    // 두 노드의 관계를 저장하는 함수  
    void addEdge(int l1, int l2) {  
        Node n1 = nodes[l1];  
        Node n2 = nodes[l2];  
  
        if (!n1.adjacent.contains(n2)) {  
            n1.adjacent.add(n2);  
        }  
  
        if (!n2.adjacent.contains(n1)) {  
            n2.adjacent.add(n1);  
        }  
    }  
  
    void dfs() {  
        dfs(0);  
    }  
  
    void dfs(int index) {  
        Node root = nodes[index];  
  
        Stack<Node> stack = new Stack<>();  
        stack.push(root);  
        root.marked = true;  
  
        while (!stack.isEmpty()) {  
            Node r = stack.pop();  
  
            for (Node n : r.adjacent) {  
                if (!n.marked) {  
                    n.marked = true;  
                    stack.push(n);  
                }  
            }  
  
            visit(r);  
        }  
    }  
  
    void bfs() {  
        bfs(0);  
    }  
  
    void bfs(int index) {  
        Node root = nodes[index];  
  
        Queue<Node> queue = new LinkedList<>();  
        queue.add(root);  
        root.marked = true;  
  
        while (!queue.isEmpty()) {  
            Node r = queue.poll();  
            for (Node n : r.adjacent) {  
                if (!n.marked) {  
                    n.marked = true;  
                    queue.add(n);  
                }  
            }  
  
            visit(r);  
        }  
    }  
  
    void visit(Node r) {  
        System.out.print(r.data + " ");  
    }  
  
    void initMarks() {  
        for (Node n : nodes) {  
            n.marked = false;  
        }  
    }  
  
    boolean search(int i1, int i2) {  
        return search(nodes[i1], nodes[i2]);  
    }  
  
    boolean search(Node start, Node end) {  
        initMarks();  
        LinkedList<Node> q = new LinkedList<>();  
        q.add(start);  
  
        while(!q.isEmpty()) {  
            Node r = q.poll();  
  
            if(r == end) {  
                return true;  
            }  
  
            for (Node n : r.adjacent) {  
                if (!n.marked) {  
                    n.marked = true;  
                    q.add(n);  
                }  
            }  
        }  
  
        return false;  
    }  
}  
  
  
/*  
그래프에서 두개의 노드가 서로 찾아갈수 있는 경로가 있는지 확인할수 있는 함수를 구현하시오  
* */  
  
public class test2 {  
  
    public static void main(String[] arg) {  
        Graph g = new Graph(9);  
  
        g.addEdge(0, 1);  
        g.addEdge(1, 2);  
        g.addEdge(1, 3);  
  
        //g.dfs();  
        g.bfs();  
    }  
}