강한 결합 요소(Strongly Connected Components)

강한 결합 요소

: 그래프 안에서 강하게 결합된 정점 집합

 

cf> scc 활용

: scc마다 묶으면 cyclic 존재하지 않는 방향 그래프이기에 위상정렬 수행 가능하다

---

1. 알고리즘

• 코사라주 알고리즘(Kosaraju's Algorithm)
• 타잔 알고리즘(Tarjan's Algorithm)

(1) 타잔 알고리즘

: 모든 정점에 대해 DFS(Depth-First Search, 깊이 우선탐색)을 수행하여 scc 찾는 알고리즘

: 부모로 돌아올 수 있어야 scc 성립

: 각 정점마다의 부모 노드가 무엇인지 기록(초기값은 자기자신) => union-find algorithm 개념과 비슷

 

(2) 작동 방식 

1) 정점번호가 낮은 순으로 DFS 탐색 (이때, 연결리스트 통해 오름차순으로 정렬하였음)

2) 현재 정점의 부모 노드 설정(초깃값 : 자기자신)하고 stack에 push

3) 현재 정점으로부터 도달가능한 정점으로 DFS 수행 (연결되어있고, finished==false인 정점)

=> finished : DFS 수행하다가 stack에서 pop하면서 true로 변경 , visited : DFS 수행 시작 여부

4) 재귀함수 통해 부모 값을 계속해서 반환하며 update한다. 그러다가 최종적으로 p[x] == x인 정점이 나오게 되면 pop한 데이터가 x가 될 때까지 stack에서 pop

(이때, finished 배열 true로 변경)

5) 따로 scc 그룹 저장할 배열 만들어놓고 pop한 데이터들(하나의 scc그룹) 저장

6) DFS 완전히 끝날때까지 과정 반복

 

 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <memory.h>
#define Min(a,b) ((a)>(b)?(b):(a))
#define VERTEX_SIZE 101



typedef struct _NODE_ {
	int data;
	struct _NODE_* link;
}NODE;

typedef struct _GRAPH_TYPE_ {
	NODE* head[VERTEX_SIZE];
	int n; // 정점의 갯수
}GRAPH_TYPE;

typedef struct _STACK_ {
	int top;
	int stack[VERTEX_SIZE];
}STACK;

void init(STACK* st) {
	st->top = -1;
	memset(st->stack, 0, VERTEX_SIZE * sizeof(int));
}

int IsEmpty(STACK* st) {
	return st->top == -1;
}

int IsFull(STACK* st) {
	return st->top == VERTEX_SIZE;
}
void push(STACK* st, int item) {
	if (IsFull(st)) {
		printf("더이상 스택에 push 할 수 없습니다\n");
		return;
	}
	else {
		st->top++;
		st->stack[st->top] = item;
	}
}

int pop(STACK* st) {
	if (IsEmpty(st)) {
		printf("pop할 데이터가 존재하지 않습니다\n");
		return;
	}
	else {
		int popdata = st->stack[st->top];
		st->top--;
		return popdata;
	}
}

void PrintStack(STACK* st) {
	printf("\n스택 출력: ");
	for (int i = 0; i <= st->top; i++) {
		printf("%d ", st->stack[i]);
	}
	printf("\n");
}

int DFS(GRAPH_TYPE* graph, STACK *st,int vertex,bool * finished, int * parent, bool * visited) {
	visited[vertex] = true;
	parent[vertex] = vertex;
	push(st, vertex);
	PrintStack(st);
	static int cnt = 1;
	printf("\n%d탐색시작",vertex);

	NODE* curNode = graph->head[vertex];
	while (curNode != NULL) {
		if (visited[curNode->data] != true) {
			int new =DFS(graph, st, curNode->data, finished, parent, visited);
			if (parent[vertex] > new) {
				parent[vertex] = new;
			}
		}
		else {
			if (finished[curNode->data] != true) {
				parent[vertex] = parent[curNode->data];
			}
		}
		curNode = curNode->link;
	}

	printf("\n부모값 출력: ");
	for (int i = 1; i <= graph->n; i++) {
		printf("%d ", parent[i]);
	}
	printf("\n");

	if (parent[vertex] == vertex) {
		printf("\n%d번째 scc : {", cnt++);
		while (!IsEmpty(st)) {
			int popdata = pop(st);
			finished[popdata] = true;
			printf("%d ", popdata);
			if (popdata == vertex) {
				break;
			}
		}
		printf("}\n");
	}
	return parent[vertex];
}

