[자료구조] 인접 행렬, 인접 리스트 시간 복잡도 코드 구현

 

 

그래프를 인접 행렬과 인접 리스트로 표현했을 때

진입/진출 차수 계산, 엣지수를 계산할 때 각각의 시간 복잡도를 C언어 코드로 구현하였다.

 

 

int matrixCalculateOutDegree(GraphType* g, int v) {
	int i, degree = 0;
	for (i = 0; i<g->n; i++) {
		if (g->adj_mat[v][i] != 0)
			degree++;
	}
	return degree;
	// 시간 복잡도는 O(n)
}

int matrixCalculateInDegree(GraphType* g, int v) {
	int i, degree = 0;
	for (i = 0; i < g->n; i++) {
		if (g->adj_mat[i][v] != 0)
			degree++;
	}
	return degree;
	// 시간 복잡도는 O(n);
}

int matrixCalculateEdges(GraphType* g, int v) {
	int i, j, e = 0;
	for (i = 0; i < g->n; i++)
		for (j = 0; j < g->n; j++)
			if (g->adj_mat[i][j] != 0)
				e++;
	return e;
    // 시간 복잡도는 O(n^2)
}

int listCalculateOutDegree(GraphType* g, int v) {
	int degree;
	GraphNode* node = g->adj_list[v];
	while (node != NULL) {
		degree++;
		node = node->link;
	}
	return degree;
	// 정점 v에서의 e개의 엣지들을 순회하며 개수를 세면 되므로
	// 시간 복잡도는 O(e)
}

int listCalculateInDegree(GraphType* g, int v) {
	int degree;
	GraphNode* node;
	for (int i = 0; i < g->n; i++) {
		node = g->adj_list[i];
		while (node != NULL) {
			if (node->vertex == v)
				degree++;
			node = node->link;
		}
	}
	return degree++;
	// n개의 노드들을 다 탐색해서 v로 진입하는 엣지들을 찾아야하므로
	// 시간 복잡도는 O(n+e)
}

int calculateEdges(GraphType* g, int v) {
	int e = 0;
	GraphNode* node;
	for (int i = 0; i < g->n; i++) {
		node = g->adj_list[i];
		while (node != NULL)
		{
			e++;
			node = node->link;
		}
	}
	return e;
	// n개의 노드와 e개의 간선을 모두 탐색해야하므로
	// 시간 복잡도는 O(n+e)
}