처음 인접리스트와 인접행렬을 공부하면서 참고한 사이트가 있습니다. 제 블로그에서는 해당 블로그글을 요약하는 형태로 작성해보았습니다!
https://sskl660.tistory.com/60
그래프를 표현하는 경우는 크게 두 가지 방법이 있습니다.(인접행렬과 인접리스트입니다.)
(1) 인접행렬
인접행렬은 프로그래밍 상에서 2차원 배열로 나타낼 수 있습니다. 2차원 배열이 두 방향을 나타낼 수 있다는 점을 활용하기 때문입니다. 기본적으로 각 인덱스를 정점이라고 생각하고 정점이 교차하는 지점을 연결한 상태로 표시해주면 됩니다.
인접행렬은 무향 그래프와 유향 그래프로 나뉠 수 있습니다.
(1) 무향 그래프
무향 그래프는 방향을 가지지 않는 그래프로, 행렬이 매우 대칭적이라는 특징이 있습니다.
(2) 유향 그래프
방향을 가진 그래프로, 무조건 행렬이 대칭적으로 같은 값을 가지지 않습니다.(2) 인접 리스트
연결리스트 자료구조를 활용해 그래프를 표현합니다. 1차원 배열을 설정해 각 배열의 인덱스를 기준으로 연결리스트를 생성합니다. 따라서 그래프의 노드정보가 추가될 때마다 해당 노드의 연결리스트에 값이 추가하기만 하면 됩니다.
(1) 무향 그래프
제시되는 노드 정보들을 모두 정보를 추가해주면 됩니다.
0번 노드의 경우에는 노드에 포함하지 않기 때문에 비워두고, 위의 그림처럼 해당하는 노드들을 서로 넣어줍니다.
(2) 유향 그래프
유향 그래프는 어떤 노드1가 다른 노드2를 가리킬 때, 노드1의 배열 인덱스의 연결리스트에 노드2의 정보를 추가해주면 됩니다.**장단점에 대하여 작성
인접 행렬
메모리를 많이 사용합니다.(O(V^2)만큼)
전체 탐색에 걸리는 시간은 O(V^2)이며 두 노드의 연결성을 확인하는데 걸리는 시간은 O(1)만큼 걸립니다.
인접 리스트
메모리를 적게 사용합니다.(O(V+E)만큼)
전체 탐색에 걸리는 시간은 O(V+E)이며 두 노드의 연결성을 확인하는데 걸리는 시간은 O(V)만큼 걸립니다.
-> 인접리스트는 노드의 추가와 삭제가 빈번하게 발생하는 경우에 사용하면 좋습니다.
