Graph

Graph

• [그림] 자료구조의 Graph의 모습

용어정리

• 직접적인 관계: 두 점 사이를 이어주는 선.

• 간접적인 관계: 몇 개의 점과 선에 걸쳐 이어짐.

• 정점(vertex) : 그래프에서 하나의 점 // 간선(edge) : 하나의 선
  
  [그림] 4개의 정점 : 0,1,2,3 / 간선 0-3 , 0-2 , 0-1, 1-2 (3하고 1,2은 관계가 없다라고 표현한다; 간선이 없기 떄문에)

• 비가중치 그래프: 추가적인 정보를 파악할 수 없는 그래프

  • 비가중치 그래프는 (연결의 강도)가 얼마나 되는지 적혀 있지 않다.
  • 위의 그래프를 객체로 비가중치 그래프로 표현

  const isConnected = {
  0: {
    1: true,
    2: true,
    3: true
  },
  1: {
    0: true,
    2: true
  },
  2: {
    0: true,
    1: true
  },
  3: {
    0: true
  }
  }

• 가중치 그래프

  • 더 자세한 정보를 담을 수 있다.

• 무(방)향 그래프 : 양쪽 다 왔다 갔다 할수 있게 만든 것 / 단반향 그래프하고 다르다.
  

• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.

• 인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
  

• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
  

• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다.
  

인접행렬

인접행렬은 언제 사용 하는가 ?

• 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이합니다.
  • 예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있습니다.
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용됩니다.

인접 행렬은 무엇인가 ?

• 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표입니다. (만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장합니다.)

• A의 진출차수는 1개 입니다: A —> C
  [0][2] === 1
• B의 진출차수는 2개 입니다: B —> A, B —> C
  [1][0] === 1
  [1][2] === 1
• C의 진출차수는 1개입니다: C —> A
  [2][0] === 1

인접리스트
인접 리스트는 언제 사용할까?

• 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용합니다.
  • 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지합니다.

인접 리스트는 무엇인가 ?

• 인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현합니다.

출처: 코드스테이츠