[자료구조] 그래프

개념 및 용어

그래프 G는 하나 이상의 정점(혹은 노드)을 포함하는 집합 V와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E의 순서쌍으로 정의함 (G = (V, E))

• 간선(인접한다)
  • 두 정점을 연결하는 선
  • 두 정점 쌍으로 나타냄
• 무방향 그래프
  • 간선의 방향성이 없음
  • 정점 쌍이 순서를 나타낼 필요가 없으므로 {v1, v2}로 나타냄
  • n개의 정점을 갖을 때 최대 간선 개수: n(n-1)/2
  • 차수: 정점에 연결된 간선들의 개수
• 방향 그래프
  • 간선의 방향성이 있음
  • 순서쌍 (v1, v2)
  • n개의 정점을 갖을 때 최대 간선 개수: n(n-1)
  • 진입 차수: 주어진 정점으로 향한 간선의 개수
  • 진출 차수: 주어진 정점에서 시작하는 간선의 개수
  • 정점의 차수: 진출 차수와 진입 차수의 합
• 다중 그래프: 두 정점을 잇는 간선이 여러 개인 그래프
• 방향 다중 그래프: 방향성을 갖는 간선으로 이루어진 다중 그래프
• 무방향 다중 그래프: 방향성이 없는 간선으로 이루어진 다중 그래프
• 가중 그래프: 간선이 가중치를 갖는 그래프
• 완전 그래프: 모든 정점들이 간선으로 서로 연결된 그래프
• 독립 정점: 다른 어떤 정점과도 인접하지 않은 정점
• 널(null) 그래프: 독립 정점만으로 구성한 그래프( E가 공집합 )
• 경로: 임의의 두 정점을 연결하는 어떤 간선의 끝 정점(해당 간선의 머리)에서 그 간선의 시작 정점(해당 간선의 꼬리)으로 이러이즌 간선의 연속(열)
• 경로 길이: 경로에 있는 간선의 수
• 단순 경로: 경로 상에 있는 모든 정점이 서로 다른 경로
• 기본 경로: 경로 상에 있는 모든 간선이 서로 다른 경로
• 사이클: 출발점과 도착점이 동일한 단순 경로
• 사이클 그래프: 사이클이 있는 그래프
• 루프: 간선의 시작점과 끝점이 같은 정점인 길이가 1인 그래프
• 무사이클 그래프: 사이클이 없는 그래프 (혹은 트리)

추상 자료형

• 객체의 정의: 정점과 간선의 유한 집합
• 연산:
  • Graph Create() ::= 그래프 생성
  • Destroy(Graph) ::= 그래프 기억장소 반납
  • Graph Copy_Tree(Graph) ::= 그래프 복사
  • InsertVertex() ::= 그래프에 정점 삽입 InsertEdge() ::= 그래프에 간선 추가
  • DeleteVertex() ::= 정점 삭제 DeleteEdge() ::= 간선 삭제
  • Search() ::= 정점 탐색
  • IsAdjacent() ::= 인접 정점 여부 확인
  • ExistPath() ::= 경로가 존재하는지 확인
  • PathLength() ::= 경로 길이 계산
  • BFS() ::= 너비 우선 탐색
  • DFS() ::= 깊이 우선 탐색

그래프 탐색

그래프 G=(V, E)와 V(G)에 있는 정점 v가 주어졌을 때, 정점 v에 도달할 때까지 G의 정점을 방문하는 연산 → 만일 그래프 내에 정점이 v가 없다면, 그래프의 모든 정점을 방문한 후 종료함

깊이 우선 탐색(Depth First Search, DFS)

• 시작: 출발점 v를 방문
• 다음으로 v에 인접하고 아직 방문하지 않은 정점 w를 선택하여 w를 출발점으로 다시 깊이 우선 탐색(인접하고 아직 방문하지 않은 정점을 선택)
• 위의 두 과정을 모든 정점을 한 번씩 방문할 때까지 반복
• 만약 인접한 모든 정점들이 이미 방문한 정점인 경우, 가장 최근에 방문했던 정점 중에서 방문하지 않은 정점 w를 가진 정점을 선택하여 정점 w로부터 다시 깊이 우선 탐색 시작 → 스택을 사용하여 가장 최근에 선택의 지점에 있던 정점을 찾아냄
• 방문하지 않은 정점이 없으면 탐색 종료

// 순환 호출
void DFS(Graph* g, int s) {
	int i, adjacent;
	g -> visited[s] = 1;
	printf("%d", s);

	for(adjacent = 0; adjacent < g -> nv; adjacent++) {
		if(g -> adj[s][adjacent] && !g -> visited[adjacent]) {
			g -> visited[adjacent] = 1;
			DFS(g, adjacent);
		}
	}
}

