알고리즘 복습) 그래프 기초

그래프

우리가 흔히 그래프라고 알고 있는 것은 시각화된 차트나 다이어그램일 것이지만, 알고리즘에서의 그래프는 사물 혹은 추상적인 개념간의 연결관계를 표현한 것이다.

일반적인 그래프

알고리즘의 그래프

이러한 그래프는 정점(Vertex)와 간선(Edge)들로 이루어져있다.

 

• 정점(Vertex):데이터를 표현(사물,개념)

 

• 간선(Edge):정점들(Vertex)을 연결하는데 사용 

 

사용할 그래프

이번 포스팅에서 사용할 그래프는 가중치 그래프와 방향그래프 두가지이다.

 

가중치 그래프

가중치 그래프는 연결관계를 나타낼뿐 아니라 이들의 관계에서 숫자를 기입하여 중요도등을 나타낼수 있는 그래프이다.

ex)지하철 노선도

가중치 그래프

방향 그래프

방향 그래프는 양방향으로 연결된것이 아닌 특정 방향으로 연결관계를 나타내는 것을 의미한다.

ex)일방통행이 포함된 도로망, 상호작용 표현

방향 그래프

 

 

그래프 구현

 

방향그래프

 

방향 그래프

 

//
void CreateGraph_1()
{
 struct Vertex
 {
 };
 
 vector<vector<int>>adjacent(6);
 
 adjacent[0]={1,3};
 adjacent[1]={0,2,3};
 adjacent[2]={};
 adjacent[3]={4};
 adjacent[4]={};
 adjacent[5]={4};
 
}



//메모리 소모는 심하지만 빠른 접근을 할때 유리
void CreateGraph_2()
{
 struct Vertex
 {
 };
 
 vector<vector<bool>>adjacent(6,vector<bool>(6,false));
 
 adjacent[0][1]=true;
 adjacent[0][3]=true;
 adjacent[1][0]=true;
 adjacent[1][2]=true;
 adjacent[1][3]=true;
 adjacent[3][4]=true;
 adjacent[5][4]=true;
 
 }

 

가중치&방향그래프

 

가중치 그래프

void CreateGraph_2()
{
 struct Vertex
 {
 };
 
 vector<vector<bool>>adjacent(6,vector<bool>(6,false));
 
 adjacent[0][1]=true;
 adjacent[0][3]=true;
 adjacent[1][0]=true;
 adjacent[1][2]=true;
 adjacent[1][3]=true;
 adjacent[3][4]=true;
 adjacent[5][4]=true;
 
 vector<vector<int>>adjacent2=
 {
  vector<int>{-1,15,-1,35,-1,-1}
  vector<int>{15,-1,5,10,-1,-1}
  vector<int>{-1,-1,-1,-1,-1,-1}
  vector<int>{-1,-1,-1,-1,5,-1}
  vector<int>{-1,-1,-1,-1,-1,-1}
  vector<int>{-1,-1,-1,-1,5,-1}
 };
 
 }