[자료구조] 그래프 란(Swift)

그래프의 개념

그래프(Graph)는 연결이 되어있는 원소(Node)간의 관계를 표현한 자료구조입니다.

앞선 트리와의 가장 큰 차이점은 사이클이 존재가능하다는 점이고 그래프를 연결할 객체를 나타내는 Node(Vertex)와 그 Node를 연결하는 간선(Edge)의 집합으로 구성됩니다.

그래프는 방향이 존재하는 방향 그래프 , 방향이 없는 무방향 그래프 , 간선에 비용이나 가중치가 들어간 가중치 그래프 등으로 구성되어있습니다.

그래프 구현

 

1.인접행렬 구현

 

map[i][j] = 1 -> i 에서 j로 가는 간선이 존재한다는 뜻입니다.

map[i][j] = 0 -> i 에서 j로 가는 간선이 없다는 뜻입니다.

 

ex)

map[1][2] = 1

map[2][1] = 1

map[1][3] = 1

map[3][1] = 1

...

map[2][4] = 1

map[4][2] = 1

 

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map({Int(String($0))!})
    matrix[input[0]][input[1]] = 1
    matrix[input[1]][input[0]] = 1
}

 

 

2.인접 리스트 구현

 

1 -> [2,3] // 1이 2와 3과 연결되어 있다는 의미 , 방향그래프도 동일하게 작성합니다

2 -> [1,3,4]

3 -> [1,2,4]

4 -> [2,3]

 

1,2,3,4 부분을 index로 잡고 이차원 배열로 처리가능 합니다 

또는 딕셔너리 사용해서 처리가능합니다

 

 

인접행렬의 장점은 메모리를 좀더 사용하는 대신 두 정점이 연결되어있는지 확인하는 속도가 빠릅니다

인접리스트의 장점은 메모리를 덜쓰는 구조입니다. 하지만 두 정점의 연결여부를 확인하는데 좀 더 시간이 걸립니다.

 

 

 

그래프 관련 문제

https://school.programmers.co.kr/learn/courses/30/lessons/258711 

https://www.acmicpc.net/problem/1260

https://www.acmicpc.net/problem/2178

 

 

 

 

 

왜 사용해야할까 or 나만의 고민

여러 노드들의 관계를 표현하는데 효과적인 자료구조(비선형 자료구조)입니다.

-> 복잡한 관계를 직관적으로 확인할수있는데 도움이 됩니다.