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. 최소비용 신장트리

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