[자료구조] 그래프 (Graph)

DevHwan·2022년 1월 18일

📌 그래프(Graph)란?

그래프란 정점들의 집합과 그 정점들을 연결하는 간선들의 집합을 가지는 자료구조이다. 그래프는 정점 사이의 관계를 표현할 수 있는 적합한 자료구조이다.
트리는 그래프의 한 종류이며, DAG(directed, Acyclic, Graph) 방향성이 존재하고, cycle이 없는, 비순환 그래프를 의미한다.

📌 용어 정리

vertex: 정점, 객체 또는 위치 (node라고 불리기도 한다)
edge : 간선, 정점들간의 연결 관계를 나타내는 선 (link라고 불리기도 한다)
adjacent vertex : 인접 정점, 간선을 통해 연결된 정점
incident edge : 부속 간선, 두 정점을 연결하느 간선
degree : 차수, 해당 정점에 연결되어 있는 간선의 수
sparse graph / dense graph : 간선이 정점보다 적은 그래프, 간선이 정점보다 많은 그래프
cycle : 경로의 시작점과 도착점이 같은 경우
용어 추가 예정

📌 그래프의 특징

그래프에서는 정점이 부모와 자식 관계를 갖지 않는다.
순회하는 방법으로는 DFS와 BFS가 존재한다.
그래프는 순환할 수 있고, 순환하지 않을 수 있다. ( cyclic or acyclic )
특징 추가 예정

📌 그래프의 종류

무방향 그래프와 방향그래프

무방향 그래프 ( Undirected graph )
- 무방향 그래프의 간선은 방향성이 존재하지 않는다.
- 무방향 그래프에서는 간선을 통해서 양방향으로 이동이 가능하다.
- 정점 A와 정점 B를 연결하는 간선은 (A,B)와 같이 표현한다.
방향 그래프 ( Directed graph )
- 방향 그래프의 간선은 방향성이 존재한다.
- A에서 B로 이동할 수 있는 간선은 <A,B>와 같이 표현한다.

가중치 그래프

가중치 그래프 ( Weighted graph )
- 간선에 비용이 할당되는 그래프

순환 그래프와 비 순환 그래프

순환 그래프 ( Cyclic )
- 경로의 시작점과 도착점이 일치하는 경우
비 순환 그래프 ( Acyclic )
- 싸이클이 없는 그래프

완전 그래프

완전 그래프 ( Completed graph )
- 그래프에 있는 모든 정점이 연결된 그래프

📌 그래프의 구현

그래프의 구현은 크게 두 가지 방법으로 나눌 수 있다. 행렬을 이용한 구현과 리스트를 이용한 구현이다.

인접행렬

행렬에서 행과 열은 정점을 나타내고, 행렬값이 연결상태를 나타낸다. 0은 연결되어 있지 않음을의미하고, 1은 연결되어 있는 상태를 의미한다. 가중치 그래프라면 가중치가 입력된다. 무방향 그래프의 경우 행렬이 대칭으로 나타난다.

#include<iostream>
using namespace std;
const int SIZE = 1024;
int graph[SIZE][SIZE];

int main()
{
	int start, end;
	//int weight 가중치 그래프의 경우

	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			cin >> start >> end;
			//cin >> weight;
			graph[start][end] = 1;
			graph[end][start] = 1;
			//graph[start][end] = weight;
		}
	}
}

인접리스트

보통 벡터를 리스트처럼 이용하여 그래프를 구현한다. 정점의 수 만큼 리스트를 생성하고 해당 리스트에 연결된 정점을 추가하는 방식으로 구현한다.

#include<iostream>
#include<vector>
using namespace std;
const int SIZE = 1024;
vector<int> graph[SIZE];

int main()
{
	int start, end;

	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			cin >> start >> end;
			graph[start].push_back(end);
			graph[end].push_back(start);
			//가중치 그래프의 경우 vector<pair<int,int>> grpah[SIZE] 혹은 구조체를 이용한다.
		}
	}
}