Graph Algorithm   그래프 알고리즘

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

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

1. 그래프 알고리즘을 크게 구분하면,그래프 내 모든 정점을 순회하는 방법
  ㅇ 작업 사이에 특정 의존(순서)관계가 있을 때 이를 정렬시키는 방법
  ㅇ 루프가 없는 그래프(신장 트리)를 생성시키는 방법
  ㅇ 최소 신장 트리를 작성하는 방법
  ㅇ 그래프 상에서 최단 경로를 탐색하는 방법


2. 그래프 순회 방법 (Graph Traversal)그래프 상의 모든 정점을 한번씩 만 방문하며, 목표 정점을 찾아가는 방법

     - (용도) 특정 정점에서 다른 정점으로 갈수 있는지 서로 연결되었는지 등을 확인하는데에 사용 
     - (명칭) 때론, 그래프 탐색/그래프 검색(Graph Search) 방법 이라고 함
     - (대표적인 例 둘)
        . 깊이 우선 탐색 (Depth First Search, DFS)
        . 너비 우선 탐색 (Breadth First Serach, BFS)


3. 작업 순서의 정렬 방법

  ㅇ 작업 사이에 특정한 의존 관계(선행 의무)가 있는 경우에 순서화시키는 정렬 방법을 찾음
  ㅇ (대표적인 例) : 위상 정렬 (Topological Ordering) 알고리즘
     - 방향성 비순환 그래프에서, 1 이상의 선형적 순서를(1 이상 방법으로 정렬하여) 생성해 냄


4. 생성 트리/신장 트리의 작성 방법 (Spanning Tree)

  ㅇ 여기서, 생성 트리/신장 트리 이란?
     - 루프가 없는 그래프를 말함

  ㅇ 그래프의 모든 정점을 한번씩 만 방문하며 (특히, 루프없이), 
     - 결국, 모두를 포함하되 루프는 없게되는, 부분 그래프(트리)를 작성하는 방법

  ㅇ (방법)
     - 연결그래프에서 그래프 순회(Graph Traversal)를 하면,
     - n-1개 간선(링크)를 이동하면서 모든 정점을 방문하게 되므로,
     - 결국 이것이 신장트리(생성트리)를 만들게 됨


5. 최소 생성트리/신장트리 작성 알고리즘 (Minimum Spanning Tree)

  ㅇ 연결선에 부여된 가중치 합이 최소가 되도록 신장트리를 작성하는 알고리즘

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


6. 최단 경로 탐색 알고리즘 (Shortest Path Algorithm)

  ㅇ 두 정점 간에, 가중치 합이 최소가 되는 경로를 찾는 알고리즘최단 경로 문제의 종류
     - 단일 출발지,단일 목적지 최단 경로 문제 
     - 단일 출발지 최단경로 문제
     - 단일 도착지 최단경로 문제
     - 모든 쌍 최단경로 문제

  ㅇ (대표적인 例)
     - Dijkstra 알고리즘  :  (단일 출발지 최단경로 문제)
        . 단일 시작점으로부터 모든 정점까지, 최단 경로를 하나씩 결정하면서,
        . 점차 그래프 전체를 탐색해나감
     - 벨만 포드 알고리즘  :  (단일 출발지 최단경로 문제)
        . 모든 간선에 대해 (모든 정점 쌍 간에), 가중치를 계산, 갱신해가며,
        . 가중치가 변경되지 않을 때까지 처리를 반복해나감
     - 플로이드 알고리즘 등  :  (모든 쌍 최단경로 문제) 
        . 우선 그래프를 표현하는 인접 행렬을 구해 놓고,
        . 두 정점 간에 가능한 모든 경로 비용들을 비교하여 최단 거리를 구하며, 이를 저장하고,
        . 전체 두 정점 간에 이를 적용하며, 최소 비용 테이블을 구함


[그래프 알고리즘] 1. 그래프 알고리즘 2. 그래프 순회 (DFS,BFS) 3. 최단 경로 4. 다익스트라 알고리즘 5. 최소비용 신장트리 6. 위상 정렬 7. 플로이드 알고리즘

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