그래프) 1. 그래프의 세 가지 표현 방법

*그래프를 표현(구현)한다 == 모든 정점을 기록하고, 두 정점간의 관계(간선)을 기록하여 저장한다.

*V는 정점을 의미한다.

 

1. 인접 행렬 표현

-구현 방법

n개의 V에 대하여, n*n 이차원 배열에 두 정점간의 관계(간선)를 표현한다.

배열의 인덱스엔 두 정점이 들어가고, 배열의 내용엔 간선에 대한 정보가 들어간다. 

//1. 동적으로 인접 행렬을 구현할 때 (메모리 제약이 있을 때)
	//n은 정점의 개수
	int n;
	scanf("%d", &n);

	//a는 간선을 인접 행렬 방법으로 표현하기 위한 이차원 배열
	int** a;

	//정점의 이름대로 배열에 접근하기 위해서 n+1개의 공간을 할당 받는다.
	a = (int**)malloc(sizeof(int*) * (n + 1));
	for (int i = 0; i < n+1; i++) {
		a[i] = (int*)malloc(sizeof(int*) * (n + 1));
	}

//2. 그냥 ps용 인접 행렬을 구현할 때 (정점 개수의 제한이 주어졌을 때)
//ex> 모든 정점의 개수는 100개 이하 이다.
//정점대로 배열읕 사용하기 위해서 100+1 만큼의 배열을 선언한다.
	int aa[101][101];
    

 

ex> 배열 표현 방법

정점 1과 정점 2간의 관계가 궁금하다. (두 정점을 잇는 간선이 존재하는지 궁금하다.)

그래프를 인접 행렬로 표현한 이차원 배열 a에 대하여, a[1][2]가 참인지 확인한다.

//정점이 100개인 그래프의 간선을 표현하기 위한 이차원 배열 a
int a[101][101];

//임의로 간선을 정해줌
a[1][2] = 1;

//정점 1과 정점 2가 이어져 있는지 확인하는 코드
if(a[1][2]){ //0이 아닌 수는 참을 의미하므로, 
	println("정점 1과 정점 2 사이엔 간선이 존재 합니다."); }
   
    
 

 

ex> 배열의 내용에 들어가는 값

무방향 그래프) 참(true, 0이 아닌 수), 거짓(false, 0)

가중치 그래프) 가중치 값

 

 

-장점

두 정점에 대한 간선 존재 여부를 빠르게 찾을 수 있다.

*두 정점의 번호가 주어졌을 때, 두 정점을 잇는 간선이 존재하는지, 한 번의 연산으로 알 수 있다.

 

-단점

항상 (전체 정점의 개수)^2 만큼의 공간을 사용한다. 

*따라서 밀집 그래프에 유리하다.

*밀집 그래프 : (전체 정점의 개수)^2개에 가까운 간선을 가진 그래프

 

 

2. 인접 리스트 표현

-장점

항상 간선 수 만큼의 공간을 사용한다.

*따라서 희소 그래프에 유리하다. 

*밀집 그래프 : (전체 정점의 개수)^2보다 훨씬 적은 간선을 가진 그래프

 

-단점

두 정점에 대한 간선 존재 여부를 비교적 느리게 찾을 수 있다.

*두 정점의 번호가 주어졌을 때, 두 정점을 잇는 간선이 존재하는지, 해당하는 정점의 리스트를 탐색해야 알 수 있다.

 

 

3. 암시적 그래프 표현

-장점

(x,y)식으로 정점을 간단하게 표현할 수 있다.

 

-단점

그래프를 사용하는 알고리즘 사용 시, 코드 변환이 까다롭다.