[자료구조] 그래프(Graph)란? / 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)

그래프란?

그래프는 정점(vertex)와 간선(edge)의 집합으로 구성된다.

정점은 노드, 간선은 엣지를 말 하며 정점과 정점을 잇는 선을 간선이라고 한다.

그래프는 리스트와 행렬 구조 중의 하나로 구분 가능하지만 실제로는 두 구조의 조합된 형태를 나타낸다. 일반적으로 알고 있는 수학에서의 그래프와는 다른 모양이다.

그래프 종류로는 무방향 그래프, 방향 그래프, 완전 그래프, 부분 그래프, 가중 그래프, 유향 비순환 그래프, 연결 그래프, 단절 그래프 등이 있다.

 

그래프의 표현 방식

• 인접 행렬(Adjacency Matrix)
  
  그래프를 행렬로 표현하는 방식 → 정방 행렬을 사용하여 그래프의 정점 간의 연결 관계를 나타냄
  
  인접 행렬은 그래프의 정점(Vertex) 수를 n이라고 할 때, n x n 크기의 행렬을 생성한다. 행렬 내의 각 원소는 간선(Edge)의 존재 여부를 나타내며, 행렬의 행과 열은 각각 그래프의 정점을 나타낸다. 따라서, 인접 행렬의 (i,j) 위치에 있는 원소는 정점 i 와 정점 j 사이의 간선이 있는지 여부를 나타낸다. 간선이 존재하는 경우 1로 표시하고, 존재하지 않는 경우 0으로 표시한다.
  
  * 인접 행렬은 모든 가능한 경우의 수를 저장하기 때문에 메모리 차지가 인접 리스트에 비해 많다.
  
  아래의 그래프와 그래프를 인접 행렬로 표현한 것을 살펴보면 쉽게 이해할 수 있다.
• 화살표에 따라 숫자가 정해지는데 화살표가 가리키면 1 아니면 0을 넣어준다.

• 인접 리스트(Adjacency List)
  각 노드가 데이터와 다음 노드를 가리키는 포인터를 저장하는 리스트로 구성된다. 연결 리스트는 동적으로 메모리를 할당하여 사용하기 때문에 메모리를 효율적으로 사용할 수 있다.

 

✨ 인접 행렬과 인접 리스트의 차이?

인접 행렬	인접 리스트
2차원 배열을 사용하여 그래프의 연결 정보 저장	연결리스트로 그래프의 연결 정보 저장
정점의 개수를 행과 열로 가지는 행렬을 생성하여 정점 간의 연결 여부를 행렬의 원소로 표현(0과 1)	각 정점마다 연결된 정점들을 리스트로 나타내고 리스트를 배열로 관리
간선의 존재 여부를 실시간으로 확인 가능 * 상수시간 : 해당 연산을 수행하여 원하는 정보를 얻는 데에는 입력의 크기에 관계없이 일정한 시간	간선의 존재 여부를 확인 하기 위해서는 리스트를 순회해야 하므로 시간 복잡도가 높음
간선의 수가 정점의 수에 비해 많은 경우에는 메모리를 효율적으로 사용	간선의 수가 정점의 수에 비해 적은 경우에는 메모리를 효율적으로 사용
그래프의 구조가 동적으로 변경되는 경우에는 메모리의 재할당이 필요하므로 비효율적	그래프의 구조가 동적으로 변경되는 경우에도 메모리 관리가 용이

 

그래프 용어 정리

1. 정점(Vertex)
   그래프에서 하나의 개체를 나타내는 점이나 노드
   각 정점은 고유한 식별자를 가지며, 다른 정점들과 연결될 수 있음
   
   
2. 간선(Edge)
   두 개의 정점을 연결하는 선이나 링크
   간선은 정점과 정점 사이의 관계를 표현하며, 방향성이 있는 경우도 있음
   
   
3. 방향 그래프(Directed Graph)
   간선에 방향이 있는 그래프 즉, 간선은 출발 정점과 도착 정점을 가리키는 방향
   
   
4. 무방향 그래프(Undirected Graph)
   간선에 방향이 없는 그래프
   간선은 단순히 두 정점을 연결하는 것으로 방향성이 없다.
   
   
