[Swift 알고리즘] 그래프의 표현

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

1. 에지 리스트(edge list)

• 에지를 중심으로 그래프를 표현
• 특정 노드와 관련되어 있는 에지를 탐색하기 쉽지 않기 때문에 노드 중심 알고리즘에서 잘 사용하지 않고
  • 벨만 포드나 크루스칼 알고리즘에서 사용

[에지 리스트로 가중치 없는 그래프 표현하기]

• 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현
  • 배열의 행은 2개면 충분
• 노드는 여러 자료형을 사용할 수 있다.

[에지 리스트로 가중치 있는 그래프 표현하기]

• 가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다.

 

2. 인접 행렬(adjacency matrix)

• 2차원 배열을 자료구조로 이용하여 그래프를 표현
• 노드 중심으로 그래프를 표현

• 인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단해야 한다.
  • 자바) 노드가 3만 개가 넘으면 자바 힙 스페이스 에러가 발생

[인접 행렬로 가중치 없는 그래프 표현하기]

• 1을 저장하는 이유는 가중치가 없기 때문에, 1에서 2로 향하는 에지가 있다는 표시를 노드 중심으로

[인접 행렬로 가중치 있는 그래프 표현하기]

• 1에서 2로 향하는 에지의 가중치를 1행 2열에 기록

 

3. 인접 리스트(adjacency list)

• 인접 리스트는 ArrayList로 그래프를 표현한다.
• 노드 개수만큼 ArrayList를 선언한다.

[인접 리스트로 가중치 없는 그래프 표현하기]

• N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현

[인접 리스트로 가중치 있는 그래프 표현하기]

• ArrayList[1]에 [(2, 3), (5, 13)]이 연결되어 있다.
  • 노드 1과 2가 가중치 3 에지로,
  • 노드 1과 5가 가중치 13 에지로 연결되어 있다는 의미
  • 방향성도 고려되어 있다.

 

 

 

 

 

 

참고하였습니다. 감사합니다.

http://www.yes24.com/Product/Goods/108571508

Do it! 알고리즘 코딩 테스트 자바 편 - YES24