[자료구조] 그래프

그래프

• 그래프는 정점(vertex)와 간선(edge)로 이루어진 한정된 자료구조를 의미한다.
• 그래프는 인접 리스트와 인접 행렬로 구현할 수 있다.
• 방향 그래프 : 방향성이 있어 간선이 한방향으로만 이루어져 있다.
• 무방향 그래프 : 방향성이 없어 간선을 통해 양방향으로 이동할 수 있다.
• 가중치 그래프 : 간선에 가중치를 두어 간선의 비용을 나타낸다.

구현방식

• 그래프는 인접 행렬과 인접 리스트 두가지 방식으로 구현한다.
• 인접 리스트 방식은 공간 효율성은 좋지만 특정 간선 접근이 비효율적이다.
• 인접 행렬 방식은 공간 효율성은 좋지 않지만 특정 간선 접근이 효율적이다.

코드

위의 그래프를 인접 행렬 방식으로 구현

void CreateGraph()
{
	vector<vector<int>> adjacent 
    		= vector<vector<int>>(6, vector<int>(6, -1));

	adjacent[0][2] = 10;
	adjacent[0][4] = 20;
	adjacent[0][5] = 5;
	adjacent[1][5] = 10;
	adjacent[2][3] = 25;
	adjacent[2][4] = 5;
	adjacent[4][5] = 10;
    
	// -1 -1 10 -1 20 5
    	// -1 -1 -1 -1 -1 10
        // 10 -1 -1 25  5 -1
        // -1 -1 25 -1 -1 -1 
        // 20 -1  5 -1 -1 10
        //  5 10 -1 -1 10 -1
}