STL Vector, 그래프, 트리 (20190517)

1. vector

vector<type> name;

array와 같다. 

(1) push_back(value) : 벡터에 value를 맨 뒤에 집어넣는다.

(2) pop_back() : 맨 뒤의 값을 뺀다.

(3) size() : 벡터의 사이즈 리턴.

 

2. 그래프

정점과 간선의 집합.

정점(node, vertex)

간선(edge, arc)

 

표현 방법에는 어떤게 있을까?

(1) 인접행렬

이차원배열로 정점과 정점의 연결관계를 나타냄.

arr[i][i]는 0이고 , 양방향그래프에선 arr[i][j]와 arr[j][i]의 값은 같다.

메모리 낭비가 너무 심해서 10^6만 되어도 터진다.

 

(2) 인접리스트

각 정점에서 연결된 정점만 표현해주는 리스트.

벡터를 사용하면 완젼 편리하다.

vector<int> graph[5]이렇게 하면 굿.

ex)

1 2
1 3
1 4
2 4
3 4

이렇게 입력되면, scanf("%d %d", &a, &b);

graph[a].push_back(b);
graph[b].push_back(a);

정리하면,

graph[1] =>2 3 4
graph[2] =>1 4
graph[3] =>1 4
graph[4] =>1 2 3

이렇게 들어가게 된다.

 

 

3. 그래프 탐색방법?

(1) DFS 깊이 우선 탐색

스택으로 구현한다.

하지만 스택을 사용하면 약간 머리가 어질어질 하기 때문에
스택과 유사한 구조를 가진 재귀를 사용한다.

 

(2) BFS 넓이 우선 탐색

큐로 구현한다.

현재 노드에서 연결된 모든 정점(visit한거 빼고)를 큐에 넣어준다.
넣어줄 때 해당 노드의 visit을 1로 바꿔주는거 잊지 말자.

많이 틀리는 부분은 방문체크

DFS, BFS 기본문제 https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

코드 : 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> v[1001];
queue<int> q;
int visit[1001];
void DFS(int node){
    printf("%d ", node);
    visit[node]=1;
    for(int i=0; i<v[node].size(); ++i){
        if(visit[v[node][i]]) continue;
        DFS(v[node][i]);
    }
}
void BFS(){
    int node=q.front();
    printf("%d ", node);
    q.pop();
    for(int i=0; i<v[node].size(); ++i){
        if(visit[v[node][i]]) continue;
        q.push(v[node][i]);
        visit[v[node][i]]=1;
    }
    if(!q.empty()) BFS();
}
int main(){
    int N, M, V;
    scanf("%d %d %d", &N, &M, &V);
    for(int i=0; i<M; ++i){
        int a, b;
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1; i<=N; ++i){
        sort(v[i].begin(), v[i].end());
    }
    DFS(V);
    printf("\n");
    for(int i=0; i<=N; ++i) visit[i]=0;
    q.push(V);
    visit[V]=1;
    BFS();
}

 

4. 트리

순환이 생기지 않는 그래프를 트리라고 한다.

간선의 개수는 항상 정점의 개수-1개이다.