Heap

void insert_max_heap(element item, int *n) {
	/* insert item into a max heap of current size *n */
	int i;
	if(HEAP_FULL(*n)) {
		fprintf(stderr, "The heap is full.\\n");
		exit(1);
	}
	i = ++(*n);
	while((i != 1) && (item.key > heap[i/2].key)) {
		heap[i] = heap[i/2]; // 부모걸 가져옴
		i /= 2;
	}
	heap[i] = item; // 최종 위치에 삽입
}

element delete_max_heap(int *n) {
	/* delete element with the highest key from the heap */
	int parent, child;
	element item, temp;
	if(HEAP_EMPTY(*n)) {
		fprintf(stderr, "The heap is empty");
		exit(1);
	}
	/* save value of the element with the largest key */
	item = heap[1]; // 젤 크던 거 저장
	/* use the last element in the heap to adjust heap */
	temp = heap[(*n)--]; // 마지막 노드 저장
	parent = 1;
	child = 2; // parent child 설정해주고
	while(child <= *n) { // while문 돌려
		/* find the larger child of the current parent */
		if((child < *n) && (heap[child].key < heap[child+1].key)) child++;
		if(temp.key >= heap[child].key) break;
		/* move to the next lower level */
		heap[parent] = heap[child];
		parent = child;
		child *= 2;
	}
	heap[parent] = temp;
	return item;
}

disjoint set

int simpleUnion(int i, int j) {
	parent[i] = j;
}

int simpleFind(int i) {
	for( ; parent[i] >= 0; i = parent[i] )
		;
	return i;
}

void weightedUnion(int i, int j) {
	int temp = parent[i] + parent[j];
	if(parent[i] > parent[j]) {
		parent[i] = j; /* make j the new root */
		parent[j] = temp;
	}
	else {
		parent[j] = i; /* make i the new root */
		parent[i] = temp;
	}
}

int collapsingFind(int i) {
	int root, trail, lead;
	/* find root */
	for(root = i; parent[root] >= 0; root = parent[root])
	;
	/* 나 포함 조상들의 parent를 root로 수정 */
	for(trail = i; trail != root; trail = lead) {
		lead = parent[trail];
		parent[trail] = root;
	}
	return root;
}

void main() {

    int i, j, n, found;
    printf("Enter number of items (<= %d) ", MAX_SIZE);
    scanf("%d", &n);

    for(i=0; i<n; i++) parent[i] = -1;

    printf("Enter a pair of equivalent items (-1 -1 to quit): ");
    scanf("%d%d", &i, &j);
    
    weightedUnion(i, j);

    while(i >= 0) {
        printf("Enter a pair of equivalent items (-1 -1 to quit): ");
        scanf("%d%d", &i, &j);

        weightedUnion(simpleFind(i), simpleFind(j));
    }

    for(i=0; i<n; i++) {
        found = 0;
        for(j=0; j<n; j++) {
            if(simpleFind(j) == i) {
                printf("%d ", j);
                found = 1;
            }
        }
        if(found > 0) printf("\\n");
    }
}

Connected Components

/* count the connected components of a graph */
void connected(void) {
	int i, count = 0;
	for(i = 0; i < n; i++)
		if(!visited[i]) {
			count = count + 1; /* the next connected component */
			countAndLabel(i, count);
		}
}

/* count and label connected components using DFS */
void countAndLabel(int v, int count) {
	nodePointer w;
	push(v);
	while(top) { /* stack is not empty */
		v = pop();
		if(!visited[v]) {
			visited[v] = TRUE;
			comp[v] = count; /* set the component number of v */
			for(w = graph[v]; w; w = w->link)
				push(w->vertex);
		}
	}
}

biconnected components

#define MIN2(x, y) ((x) < (y) ? (x) : (y))

void dfnlow(int u, int v) { /* v는 u의 parent node */
    nodePointer ptr;
    int w;
    dfn[u] = low[u] = num++; ⭐
    for(ptr = graph[u]; ptr; ptr = ptr->link) {
        w = ptr->vertex;
        if(dfn[w] < 0) { /* 아직 안 간 노드 */
            dfnlow(w, u);
            low[u] = MIN2(low[u], low[w]); ⭐
        }
        else if(w != v) { /* w is a back node */
            low[u] = MIN2(low[u], dfn[w]); ⭐
        }
    }
}

int checkAp(int u) {
   
    if(dfn[u] == 0) {
        /* if u is root, then check whether it has more than one child nodes. */
        int nChild = 0;
        nodePointer ptr = graph[u];
        while(ptr) {
            if(parent[ptr->vertex] == u) nChild++;
            ptr = ptr->link;    
        }
        if(nChild > 1) return TRUE;
        else return FALSE;
    }
    else {
        /* if u is non-root, then check whether it has a chlid w, where low[w] >= dfn[u]. */
        nodePointer ptr = graph[u];
        while(ptr) {
            if(dfn[ptr->vertex] > dfn[u]) {
                if(parent[ptr->vertex] == u)
                    /* ptr->vertex is a child of u */
                    if(low[ptr->vertex] >= dfn[u]) return TRUE;
            }
            ptr = ptr->link;
        }
        return FALSE;
    }
}

Dijkstra

void shortestPath(int v, int cost[][MAX_VERTICES], int distance[], int n, short int found[]) {
	/* distance[i] represents the shortest path from v to i, cost is the adjacency
	matrix */
	int i, u, w;
	for(i = 0; i < n; i++) {
		found[i] = FALSE;
		distance[i] = cost[v][i];
	}
	found[v] = TRUE;
	distance[v] = 0;
	for(i = 0; i < n-2; i++) { /* 시작 정점, 마지막에 자동으로 확정되는 정점 제외 */
		u = choose(distance, n, found);
		found[u] = TRUE;
		for(w = 0; w < n; w++) /* relaxing (u,w) */
			if(!found[w])
				if(distance[u] + cost[u][w] < distance[w])
					distance[w] = distance[u] + cost[u][w];
	}
}

int choose(int distance[], int n, short int found[]) {
	/* find the smallest distance not yet checked */
	int i, min, minpos;
	min = INT_MAX;
	minpos = -1;
	for(i = 0; i < n; i++)
		if(distance[i] < min && !found[i]) {
			min = distance[i];
			minpos = i;
		}
	return minpos;
}

시간복잡도

Equivalence class

Initialization O(n)

Input O(m)