그래프

정의

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조

---

특징

• 정점 집합과 간선 집합으로 표현 가능
• 정점은 Node, 간선은 Edge 라고도 함
  
• 정점은 여러 개의 간선을 가질 수 있음
  <-> 선형 구조는 앞 뒤로 하나의 요소만 가질 수 있음
• 방향 그래프와 무방향 그래프로 나눌 수 있음
• 간선은 가중치를 가질 수 있음
• 사이클이 발생할 수 있음
  탐색 시 무한 루프에 빠지지 않도록 하는 것에 주의
• 인물 관계도로 비유 가능하며 지하철 노선도, 페이지랭크 등에 사용

---

간선 방향성에 따른 분류

무방향 그래프

• 간선으로 이어진 정점끼리 양방향으로 이동 가능
• (A, B) 와 (B, A) 는 같은 간선으로 취급 ex) 양방향 통행 도로

방향 그래프

• 간선에 방향성이 존재하는 그래프
• <A, B> 와 <B, A> 간선을 통해 양방향으로 갈 수 있더라도
  두 간선은 다른 간선으로 취급됨 ex) 일방 통행

---

전체 그래프의 연결 상태에 따른 분류

연결 그래프

• 모든 정점이 서로 이동 가능한 상태의 그래프

비연결 그래프

• 특정 정점쌍 사이에 간선이 존재하지 않는 그래프
• ec) 친한 친구 설문 그래프... 🥲

완전 그래프

• 모든 정점끼리 연결된 상태의 그래프
• 한 정점의 간선 수는 (전체 정점 수 - 1)
• (전체 정점 수 - 1) X (전체 정점 수) = 전체 간선 

---

사이클

그래프의 정점과 간선의 부분 집합에서 순환이 발생하는 부분

---

그래프 구현 방법

• 인접 행렬 => 2차원 배열
• 인접 리스트 => 연결 리스트

---

Javascript 로 인접 행렬 표현

const graph = Array.from(new Array(5), () => Array(5).fill(false));

graph[0][1] = true;
graph[0][3] = true;
graph[1][2] = true;
graph[2][0] = true;
graph[2][4] = true;
graph[3][2] = true;
graph[4][0] = true;

• 간선에 가중치가 필요하다면 true/false 가 아닌 null/임의 가중치 를 넣으면 됨
• 무방향 그래프의 경우 모든 값을 대칭으로 넣어주면 됨

---

Javascript 로 인접 리스트 표현

const graph = Array.from(new Array(5), () => []);

graph[0].push(1);
graph[0].push(3);
graph[1].push(2);
graph[2].push(0);
graph[2].push(4);
graph[3].push(2);
graph[4].push(0);

 

• 정점 수 만큼 배열을 만든 후 연결할 정점을 배열에 추가하면 됨