그래프

• Walk: 노드나 엣지의 중복을 허용하는 경로
  • Open walk: 시작점과 끝점이 다른 walk
  • Closed walk: 시작점과 끝점이 같은 walk
• Trail: 엣지의 중복이 없는 walk
  • Circuit(=tour): 엣지의 중복이 없고, 시작점과 끝점이 같은 walk (=closed trail)
• Path: 노드와 엣지 모두 중복이 없는 walk
  • Cycle: 노드와 엣지 모두 중복이 없고, 시작점과 끝점이 같은 walk (=closed path)

• 트리
  • 사이클이 없는 그래프
  • 트리 (Tree) 참고
• 이분 그래프 (Bipartite Graph)
  • 다음은 모두 동치
    • 이분 그래프이다
    • 2색 색칠이 가능하다
    • 홀수 길이 사이클을 포함하지 않는다
  • 따라서 트리는 당연히 이분그래프
  • 이분그래프에서만 사용 가능한 알고리즘 - 2색 색칠, 이분 매칭 (Bipartite Matching), …
  • 어떤 그래프가 이분그래프인지 찾기 위해서는 2색 색칠을 시도해보면 된다.
    • teflib.graph.two_coloring 을 돌려서 정상적으로 리턴되면 이분그래프, ValueError가 나오면 이분그래프가 아닌 것이다.
    • 자세한 내용은 2색 색칠 참고
• 선인장

• 무향그래프에서 연결 요소를 찾기
  • DFS/BFS를 돌리거나, Disjoint Set을 이용할 수 있다.
  • 11724 - DFS가 빠르다
• 무향그래프에 사이클이 있는지 확인
  • 그래프가 트리 또는 Forest인지 물어보는 것과 똑같다
  • 전체가 커넥티드라는 조건이 있으면 그냥 |E|=|V|-1 인지만 확인해봐도 된다
  • 그게 없으면 그냥 DFS나 BFS를 돌려서 찾을수 있다. 또는 DisjointSet을 이용해서 찾을수도 있다.
• 유향그래프에 사이클이 있는지 확인
  • 위상정렬 알고리즘을 사용한다
• 가중치 있는 그래프에 음수 사이클이 있는지 확인
  • 벨만포드/SPFA 를 사용한다

• [정리안됨]
• 이론적으로 엣지 리스트, 인접 행렬, 인접 리스트 등으로 표현 가능하지만, PS에서는 몇몇 경우를 제외하고는 대부분은 인접 리스트 형태로 돌리는게 유리하다.
  • 인접행렬이 필요한 경우의 예는 플로이드 알고리즘
  • 엣지 리스트가 필요한 경우의 예는 크루스칼 알고리즘
• 인접리스트 형태의 그래프를 어떻게 구현할 것인가. 기본적으로는 list와 dict, list와 set 중에서 어떤 것을 사용할지를 정해야 한다.
  • 예를 들어 가중치 없는 그래프를 인접리스트로 구현할 때 아래의 네 가지 방식중 어느것으로 통일하느냐 하는 것.

    • g1 = [[1, 2], [], [0]]
      g2 = {0: [1, 2], 1: [], 2: [0]}
      g3 = [{1, 2}, {}, {0}]
      g4 = {0: {1, 2}, 1: {}, 2: {0}}

• 먼저, 노드는 항상 0-based의 정수를 갖는 것을 원칙으로 한다.
  • 물론, 문자열을 노드로 쓰는 것이 필요한 경우도 있고, 몇가지 데이터를 복합해서 표현하는 어떤 상태들을 노드로 표현해야 할 경우도 있다. 하지만 상대적으로 그런 경우는 적은 편이다. 그런 경우에는 노드는 정수로 갖도록 하되, 노드번호와 상태를 매핑하는 맵을 따로 만들어서 참조하도록 처리하도록 하자.
• 노드타입이 항상 0-based의 정수형이 된다면, 외부를 굳이 dict로 쓸 필요는 없다. 외부는 list로 고정하자.
• 내부는 list 로 할지 set으로 할지를 고민해야 한다. weighted 그래프 라면 list[tuple[node, weight]] 또는 dict[node, weight] 중에서 고민해야 한다.
  • 어떤 엣지가 존재하는지 여부를 찾아야 할 필요가 있다면 set을 써야 한다. 그러나 그런 알고리즘은 별로 없다..
  • 중복 엣지가 존재하는 multi graph 라면 list를 써야 한다. 그러나 대부분의 경우는 그냥 중복엣지를 없애서 simple graph 형태로 바꿔서 돌려도 상관 없다. weighted graph라면 같은 노드들을 잇는 엣지들중 가장 가중치가 작은 것을 남기면 되는 경우가 많다. *

