Graph

• 인접 리스트 adj[]
• 방문 리스트 visit[]
• 편의
  • 부모 리스트 parent[]
  • 루트 리스트 root[] - union-find용
• 반전 그래프 (방향 그래프에서)
  • n번의 다익스트라를 2번으로 줄이는 기법
• 사이클
  • 사이클이 없는 것 → 트리
  • 사이클 판별법
    • 무향 그래프
      • union-find
        • 간선 추가시 이미 같은 그룹이라면 사이클

        •   bool unionSet(int a, int b) {
                int rootA = find(a);
                int rootB = find(b);
            
                if (rootA == rootB) return true; // ❌ 이미 같은 그룹이면 사이클 발생
            
                parent[rootB] = rootA; // 두 집합을 합침
                return false;
            }

      • dfs
        • 방문한 노드가 다시 나왔는데, 부모가 아니라면 사이클
    • 방향 그래프
      • 위상 정렬
        • 한 그룹이 안돌아지면
        • (진입 차수 - 1)
        • 진입 차수가 0인 노드를 큐에 넣고, 큐에서 노드를 하나씩 꺼내어 그 노드와 연결된 모든 노드의 진입 차수를 감소시킵니다.
        • 이 과정에서 진입 차수가 0인 노드가 더 이상 없다면 그래프에 사이클이 존재하는 것입니다.
• 평면 그래프
  • 그래프의 모든 간선(변, edge)을 서로 교차하지 않게 그릴 수 있다면 평면그래프라고 한다
  • 4색 정리
    • 평면 그래프가 주어졌을 때, 각 정점에 대하여 인접한 정점과 다른 색으로 칠하는데 필요한 색은 4가지면 충분
• 이동 용어
  • 워크
    • 아무 제약없이 이동
  • 트레일
    • 한번 지나간 간선(edge)은 다시 지나가지 않는 탐색
  • 경로
    • 한번 방문한 정점(node, vertex)은 다시 방문하지 않는 탐색