void SCC(GRAPH_TYPE * graph,STACK *st) {
	bool* finished = (bool*)calloc((graph->n) + 1, sizeof(bool));
	assert(finished != NULL);
	int* parent = (int*)calloc((graph->n) + 1, sizeof(int));
	assert(parent != NULL);
	bool* visited = (bool*)calloc((graph->n) + 1, sizeof(bool));
	assert(visited != NULL);

	for (int i = 1; i <= graph->n; i++) {
		if (finished[i] != true) {
			DFS(graph, st, i, finished, parent, visited);
		}
	}
}



GRAPH_TYPE* makeGraph() {
	GRAPH_TYPE* graph = (GRAPH_TYPE*)calloc(1, sizeof(GRAPH_TYPE));
	assert(graph != NULL);
	return graph;
}

void InsertVertex(GRAPH_TYPE* g, int vertex) {
	if (g->n >= VERTEX_SIZE-1) {
		printf("더이상 정점을 삽입할 수 없습니다\n");
		return;
	}
	else {
		g->n++;
	}
}

void InsertEdge(GRAPH_TYPE* g, int u, int v) {
	if (u > g->n || v > g->n || u==v) {
		return;
	}
	else {
		NODE* newNode = NULL;
		newNode = (NODE*)calloc(1, sizeof(NODE));
		assert(newNode != NULL);
		newNode->data = v;
		newNode->link = NULL;
		if (g->head[u] == NULL) {
			g->head[u] = newNode;
		}
		else {
			NODE* curNode = g->head[u];
			NODE* preNode = curNode;
			while (curNode != NULL) {
				preNode = curNode;
				if (curNode->data > newNode->data) {
					break;
				}
				curNode = curNode->link;
			}
			newNode->link = preNode->link;
			preNode->link = newNode;
		}
	}
}

void PrintGraph(GRAPH_TYPE* g) {
	NODE* curNode = NULL;
	for (int i = 1; i <= g->n; i++) {
		curNode = g->head[i];
		printf("\n[Head: %d] ", i);
		while (curNode != NULL) {
			printf("-> %d ", curNode->data);
			curNode = curNode->link;
		}
	}
}

int main() {
	GRAPH_TYPE* graph = makeGraph();
	STACK* st = (STACK*)calloc(1, sizeof(STACK));
	assert(st != NULL);
	init(st);
	for (int i = 1; i <= 11; i++) {
		InsertVertex(graph, i);
	}

	InsertEdge(graph, 1, 2);
	InsertEdge(graph, 2, 3);
	InsertEdge(graph, 3, 1);
	InsertEdge(graph, 4, 2);
	InsertEdge(graph, 4, 5);
	InsertEdge(graph, 5, 7);
	InsertEdge(graph, 6, 5);
	InsertEdge(graph, 7, 6);
	InsertEdge(graph, 8, 5);
	InsertEdge(graph, 8, 9);
	InsertEdge(graph, 9, 10);
	InsertEdge(graph, 10, 11);
	InsertEdge(graph, 11, 3);
	InsertEdge(graph, 11, 8);


	/*InsertEdge(graph, 1, 5);
	InsertEdge(graph, 2, 3);
	InsertEdge(graph, 3, 2);
	InsertEdge(graph, 3, 1);
	InsertEdge(graph, 4, 3);
	InsertEdge(graph, 5, 4);
	InsertEdge(graph, 5, 6);
	InsertEdge(graph, 6, 7);
	InsertEdge(graph, 7, 6);
	InsertEdge(graph, 8, 10);
	InsertEdge(graph, 9, 7);
	InsertEdge(graph, 9, 8);
	InsertEdge(graph, 10, 9);*/

	PrintGraph(graph);
	SCC(graph,st);



	getchar();
	return 0;
}