Graph Algorithm   그래프 알고리즘

(2020-03-10)
Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공업일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
정보기술(IT) >   1. 정보기술
[전산기초]
[컴퓨터구조]
[프로그래밍]
[데이터베이스]
[소프트웨어 공학]
[운영체제]
[정보보호/보안]
[IT 기타기술]
프로그래밍 >   1. 프로그램, 프로그래밍
[프로그래밍 언어론]
[프로그래밍 방법론]
[객체지향 프로그래밍]
[자료표현코드]
[자료구조]
[알고리즘]
[시스템 소프트웨어]
[프로그래밍언어 종류]
[프로그래밍 기타일반]
자료구조 >   1. 자료구조
  2. 자료구조 종류
[선형 자료구조 (리스트 등)]
[비선형 자료구조 (트리,그래프)]
[기타 자료구조]
[자료구조 기타일반]
비선형 자료구조 (트리,그래프) > [그래프]
[트리]
그래프 >   1. 그래프
  2. 그래프 종류
  3. 그래프 표현
[그래프 용어]
[그래프 알고리즘]
그래프 알고리즘   1. 그래프 알고리즘
  2. 그래프 순회
  3. 최단 경로
  4. 최소비용 신장트리

Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공업일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
정보기술(IT) >   1. 정보기술
[전산기초]
[컴퓨터구조]
[프로그래밍]
[데이터베이스]
[소프트웨어 공학]
[운영체제]
[정보보호/보안]
[IT 기타기술]
프로그래밍 >   1. 프로그램, 프로그래밍
[프로그래밍 언어론]
[프로그래밍 방법론]
[객체지향 프로그래밍]
[자료표현코드]
[자료구조]
[알고리즘]
[시스템 소프트웨어]
[프로그래밍언어 종류]
[프로그래밍 기타일반]
알고리즘 >   1. 알고리즘
  2. 순서도
  3. 재귀 호출
[알고리즘 효율성]
[알고리즘 종류]
[알고리즘 전략]
[(기타 알고리즘)]
알고리즘 종류   1. 알고리즘 분류
  2. 그래프 알고리즘
[기초 알고리즘]
[정렬 알고리즘]
[검색 알고리즘]

1. 그래프 알고리즘 구분그래프 순회 방법 (Graph Traversal)
     - 그래프 상의 모든 정점을 한번씩 만 방문하거나, 목표 정점을 찾아가는 방법
     - (용도) 특정 정점에서 다른 정점으로 갈수 있는지 서로 연결되었는지 등을 확인하는데에 사용 
     - (명칭) 때론, 그래프 탐색/그래프 검색(Graph Search) 방법 이라고 함
     - (대표적인 例 둘)
        . 깊이 우선 탐색 (Depth First Search, DFS)
        . 너비 우선 탐색 (Breadth First Serach, BFS)

  ㅇ 생성 트리/신장 트리 작성 방법 (Spanning Tree)
     - (생성 트리/신장 트리 이란? : 루프가 없는 그래프를 말함)
     - 그래프의 모든 정점을 한번씩 만 방문하며 (특히, 루프없이), 
        . 결국, 모두를 포함하되 루프는 없게되는, 부분 그래프(트리)를 작성하는 방법
     - (방법)
        . 연결그래프에서 그래프 순회(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.   자료구조
            1. 자료구조
            2. 자료구조 종류
        1.   선형 자료구조 (리스트 등)
        2.   비선형 자료구조 (트리,그래프)
          1.   그래프
                1. 그래프
                2. 그래프 종류
                3. 그래프 표현
            1.   그래프 용어
            2.   그래프 알고리즘
              1.   1. 그래프 알고리즘
                  2. 그래프 순회
                  3. 최단 경로
                  4. 최소비용 신장트리
          2.   트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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