그래프(Graph)

그래프(Graph) :  정의

구성 : 정점(Vertex), 간선(Edge)

G = (V, E)

 

경로(Path)

사이클(Cycle)

단순 경로와 단순 사이클(Simple Path and Simple Cycle) : 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클(일반적인 경우)

방향 있는 그래프(Directed Graph)

방향 없는 그래프(Undirected Graph,) : 양방향 그래프(Bidirection Graph)

간선 여러개(Multiple Edge)

루프(Loop)

가중치(Weight)

차수(Degree)

연결요소(Connected Component)

이분그래프(Bipartite Graph) : DFS또는 BFS 탐색으로 이분 그래프인지 아닌지 확인가능

플러드 필(Flood Fill) : 어떤 위치와 연결된 모든 위치를 찾는 알고리즘

 

미로탐색 : DFS탐색으로는 문제를 풀 수 없다. BFS는 단계별로 진행되므로 사용가능.

 

 

 

그래프의 표현(Representation of Graph)

인접 행렬(Adjacency-matrix) : N X N 크기의 이차원 배열

인접 리스트(Adjacency-list) : 링크드 리스트를 이용하여 구현(vector와 같이 길이를 변경할 수 있는 배열을 이용)

 - 공간복잡도(Space Complexity) : 인접 행렬O(V^2) > 인접 리스트O(E)

 - 시간복잡도(Time Complexity) : 인접 행렬O(V^2) > 인접 리스트O(V+E) 

 - 단방향, 양방향 그래프의 경우 : vector<int>

    * vector<int> a(10), vector<int> a[10]과 다름을 유의.

 - 가중치 그래프의 경우 : vector<pair<int, int>> 

간선 리스트(Edge-list) : O(V+E)

 - STL을 사용할 수 없을때, 배열을 이용해서 구현

 - 간선을 정렬후 성질을 이용

 - x -> ? 간선의 경우, cnt[x-1]부터cnt[x]-1까지 있음.

 

그래프의 탐색

깊이 우선 탐색(Depth First Search ,DFS) : 최대한 깊숙히 가는것, Stack(재귀)

너비 우선 탐색(Breadth First Search ,BFS) : 최대한 넓게 가는것, Queue

 

//인접리스트를 사용한 dfs, bfs 구현
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> a[1001];
bool check[1001];

void dfs(int x) {
	check[x] = true;
	printf("%d ", x);

	for (int i = 0; i < a[x].size(); ++i) {
		int next = a[x][i];
		if (check[next] == false) {
			dfs(next);
		}
	}
}

void bfs(int x) {
	queue<int> q;
	check[x] = true; q.push(x);

	while (!q.empty()) {
		int y = q.front(); q.pop();
		printf("%d ", y);
		for (int i = 0; i < a[y].size(); ++i) {
			int next = a[y][i];
			if (check[next] == false) {
				check[next] = true; q.push(next);
			}
		}
	}
}

int main(void) {
	int n, m, v;
	scanf("%d%d%d", &n, &m, &v);

	for (int i = 0; i < m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y); a[y].push_back(x);
		sort(a[x].begin(), a[x].end());
		sort(a[y].begin(), a[y].end());
	}

	dfs(v);
	memset(check, false, sizeof(check));
	puts("");
	bfs(v);
}

 

 

//간선리스트를 사용한 bfs, dfs 구현
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct E {
	int start;
	int end;
};

bool cmp(const E &u, const E &v) {
	if (u.start == v.start) return u.end < v.end;
	else return u.start < v.start;
}

E Elist[20001];
int cnt[1001];
bool check[1001];

void dfs(int node) {
	check[node] = true;
	printf("%d ", node);

	for (int i =cnt[node -1]; i <= cnt[node]-1; ++i) {
		int next = Elist[i].end;
		if (check[next] == false) {
			dfs(next);
		}
	}
}

void bfs(int start) {
	queue<int> q;
	check[start] = true; q.push(start);

	while (!q.empty()) {
		int node = q.front(); q.pop();
		printf("%d ", node);
		for (int i = cnt[node -1]; i <= cnt[node]-1; ++i) {
			int next = Elist[i].end;
			if (check[next] == false) {
				check[next] = true; q.push(next);
			}
		}
	}
}

int main(void) {
	int n, m, v;
	scanf("%d%d%d", &n, &m, &v);
	for (int i = 0; i < m; ++i) {
		int x, y;
		scanf("%d%d", &Elist[i].start, &Elist[i].end);
		Elist[i+m].start = Elist[i].end;
		Elist[i+m].end = Elist[i].start;
	}

	sort(Elist, Elist + 2*m, cmp);
	for (int i = 0; i < 2*m; ++i) {
		cnt[Elist[i].start]++;
	}
	for (int i = 0; i < n; ++i) {
		cnt[i+1] += cnt[i];
	}

	dfs(v);
	memset(check, false, sizeof(check));
	puts("");
	bfs(v);
}