그래프 표현

(2020-03-17)

Adjaency Matrix, 인접 행렬, Adjaency List, 인접 리스트

1. [자료구조]  그래프의 표현 

  ㅇ [기초 표현]  그림으로 나타냄
  ㅇ [기호 표현]  정점들의 관계를 나타내는 연결선들의 집합으로 표현 : G = (V,E)
  ㅇ [행렬 표현]  인접 행렬 (Adjacency Matrix), 부속/근접 행렬 (Incidence Matrix)
  ㅇ [리스트 표현]  인접 리스트 (Adjaency List)


2. [자료구조]  인접 행렬 (Adjaency Matrix)그래프행렬로 표현하는 방식 중 하나
     - 각 행,열을 정점으로 하고, 원소 값에 연결선의 수를 부여

  ㅇ 방향 그래프의 인접 행렬 표현 例
     - 행렬 원소 값 : 정점들 간에 화살의 개수
     
        . v1 자신 간에 화살 1개
        . v1에서 v2로의 화살 0개
        . v2에서 v3로의 화살 2개

     - 특징
        . 타 정점을 가리키는 정점인 경우에 만 값(연결 관계)이 부여됨

  ㅇ 무 방향 그래프의 인접 행렬 표현 例
     - 행렬 원소 값 : 정점들 간에 결합되는 간선의 개수
     
        . v1,v3가 자기 자신과 결합되는 간선 수 2개
        . v2와 v3 간에 결합 간선 수 2개
        . v1와 v3 간에 결합 간선 수 1개

     - 특징
        . 대칭 : 대칭 행렬의 형태를 갖음
        . 차수 : 행 또는 열을 합해 얻은 수와 같음


3. [자료구조]  부속 행렬,근접 행렬 (Incidence Matrix)그래프행렬로 표현하는 방식 중 하나
     - 각 행이, 정점 또는 연결선을, 각 열이, 연결선 또는 정점을 나타내도록 행렬 표현


4. [자료구조]  인접 리스트 (Adjaency List)그래프의 각 정점들을 연결 리스트(Linked List)로 표현한 것
      
     - 우선, 모든 정점들을 배열로써 표현
     - 그리고, 각 정점(배열 원소)에다가 인접한 정점들을 연결 리스트로 표현

  ㅇ 특징
     - 존재 않는 간선을 표현 않으므로 기억장소 낭비가 적음


[그래프] 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. 그래프 표현
                4. 평면 그래프
            1.   그래프 용어
            2.   그래프 알고리즘
          2.   트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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