/ PROGRAMING, PYTHON

그래프이론

그래프이론

기본적으로 ChatGPT를 이용하여 틀을 잡고 만든 것

  1. BFS,너비우선탐색
  2. DFS,깊이우선탐색
  3. 최단 경로
  4. 최소 스패닝 트리
  5. 연결된 구성요소
  6. 토폴로지 정렬
  7. 최대 흐름
  8. Eulerian Path/Circuit
  9. 이분 그래프
  10. Hamiltonian Path/Circuit
  11. 그래프 색상 지정

  12. 여행하는 세일즈맨 문제

  13. 최단 경로: 가중 간선이 있는 그래프에서 두 정점 사이의 최단 경로를 찾습니다. 이에 대한 일반적인 알고리즘에는 Dijkstra의 알고리즘과 Bellman-Ford 알고리즘이 포함됩니다.

  14. 최소 스패닝 트리: 가중 에지가 있는 그래프가 주어지면 다음의 하위 집합인 최소 스패닝 트리를 찾습니다. 모든 정점을 최소 총 가중치로 연결하는 모서리. 이에 대한 일반적인 알고리즘에는 Kruskal의 알고리즘과 Prim의 알고리즘이 포함됩니다.

  15. 연결된 구성요소: 그래프가 주어졌을 때 모든 정점이 서로 연결되어 있는 하위 그래프인 모든 연결된 구성요소를 찾습니다. . 이것은 깊이 우선 또는 너비 우선 검색으로 해결할 수 있습니다.

  16. 토폴로지 정렬: 방향성 비순환 그래프가 주어지면 정점의 방향을 유지하는 방식으로 정점을 정렬합니다. 가장자리. 이는 Kahn의 알고리즘이나 깊이 우선 검색을 사용하여 수행할 수 있습니다.

  17. 최대 흐름: 가장자리에 용량이 있는 그래프가 주어지면 보낼 수 있는 최대 흐름량을 찾습니다. 소스 정점에서 싱크 정점으로. 이는 Ford-Fulkerson 알고리즘 또는 Edmonds-Karp 알고리즘을 사용하여 해결할 수 있습니다.

  18. Eulerian Path/Circuit: 주어진 그래프에서 모든 에지를 정확히 가로지르는 경로 또는 회로를 찾습니다. 한 번. 그래프에 차수가 홀수인 정점이 정확히 두 개 있으면 오일러 경로가 존재하고, 모든 정점의 차수가 짝수이면 오일러 회로가 존재합니다. 이는 Fleury의 알고리즘 또는 Hierholzer의 알고리즘을 사용하여 해결할 수 있습니다.

  19. 이분 그래프: 무방향 그래프가 있을 때, 이분인지 확인합니다. 즉, 동일한 세트의 두 정점이 모서리로 연결되지 않도록 해당 정점을 두 세트로 나눌 수 있음을 의미합니다. 이는 깊이 우선 검색 또는 너비 우선 검색을 사용하여 해결할 수 있습니다.

  20. Hamiltonian Path/Circuit: 주어진 그래프에서 모든 정점을 정확히 방문하는 경로 또는 회로를 찾습니다. 한 번. 이것은 잘 알려진 NP-완전 문제이므로 일반적으로 이를 해결할 수 있는 효율적인 알고리즘은 알려져 있지 않습니다. 그러나 대략적인 솔루션을 찾는 데 사용할 수 있는 휴리스틱 알고리즘이 있습니다.

  21. 그래프 색상 지정: 무방향 그래프가 주어졌을 때 인접한 두 꼭지점이 서로 겹치지 않도록 꼭지점에 색상을 할당합니다. 가능한 최소한의 색상을 사용하여 동일한 색상. 이것은 잘 알려진 NP-완전 문제이기도 하지만 근사해를 찾는 데 사용할 수 있는 휴리스틱 알고리즘이 몇 가지 있습니다.

  22. 여행하는 세일즈맨 문제: 가중 에지, 모든 꼭짓점을 정확히 한 번 방문하는 가장 짧은 해밀턴 회로를 찾습니다. 이것은 잘 알려진 또 다른 NP-완전 문제이지만 이를 해결하는 데 사용할 수 있는 몇 가지 정확하고 근사한 알고리즘이 있습니다.