5. 가중치(Weight)
   그래프의 간선에 할당된 값 또는 비용 가중 그래프(Weighted Graph)는 간선에 가중치가 있는 그래프를 의미
   
   
6. 인접 정점(Adjacent Vertex)
   간선으로 직접 연결된 두 개의 정점 예를 들어, 간선 (u, v)가 존재하는 경우, 정점 u와 v는 서로 인접 정점
   
   
7. 차수(Degree)
   정점에 연결된 간선의 수를 의미
   무방향 그래프의 경우, 차수는 해당 정점에 인접한 정점들의 수
   방향 그래프의 경우, 차수는 해당 정점으로 들어오는 간선의 수와 해당 정점에서 나가는 간선의 수의 합
   
   
8. 경로(Path)
   그래프에서 정점들을 연결하는 간선들의 순서를 나타내는 순서쌍
   경로는 연속된 간선들로 이루어지며, 간선을 따라 이동하여 한 정점에서 다른 정점으로 이동하는 방법
   
   
9. 사이클(Cycle)
   경로의 시작 정점과 끝 정점이 동일한 경우를 의미
   즉, 사이클은 한 정점에서 시작하여 다시 해당 정점으로 돌아오는 경로
   
   
10. 연결 그래프(Connected Graph)
    그래프에서 임의의 두 정점 사이에 경로가 존재하는 경우
    즉, 모든 정점 쌍 간에 연결이 되어 있는 그래프
    
    
11. 연결 요소(Connected Component)
    무방향 그래프에서 연결된 정점들의 집합
    연결 요소는 각각의 정점들이 서로 연결되어 있지만 다른 연결 요소와는 연결되어 있지 않음
    
    
12. 강한 연결 요소(Strongly Connected Component)
    방향 그래프에서 모든 정점 쌍 간에 양방향으로 경로가 존재하는 정점들의 최대 집합
    강한 연결 요소는 서로에게 도달할 수 있는 정점들의 그룹
    
    
13. 사이클 검출(Cycle Detection)
    그래프에서 사이클의 존재 여부를 확인하는 알고리즘 또는 절차
    사이클 검출은 그래프 내에서 반복되는 경로를 찾아내는 중요한 작업
    
    
14. 최단 경로(Shortest Path)
    그래프에서 두 정점 사이의 가장 짧은 경로를 찾는 문제
    최단 경로 문제는 가중치가 있는 그래프에서 가장 작은 가중치의 경로를 찾는 것이 일반적
    
    
15. 트리(Tree)
    사이클이 없는 연결 그래프 트리는 하나의 루트(Root) 정점을 가지고 있으며, 각 정점은 부모-자식 관계로 연결되어 있다.
    
    
16. 이진 트리(Binary Tree)
    각 정점이 최대 두 개의 자식을 가질 수 있는 트리
    
    
17. 그래프 탐색(Graph Traversal)
    그래프 내의 모든 정점을 방문하는 작업을 의미합니다. 대표적인 그래프 탐색 알고리즘으로는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.
    ✅ 다음 게시글

 

🔽 트리, 이진트리 알아보기

[자료구조] 트리 구조 (Tree) / 이진 트리 (Binary Tree)

 

---

오늘이 진짜 역대급으로 정말 제일 제일 외계어같고 무슨 말인지도 모르겠는 그런 날의 연속이었다. 사실 오늘 배운 것은 트리순회와 BFS와 DFS였다. 그 이전에 개념들이 제대로 정리되지 않은 것 같아서 그래프를 다시 정리했다. 물론 아직 더 파고 파고 파야할 것들이 남아있다. 트리구조에서도...

다들 시간을 어떻게 쓰고 있을까? 너무 궁금하다. 늦게 자면 늦게 자는대로 그 다음 날이 너무 힘들고 시간은 매일 부족하다.ㅜㅜ 잠이 사라졌으면 좋겠다. 내일이면 또 새로운 페어를 시작하는데 너무 부담이다.

하.. ㅜㅜ 어떡해.. 나는 아직 오늘 한 것두 못했는데 너무 속상하당.