🔍 그래프와 그래프 알고리즘 정리

🔍 그래프란?

그래프는 노드(Node)와 엣지(Edge)로 구성된 데이터 구조이다.

• 노드 : 데이터를 표현하는 단위 (정점)
• 엣지 : 노드 간의 연결을 나타내는 선

그래프는 데이터를 연결하여 표현하기 적합하다.

 

---

📖 그래프 알고리즘

• 유니온 파인드
  • 주요 목적 : 서로 다른 두 집합을 병합하거나, 두 노드가 같은 집합에 속해 있는지 판별
  • 응용
    • 그래프의 사이클 유무 판단
    • 최소 신장 트리(MST) 구현

---

• 위상 정렬
  • 조건 : 사이클이 없는 방향 그래프(DAG)
  • 정의
    • 그래프의 노드를 순서대로 정렬하는 알고리즘
    • 정렬 결과는 유일하지 않을 수 있음
  • 예시
    • 수강 괌고 신청 순서 : 선이수 과목(수1 ➡️ 수2)

---

[ 최단 거리 알고리즘  ]

: 그래프에서 특정 노드 간의 최단 경로를 찾는 알고리즘

• 다익스트라
  • 특징 : 시작점에서 다른 모든 노드로의 최단 거리 계산
  • 조건 : 음수 간선 불가
• 벨만-포드
  • 특징 : 시작점에서 다른 모든 노드로의 최단 거리 계산
  • 조건 : 음수 간선 허용, 음수 사이클도 판별 가능
• 플로이드-워셜
  
  • 특징 : 모든 노드에서 모든 노드까지의 최단 거리 계산
  • 조건 : 시작점이 없으며 모든 노드 쌍의 최단 거리 계산 가능
  • 단점 : 시간 복잡도가 높음 O(V³)

---

• 최소 신장 트리
  • 정의
    • 그래프의 모든 노드를 연결하는 최소 가중치의 트리
    • 간선의 가중치 합이 최소가 됨
  • 알고리즘
    • 크루스칼 알고리즘 : 유니온 파인드를 사용하여 구현
    • 프림 알고리즘 : 우선순위 큐를 사용하여 구현
  • 응용
    • 네트워크 구축 비용 최소화
    • 전력망, 도로 연결 등

---

 

🗂️

 

 

---

 

👩🏻‍💻 인접 리스트

 

[ 가중치 없는 그래프 표현하기 ]

ArrayList<Integer>[N]

 

⭐️ [ 가중치 있는 그래프 표현하기 ]

ArrayList<Node>[N]

* Node 클래스(int E, int V) 선언