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. 유클리드 알고리즘
[정렬 알고리즘] [검색 알고리즘]
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램,프로그래밍
      1.   프로그래밍 언어론
      2.   구조적 프로그래밍
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 알고리즘 설계
            3. 계산 복잡도
            4. 하노이 탑
            5. 순서도
            6. 재귀 호출
        1.   알고리즘 종류
              1. 알고리즘 분류
              2. 그래프 알고리즘
              3. 최대 최소 구하기
              4. 유클리드 알고리즘
          1.   정렬 알고리즘
          2.   검색 알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     요약목록     참고문헌