그래프

자바에서 그래프 표현 방법
Hashmap 과 ArrayList 로 표현가능

그래프 구조는 해시맵을 사용
String 키가 노드의 이름이고 ArrayList가 노드의 인접한 이웃을 가짐
BFS (너비우선탐색) 함수에서 구현함. BFS는 큐를 사용해서 구현할 수 있다. c++ 에서는 Queue 는 Queue로 생성해서 사용하면 되는데 자바는 Queue 는 LinkedList로 생성해야한다.
이미 탐색한 노드 체크는 HashSet을 사용해봤다 배열보다는 트리가 탐색이 더 빠를테니까

강의에서는 그냥 ArrayList 로 해결하고 있다
이미 탐색했던 노드도 ArrayList로 해결하고 있다.

BFS 탐색 함수의 시간 복잡도는 O(V+E) 이다. 정점과 간선의 개수를 합한것과 같다
실제로 while 문을 카운트 해보면 V+E 이다.

public class Graph {
    private HashMap<String, ArrayList<String>> graph;

    Graph()
    {
        graph = new HashMap<>();
    }

    void put(String key, String value)
    {
        if(graph.get(key) == null)
        {
            ArrayList<String> newlist = new ArrayList<String>();
            newlist.add(value);
            graph.put(key, newlist);
        }
        else
        {
            ArrayList<String> list = graph.get(key);
            list.add(value);
        }
    }

    boolean searchBFS(String value, String start)
    {
        Queue<ArrayList<String>> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.add(graph.get(start));
        visited.add(start);

        while(queue.isEmpty() == false)
        {
            ArrayList<String> node = queue.remove();
            for(String adjNode : node)
            {
                if(adjNode == value)
                    return true;
                if(visited.contains(adjNode) == false)
                {
                    queue.add(graph.get(adjNode));
                    visited.add(adjNode);
                }

            }
        }
        return false;

    }


	boolean searchDFS(String value, String start)
    {
        Stack<ArrayList<String>> stack = new Stack<>();
        Set<String> visited = new HashSet<>();

        stack.add(graph.get(start));
        visited.add(start);

        while(stack.isEmpty() == false)
        {
            ArrayList<String> node = stack.peek();
            boolean noAdd = true;
            for(String adjNode : node)
            {
                if(adjNode == value)
                    return true;
                if(visited.contains(adjNode) == false)
                {
                    stack.add(graph.get(adjNode));
                    visited.add(adjNode);
                    //System.out.println(adjNode);
                    noAdd = false;
                    break;
                }

            }
            if(noAdd == true)
                stack.pop();
        }
        return false;

    }
}

public class GraphTest {
    public static void main(String[] args) {
        Graph g = new Graph();

        g.put("A", "B");
        g.put("A", "C");
        g.put("B", "A");
        g.put("B", "D");
        g.put("C", "A");
        g.put("C", "G");
        g.put("C", "H");
        g.put("C", "I");
        g.put("D", "B");
        g.put("D", "E");
        g.put("D", "F");
        g.put("E", "D");
        g.put("F", "D");
        g.put("G", "C");
        g.put("H", "C");
        g.put("I", "C");
        g.put("I", "J");
        g.put("J", "I");

        g.searchBFS("H", "A");
    }
}