Graph Algorithm   그래프 알고리즘

(2016-12-12)
1. 그래프 알고리즘그래프 순회(Graph Traversal)/그래프 탐색/그래프 검색(Graph Search) 방법
     - 그래프 상의 모든 정점을 한번씩 만 방문하는 방법
        . 깊이 우선 탐색 방법 (Depth First Search, DFS)
           .. 갈 수 있는데까지 가보다가 더이상 진행 못하면 거슬러 올라가며, 아직 가보지
              못한 노드가 있으면 그 노드를 따라갈 수 있는데까지 가보는 방법
        . 너비 우선 탐색 방법 (Breadth First Serach, BFS)
           .. 우선 가까운 인접 노드를 모두 방문한 후에, 그 다음 가까운 인접 노드를 방문
              하며 진행하는 방법 

  ㅇ 신장 트리(생성 트리 : 루프가 없는 그래프) 작성 방법 
     - 그래프의 모든 정점을 한번씩 만 방문하며 모두를 포함하는 부분 그래프(트리)
        . 연결그래프에서 그래프 순회(Graph Traversal)를 하면,
        . n-1개 간선(링크)를 이동하면서 모든 정점을 방문하게 되므로,
        . 결국 이것이 신장트리(생성트리)를 만들게 됨

  ㅇ 최소 생성트리(minimum spanning tree) 작성 알고리즘
     - 연결선에 부여된 가중치 합이 최소가되는 신장트리를 작성하는 알고리즘
        . 쿠르스칼(Kruskal) 알고리즘
           .. 루프를 만들지 않으면서 최소 가중치 연결선을 하나씩 추가하며 신장트리 작성
        . 프림(Prim) 알고리즘
           .. 임의 정점부터 시작하며 연결된 연결선 중 최소 가중치를 갖는 연결선을 추가하고,
           .. 루프를 만들지 않으면서 점차 선택된 정점들에 부속된 연결선들 중
              최소 가중치 연결선을 추가하며 신장트리 작성               

  ㅇ 최단 경로 알고리즘 (Shortest Path Algorithm) 탐색 알고리즘
     - Dijkstra 알고리즘, 플로이드(Floyd) 알고리즘 등
     - 두 정점 간을 이동할 때 가중치 합이 최소가 되는 경로를 찾는 알고리즘


[알고리즘 종류] 1. 알고리즘 분류 2. 탐색 알고리즘 3. 정렬 알고리즘 4. 그래프 알고리즘 5. 해쉬 알고리즘 6. 해싱 탐색 7. 최대 최소 구하기 8. 유클리드 알고리즘

 
        최근수정     요약목록(시험중)     참고문헌