[자료구조] Graph(그래프) - 진출/진입 차수 계산

크기가 n x n인 방향 그래프 a가 존재한다. 이때의 진출 차수와 진입 차수를 구하려고 한다.

 

정점에서 나가는 노드의 차수를 진출차수(out-degree), 정점으로 들어오는 노드의 차수를 진입차수(in-degree)라 한다.

 

 

방향 그래프 a가 인접 행렬과 인접 리스트 각각으로 구현되었을 때의 진출/진입 차수를 계산하고자 한다.

 

1. 인접 행렬

 

1) 진출 차수(out-degree)

-> 인접 행렬로 구현된 경우 정점 v에 해당하는 행에서 n까지 탐색하면 된다.

 

int Count_OutDegree(GraphType *g, int v) {
	int cnt = 0;
   	for (int i = 0; i<g->n; i++) {
    		cnt += adj_list[v][i];
    	}
    	return cnt;
}

n만큼만 반복하면 되므로 시간복잡도는 O(n)이다.

 

 

2) 진입 차수(in-degree)

-> 정점 v에 해당하는 열에서 n까지 탐색

 

int Count_InDegree(GraphType *g, int v) {
	int cnt = 0;
    	for (int i = 0; i<g->n; i++) {
    		cnt += adj_list[i][v];
    	}
    	return cnt;
}

진출 차수와 마찬가지로 시간 복잡도는 O(n)이다.

 

 

2. 인접 리스트

 

 

1) 진출 차수(Out-degree)

-> adj_list에서 정점 v에 해당하는 곳을 탐색

 

int Count_OutDegree2(GraphType *g, int v) {
	GraphNode *p = g->adj_list[v];
    	int cnt = 0;
    	while (p != NULL) {
        	cnt++;
            	p = p->link;
        }
     	return cnt;
}

간선의 수만큼 반복하므로 시간 복잡도는 O(e)이다.

 

 

2) 진입 차수(In-degree)

 

int Count_InDegree2(GraphType *g, int v) {
	int cnt = 0;
    	GraphNode *p;
    	for (int i = 0; i<g->n; i++) {
        	p = adj_list[i];
            	while (p != NULL) {
                	if (p->vertex == v)
                    		cnt++;
                    	p = p->link;
                }
         }
     return cnt;
}

시간 복잡도는 O(n+e)이다.