// 스택 직접 운영
void DFS(int s) {
	int v, w;
	extern struct stack *st;
	extern int visited[];
	InitializeStack(st);
	push(st, s);
	visited[s] = 1;
	while((v=pop(st)) >= 0) {
		visited[v] = 1;
		while(v에 인접한 모든 노드 w)
			if(!visited[w]) push(st, w);
	}
}

너비 우선 탐색(Breadth First Search, BFS)

• 시작: 출발점 v를 방문
• 다음으로 v에 인접한 정점 w를 모두 방문한 후, 다시 w에 인접한 방문하지 않은 정점들을 차례로 방문
• 두 과정을 모든 정점을 한 번씩 방문할 때까지 반복
• 인접 정점을 모두 방문하기 때문에 큐를 사용

void BFS(Graph* g, int s) {
	int i, adjacent;
	int visited[MAX_VERTICES];
	for(i=0; i< g->nv; i++) visited[i]=0;
	
	int queue[MAX_VERTICES];
	int front=0, rear=0;

	visited[s]=1;
	queue[rear++]=s;

	while(front != rear) {
		s=queue[front++];
		printf("%d", s);
		for(adjacent=0; adjacent < g->nv; adjacent++) {
			if(g->adj[s][adjacent] && !visited[adjacent]) {
				visited[adjacent]=1;
				queue[rear++]=adjacent;
			}
		}
	}
}

최소 비용 신장 트리

• 트리: 사이클이 없는 단순 그래프
• 트리는 그래프이기는 하지만 루트를 가지기 때문에 (일반 그래프에는 없는) 계층 개념이 있고, 사이클이 없어서 한 정점에서 다른 정점으로 가는 경로가 유일한 구조
• 신장 트리(spanning tree): 그래프 G의 모든 정점과 간선의 일부(또는 전부)를 포함하는 트리
  • 주어진 그래프의 정점을 모두 포함함
  • n-1개의 간선으로 구성한 그래프
• G의 최소 부분 그래프: 그래프 G의 부분 그래프 중에서 간선의 수가 가장 작은 것
• 최소 비용 신장 트리: 가중치 그래프 G의 가중치가 작은 간선을 선택하여 구성된 신장 트리

프림(Prim) 알고리즘

n개의 정점을 갖는 연결 그래프 G에 대한 최소 비용 신장 트리 T를 구하는 알고리즘

• 그래프 전체에서 최소 비용을 갖는 간선 {u, v}를 선택하여 이 간선을 T에 추가함
• 이 간선을 T에 추가할 때 사이클을 형성하지 않으면 추가하고 아니면 무시함

void prim() {
	T = Ø;
	W = Ø;
	E로부터 최소 비용인 간선 {v, w}를 선택;
	while(T는 n-1개 이하의 간선 포함 && E는 공집합 아님) {
		E에서 간선 {v, w}를 제거;
		if({v, w}가 T 내에서 사이클을 생성 안함) {
			T = T ∪ {{v, w}}; // 선택한 간선 추가
			W = W ∪ {v, w}; // 선택한 정점 추가
		}
		else 간선 {v, w}를 버림;
		E로부터 W 내의 정점과 최소 비용으로 연결된 간선 {v, w}를 선택;
	}
}

크루스컬(Kruskal) 알고리즘

• 남은 간선 중에서 무조건 최소 비용인 간선을 선택한 후 사이클을 형성하지 않으면 그 간선을 선택함
• 중간 과정에 있는 T는 하나의 트리가 아니고 여러 개의 분산된 트리, 즉 숲일 수 있음

void kruskal() {
	while(T는 n-1개 이하의 간선 포함 && E는 공집합 아님) {
		E로부터 최소 비용인 간선 {v, w}를 선택;
		E에서 간선 {v, w}를 제거;
		if({v, w}가 T 내에서 사이클을 생성 안함) T = T ∪ {{v, w}};
		else 간선 {v, w}를 버림;
	}
}

솔린(Sollin) 알고리즘

• 간선이 하나도 없는 그래프의 모든 정점들로 구성된 숲에서 시작함
• 단계가 거듭되면서 숲 내의 트리들이 최소 비용을 갖는 간선으로 연결

void sollin() {
	// 집합 E의 초기 상태는 주어진 그래프의 간선 집합
	// 집합 F의 초기 상태는 그래프의 모든 정점들로 구성된 간선이 없는 숲

	T=Ø;
	while(T는 완전한 하나의 트리가 아님 && E는 공집합 아님) {
		for(F 내의 각각의 트리 T에 대하여) {
			T와 다른 트리를 연결하는 E의 간선 {v, w} 중에서 최소비용 간선 {v, w}를 선택;
			T = T ∪ {{v, w}};
			E에서 간선 {v, w}를 제거;
		}
		T에 새로 추가된 간선을 포함하여 F를 수정;
	}
}