[1028알고리즘 14]그래프

그래프

연결되어 있는 정점과 정점간의 관계를 표현할수 있는 자료구조.

선형구조는 자료저장,  꺼내는것, 비선현구조는 표현에 초점.

그래프는 연결관계에 초점.

그래프는 유방향(Directed Grape)과  무방향(undirected Grape) 그래프 두가지가 있음.

 

 

1) 인접행렬(Adjacency Matrix)

2차원 배열로 그래프의 연결 관계를 표현

0 1 2 3

0xOxx

1OxOx

2xOxO

3xxOx

graph = [

[false, true , false, false]

[true, false, true, false]

[false, true, false, true]

[false, false, true, false]

]

 

 

2) 인접리스트(Adjacency List)

링크드 리스트로 그래프의 연결관계를 표현

0->1

1->0->2

2->1>3

3->2

graph = {

0: [1],

1:[0,2],

2:[1,3],

3:[2]

}

시간 vs 공간

인접행렬은 즉각적으로 0과 1일 연결되었는지 바로 알수있음.

O(노드^2) 공간사용

인접리스트 즉각적으로연결되었는지 알수없고 리스트를 검토.

O(간선) 시간 사용.

O(간선 +노드 ) 공간사용