• 바깥의 경우에는..
  • 노드가 0~N까지의 정수로 표현된다면 dict를 쓸 이유가 전혀 없다. list를 쓰는 것이 빠르다
  • 그러나 노드가 문자열이나 튜플 등으로 표현된다면 list를 사용하기 위해서는 노드이름-to-index 형태의 맵을 추가로 유지해야 한다.
  • 제네럴한 용법을 고려한다면 dict를 써야 하는게 맞긴 한데.. 그러기에는 ps의 대다수의 문제는 0~N으로 노드를 표현한다.
  • [정수노드 문제의 비율] * [정수노드일때 dict로 손해보는 속도] 와 (1-[정수노드 문제의 비율]) * ([추가 맵 유지에 드는 코딩의 지저분함] + [추가 맵 유지에 드는 속도 저하]) 를 비교해야 할텐데.. 이중에서 가장 궁금한 것은 [정수노드일때 dict로 손해보는 속도]이다.
• 안쪽의 경우에는..
  • set을 쓸 경우, 특정 엣지의 존재 유무를 O(V)가 아닌 O(1)에 알 수 있다는 것이 장점.
    • 하지만 의외로 이 연산이 필요한 경우는 그다지 없다..
  • 단점은 list에 비해서 속도가 떨어지는 문제일텐데..
    • 근데 노드에 연결된 모든 엣지를 순회하는 것은 사실 속도 차이가 별로 없을 것 같다..
      • 테스트해보니 진짜 차이가 미미하다. set이 약간 느리다는 뜻이 아니라 오히려 빠를때도 있고 느릴때도 있다는 말..
    • set에 add할때 list에 append하는 것보다 좀 느릴것 같긴 한데. 이거는 그래프 초기화 할때만 필요한거니까 큰 문제는 아니지 않나?
  • set을 쓰자!
• 바깥쪽의 경우에는..
  • list를 쓰자!
• 결국 최종 형태는 list of set

• 표준적인 형태는 이런 식이다

V, E = [int(x) for x in sys.stdin.readline().split()]
graph = [[] for _ in range(V)]
for _ in range(E):
    u, v = [int(x) for x in sys.stdin.readline().split()]
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)  # 무향 그래프에서만 필요. 유향 그래프라면 이 줄이 없어야 한다.

• 트리 (Tree)에서와 마찬가지로, 1500문제를 넘게 풀 동안 위의 코드를 그대로 짰지만.. 결국 create_graph_from_input 함수를 만들었다.
• 그냥 저 코드를 쓰는것보다 함수를 쓰는게 좀더 느려졌다
  • 24479번 (V⇐100,000, E⇐200,000) 기준으로 그냥 입력받기 - 516ms, 저 함수를 써서 입력 - 556ms가 나왔다.
• 이 함수는 is_undirected 를 인자로 받아서, 매 엣지를 입력받을 때 마다 is_undirected 를 체크해서 역방향 에지도 추가해준다. 매번 is_undirected를 체크하는 것도 시간을 잡아먹을것 같아서 조건 체크를 제거해봤다.. 그걸 없앤 코드 - 544ms로 12ms밖에 단축 안되었다. 그래서 그냥 원래대로 유지학기로 했다

• 중복 간선이 존재하지 않는 경우엔 아래처럼 짠다.
  • 코드
• 중복 간선이 존재할 수 있는 경우에, 가장 작은 가중치를 갖는 간선을 저장해야 한다.
  • 표준적으로 짜면 아래처럼 나오겠지만 가장 빠른 방법은 아니다.

    • V, E = [int(x) for x in sys.stdin.readline().split()]
      wgraph = [{} for _ in range(V)]
      for _ in range(E):
          u, v, w = [int(x) for x in sys.stdin.readline().split()]
          try:
              wgraph[u - 1][v - 1] = min(wgraph[u - 1][v - 1], w)
          except KeyError:
              wgraph[u - 1][v - 1] = w

  • min 호출, wgraph.getitem 호출 등을 줄여서 속도를 올리려면 아래처럼 짤수 있다.

    • V, E = [int(x) for x in sys.stdin.readline().split()]
      wgraph = [{} for _ in range(V)]
      for _ in range(E):
          u, v, w = [int(x) for x in sys.stdin.readline().split()]
          if (e := wgraph[u - 1]).get(v - 1, INF) > w:
              e[v - 1] = w

  • 최단경로문제 (V<20,000, E<300,000) 기준으로, 약 180ms 정도의 차이가 생겼다. 무시할수도 있는 차이이긴 한데.. 라인수마저도 아래쪽이 짧다보니 그냥 아래쪽을 쓰도록 하자.
    • 코드는 여기. 다른 부분은 모두 동일하다. (python 3.11)
      • 위의 방식 코드 : 796ms
      • 아래 방식 코드 : 612ms