그래프 종류
- 무향 그래프
- 유향 그래프
- 가중치 그래프
- 사이클 없는 방향 그래프 (DAG)
(사이클: 두개 이상의 노드를 거쳐서 되돌아 올 수 있는 구조)
- 위상정렬 문제
- 최장거리 구하기 : 가중치에 음수로 바꿔서 최단거리 문제(다익스트라) 로 구하기
- 완전 그래프: 정점들에 대해 가능한 모든 간선들을 가진 그래프(간선 개수= nC2)
그래프 표현
인접 행렬
100만 * 100만 = 1억 불가?
- 무향그래프는 대각선 대칭
- 행 기준: A행 ~ A에서 나가는 정점(진출차수)
- 열 기준: A열 ~ A로 들어오는 정점(진입차수)
인접리스트
vector<vector<>> : 일단 출발점으로부터 연결되는 것들만
노드 번호가 10, 100만개이면 일차원 배열 형태로 잡는다.
가중치가 들어온다면,
간선 배열
만약에 노드 개수가 10억개 이상이면, map 구조로 만듣다.
map<노드번호, vector<pair<>>>
노드개수 1000개 이하
2차원 배열
노드개수
2차원 벡터
노드 개수가 10억이면
map<int, vector>>
깊이우선탐색(dfs)
선형구조: 순차 / 이진(sort 되어 있어야함)
비선형구조: bfs/dfs
노드 번호 주로 1부터
stack
방문 유무 vt[]
stack 들어오면서 check: 절대 두번 들어오지 않음
1. 출발점을 stack이나 queue에 넣기
2. 무한루프(!stack.empty) : 연결되어 있고 사용하지 않은것들만 stack에 push
stack 빠져가면서 check
너비우선탐색 (bfs)
배열기반 코드
#include <vector>
#include <stdio.h>
#include <iostream>
#include <stack>
#include <queue>
#define MAXN 1001
using namespace std;
int V, E;
int g[MAXN][MAXN];
void bfs(int start) {
//visited input할 때 check
queue<int> q; //노드 번호 저장
vector<int> vt(V + 1); //true,false보다 int가 더빠르다.
q.emplace(start);
vt[start] = 1; //들어가면서 방문 선언!
printf("[");
while (!q.empty()) {
int u = q.front(); s.pop();
//u로부터 연결되어 있고, 사용하지 않은
for (int i = 1; i <= V; ++i) {
if (g[u][i] && !vt[i]) {
vt[i] = 1;
q.emplace(i);
}
}
printf("%d ", u);
}
puts("]");
}
void dfs1(int start) {
//visited input할 때 check
stack<int> s; //노드 번호 저장
vector<int> vt(V+1); //true,false보다 int가 더빠르다.
s.emplace(start);
vt[start] = 1; //들어가면서 방문 선언!
printf("[");
while (!s.empty()) {
int u = s.top(); s.pop();
//u로부터 연결되어 있고, 사용하지 않은
for (int i = 1; i <= V; ++i) {
if (g[u][i] && !vt[i]) {
vt[i] = 1;
s.emplace(i);
}
}
printf("%d ", u);
}
puts("]");
}
void dfs2(int start) {
//visited input할 때 check
stack<int> s; //노드 번호 저장
vector<int> vt(V + 1); //true,false보다 int가 더빠르다.
s.emplace(start);
printf("[");
while (!s.empty()) {
int u = s.top(); s.pop();
//나올때 체크하는 방식이므로 stack에 두번 들어갈 수 있다.
if (vt[u]) continue; //사용했으면 continue;
vt[u] = 1; //나올때 방문 선언!
//u로부터 연결되어 있고, 사용하지 않은
for (int i = 1; i <= V; ++i) {
if (g[u][i] && !vt[i]) {
//vt[i] = 1;
s.emplace(i);
}
}
printf("%d ", u);
}
puts("]");
}
int vt[MAXN];
//깊이 우선 탐색을 재귀로 돌린 것 : backtracking
int dfs_rec(int start) {
cout << start;
vt[start] = 1;
for (int i = 1; i <= V; ++i) {
if (!vt[i] && g[start][i]) {
dfs_rec(i);
}
}
}
int main() {
int sn, en;
freopen("input.txt", "r", stdin);
scanf("&d %d", &V, &E);
for(int i = 0 ; i < E ;++i){
scanf("%d %d", &sn, &en);
g[sn][en] = 1;
g[en][sn] = 1;
}
return 0;
}
```
unordered_map 사용
#include <vector>
#include <stdio.h>
#include <iostream>
#include <stack>
#include <queue>
#include <unordered_map>
#define MAXN 1001
using namespace std;
int V, E;
vector<vector<int>>g;
//unordered map : 십만개 - 우리가 아는 hash
unordered_map<int, vector<int>> gg;
void dfs(int start) {
stack<int> s;
vector<int> vt(V + 1);
s.emplace(start);
vt[start] = 1;
printf("dfs: ");
while(!s.empty()){
int u = s.top(); s.pop();
for (int& t : g[u]) {
if (vt[t]) continue;
s.emplace(t);
vt[t] = 1;
}
}
}
int main() {
int sn, en;
freopen("input.txt", "r", stdin);
scanf("&d %d", &V, &E);
g.clear();
g.resize(V + 1);
for(int i = 0 ; i < E ;++i){
scanf("%d %d", &sn, &en);
g[sn].emplace_back(en);
g[en].emplace_back(sn);
gg[sn].emplace_back(en);
gg[en].emplace_back(sn);
}
for (int i = 1; i <= V; ++i) {
cout << i << " : ";
for (int t : gg[i]) {
cout << t << " ";
}cout << "\n";
}
return 0;
} /*
7 14
1 2 3
1 3 5
2 3 1
2 4 2
2 5 4
3 2 3
3 4 4
3 6 6
4 5 7
4 6 2
5 6 4
5 7 5
6 5 3
6 7 8
*/
#include<stdio.h>
#include <queue>
#include <vector>
using namespace std;
vector<vector<pair<int,int>>> g;
//무향그래프
int V;
void bfs(int start) {
//visit input check
queue<int> q;
vector<int> dist(V + 1, INT_MAX);
vector<int> p(V + 1);
dist[start] = 0;
q.emplace(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto& t : g[u]) {
if (dist[t.first] > dist[u] + t.second) {
dist[t.first] = dist[u] + t.second;
q.emplace(t.first);
p[t.first] = u;
}
}
}
printf("idx\t:\t[");
for (int i = 1; i <= V; ++i) {
printf("%d ", i);
}puts("]");
printf("dist\t:\t[");
for (int i = 1; i <= V; ++i) {
printf("%d ", dist[i]);
}puts("]");
printf("p\t:\t[");
for (int i = 1; i <= V; ++i) {
printf("%d ", p[i]);
}puts("]");
}
int main() {
freopen("input.txt", "r", stdin);
int E;
int sn, en, val;
scanf("%d %d", &V, &E);
g.clear();
g.resize(V + 1);
//pair f:nodeNum, s : time
for (int i = 0; i < E; ++i) {
scanf("%d %d %d", &sn, &en, &val);
g[sn].emplace_back(en, val);
}
#if 0
for (int i = 1; i <= V; ++i) {
printf("%d : ", i);
for (auto& t : g[i]) {
printf("(%d,%d) ", t.first, t.second);
}
puts("");
}
#endif
bfs(1);
return 0;
}