1. 그래프
   1. 개론
      1. 일반적으로 알고 있는 그래프와는 조금 다름
      2. 노드와 에지
         1. 노드 : 중간 지점
         2. 에지 : 노드끼리를 연결하는 길
      3. 광범위한 의미
         1. 하나의 네트워크의 기호적인 표현
            1. 전화
            2. www
            3. 전자 회로
            4. 인공 신경망
   2. 좀 더 형식적인 기술
      1. G = {N, E}
         1. N : 0 ~ (N-1)
         2. E : 3-5 / 19-7
            1. 가중치 존재
            2. 거리
            3. 길의 특성(오르막, 늪 등)
   3. 트리
      1. 비순환인 모든 그래프를 포함하는 그래프의 부분집합
   4. 그래프 밀도
      1. 밀집하거나
      2. 성기거나
   5. 다이그래프
      1. 에지의 방향 존재
      2. 16-6 : 16->6 ( ! 6->16 )
         1. 16 : 근원 노드(source node)
         2. 6 : 목적 노드(destination node)
      3. 무방향 그래프 == 쌍방향 다이그래프
   6. 게임 AI에서의 그래프
      1. 항해 그래프(navgraph)
         1. 게임 에이전트가 방문할 수 있는 게임 환경의 모든 장소와 그 지점들 사이의 모든 연결의 추상화
      2. 종속 그래프(dependency graph)
         1. 여러 빌딩, 물자, 유닛과 선우에 적용될 수 있는 기술들 사이의 종속성을 표현하기 위해 사용
      3. 상태 그래프(state graph)
         1. 시스템이 존재할 수 있는 모든 가능한 상태와 그 상태들 사이의 전환을 표현
         2. 루트 노드
         3. 부모 상태 - 자식 상태
         4. 분기율(branching factor)
            1. 각 부모 노드에서 퍼져 나가는 자식 노드의 평균 개수
         5. 대부분 분기율이 높기 때문에 목표 상태 쪽으로 탐색을 지시해 한 번에 몇 개의 노드만 생성되고 탐색
2. 그래프 클래스 구현하기
   1. 개론
      1. 표현 자료구조
         1. 인접 행렬(adjacency matrix)
            1. 직관적
            2. 용량 비효율
            3. N의 제곱
         2. 인접 리스트(adjacency list)
            1. 성긴 그래프에 효율적
            2. 공간 낭비 x
            3. N+E
   2. GraphNode Class
      1. 노드가 필요로 하는 최소 정보를 캡슐화
      2. template< class extra_info = void* > class NavGraphNode : public GraphNode
   3. GraphEdge Class
      1. 두 개의 노드 사이의 연결을 나타내기 위해 필요한 기본 정보를 캡슐화
      2. 가중치
         1. 가중치가 동일하다면 그 필드를 생략함으로써 메모리 절약
         2. 가중치가 두 노드 사이의 거리라면 Distance 함수 사용
   4. SparseGraph Class
      1. 노드와 에지에 접근할 수 있게끔
         1. 인텍스 사용
      2. 컨테이너
         1. vector<node_type> NodeVector
         2. list<edge_type> EdgeList
         3. vector<EdgeList> EdgeListVector
3. 그래프 탐색 알고리즘
   1. 개론
      1. 탐색 알고리즘이 하는 일
         1. 그래프의 모든 노드 방문
         2. 두 노드 사이의 어떠한 경로를 찾음
         3. 두 노드 사이의 최적 경로를 찾음
   2. 무정보 그래프 탐색
      1. 에지 비용에 대한 언급 없이 그래프 탐색
      2. 깊이 우선 탐색
         1. 모든 노드와 에지가 방문될 것임을 보장
         2. 알고리즘 구현
            1. 멤버
            2. m_Visited : unvisited
            3. 방문된 모든 노드들의 인덱스 기록
            4. m_Route : no_parent_assigned
            5. 목표까지의 경로 보유
            6. std::Stack 사용
            7. 순서
            8. 생성자 -> Search()
            9. std::stack<const Edge*> stack;
            10. Edge Dummy();
            11. stack.push(&Dummy);
            12. while(!stack.empty())
            13. const Edge* Next = stack.top()
            14. stack.pop()
            15. m_Route[Next->To] = Next->From()
            16. m_Visited[Next->To()] = visited
            17. if(Next->To() == m_iTarget) return true;
            18. for( ConstEdgeItr )
            19. if(m_Visited[pE->To()] == unvisited) stack.push(pE);
            20. GetPathToTarget() 에서 목표까지의 경로 반환
      3. 너비 우선 탐색
         1. 가장 적은 에지를 방문하는 경로를 보장
         2. 멤버
            1. m_Visited : unvisited
            2. 방문된 모든 노드들의 인덱스 기록
            3. m_Route : no_parent_assigned
            4. 목표까지의 경로 보유
            5. std::queue 사용
         3. 알고리즘 구현
            1. std::queue<const Edge*> Q
            2. const Edge Dummy()
            3. Q.push(&Dummy)
            4. m_Visited[m_iSource] = visited;
            5. while(!Q.empty())
            6. const Edge* Next = Q.front();
            7. Q.pop();
            8. m_Route[Next->To()] = Next->From();
            9. if(Next->To() == m_iTarget) return true;
            10. for(ConstEdgeItr)
            11. if(m_Visited[pE->To()] = visited)
            12. Q.push(pE);
            13. m_Visited[pE->To()] = visited;
   3. 비용 기반 그래프 탐색