Name	Name	Last commit message	Last commit date
parent directory ..
img	img
src	src
README.md	README.md

Graph

추천 문제
- [BOJ] 촌수계산 (소스코드) - 기본적인 그래프 BFS 순회 문제
- [BOJ] DFS와 BFS (소스코드 - DFS 재귀) (소스코드 - DFS 비재귀)
- [BOJ] パーティー (소스코드) - BFS + 단계 별 순회
- [BOJ] Hide and Seek (소스코드) - 거리 계산에는 BFS 사용
- [BOJ] HIPERCIJEVI (소스코드) - 정점 간 간선이 너무 많을 경우, 잉여 정점을 더 생성해 메모리 초과 문제를 해결할 수 있음

그래프

기본 용어
- 정점(Vertex, Node): 그래프를 구성하는 요소중의 하나로 연결점
- 간선(Edge): 두 정점 간을 이어주는 선분
- 차수(Degree): 정점에 연결된 간선 개수
- 무방향 그래프(Undirected Graph): 간선에 방향성이 없는 경우
- 방향 그래프(Directed Graph) 간선에 방향성이 있는 경우
  - Outdegree: 해당 정점으로부터 나가는 간선의 수
  - Indegree: 해당 정점으로부터 들어오는 간선의 수
- 순환 그래프(Cyclic Graph): 임의의 한 정점으로부터 출발해 자기 자신으로 돌아올 수 있는 경로(cycle)가 존재하는 그래프
- 비순환 그래프(Acyclic Graph): 임의의 한 정점으로부터 출발해 자기 자신으로 돌아올 수 있는 경로가 존재하지 않는 그래프
- 완전 그래프(Complete Graph): 모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프
- 연결 그래프(Connected Graph): 임의의 두 정점 사이에 경로가 존재하는 그래프
- 단순 그래프(Simple Graph): 임의의 두 정점 사이에 오직 1개의 간선만이 연결되어 있는 그래프
표현
- 인접 행렬(Adjacency Matrix)
  - 총 정점 수가 V일 때, 공간복잡도는 O(V²)
  - 정점 연결 상태 확인 시 시간복잡도는 O(1)
  - 어떤 정점에 연결되어 있는 정점들을 확인하고자 할 때의 시간복잡도는 O(V)
  - 무방향 그래프를 인접 행렬로 표현 시 대칭 형태를 나타냄
  - 방향 그래프를 인접 행렬로 표현하면 행은 출발 정점, 열은 도착 정점을 나타냄
  - 행과 열이 가리키는 위치에 있는 값은 간선의 가중치
  - 행과 열이 0이라면, 해당 행에서 열로 향하는 간선은 존재하지 않음
```
    // n X m directed graph
    vector<vector<int>> adj_matrix(n+1,vector(m+1)); // 1-based

    int e;
    cin>>e;
    for (int i = 1; i<=e; ++i) {
        int u, v;
        cin>>u>>v;
        adj_matrix[u][v]=1;
    }

    // n X m undirected graph
    vector<vector<int>> adj_matrix(n+1,vector(m+1)); // 1-based

    int e;
    cin>>e;
    for (int i = 1; i<=e; ++i) {
        int u, v;
        cin>>u>>v;
        adj_matrix[u][v]=1;
        adj_matrix[v][u]=1;
    }
```
- 인접 리스트(Adjacency Lists)
  - 총 정점 수가 V, 총 간선 수가 E일 때, 공간복잡도는 O(V+E)
    - V가 크면서 상대적으로 E가 작을 경우 공간을 절약할 수 있음
    - 모든 리스트에서의 원소 개수는 방향 그래프일 경우 E개, 무방향 그래프일 경우 2E개
  - 어떤 정점에 연결되어 있는 정점들을 확인하고자 할 때, 해당 정점에 연결된 리스트의 수만큼만 순회하면 결과를 얻을 수 있음 (O(dev(V)))
```
    // n X m directed graph
    vector<vector<int>> adj_list(n+1); // 1-based

    int e;
    cin>>e;
    for (int i = 1; i<=e; ++i) {
        int u, v;
        adj_list[u].push_back(v);
    }

    // n X m undirected graph
    vector<vector<int>> adj_list(n+1); // 1-based

    int e;
    cin>>e;
    for (int i = 1; i<=e; ++i) {
        int u, v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
```
- 비교

그래프를 사용한 BFS

모든 정점이 queue에 1번씩 들어가므로, 인접 행렬에서의 시간복잡도는 O(V²), 인접 리스트에서의 시간복잡도는 O(V+E)
연결 그래프에서의 순회

    vector<vector<int>> adj_list(n+1); // 1-based
    vector<bool> is_visited(n+1);

    void bfs()
    {
        queue<int> q;
        q.push(1);
        is_visited[1]=true;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            cout << cur << ' ';

            for (int next : adj_list[cur]) {
                if (is_visited[next]) {
                    continue;
                }
                q.push(next);
                is_visited[next]=true;
            }
        }

        return;
    }

연결 그래프에서 1번 정점과의 거리

    vector<vector<int>> adj_list(n+1); // 1-based
    vector<int> dist(n+1);

    void bfs()
    {
        for (int i = 1; i<=n; ++i) {
            dist[i]=-1; // init.
        }

        queue<int> q;
        q.push(1);
        dist[1]=0;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();

            for (int next : adj_list[cur]) {
                if (dist[next]!=-1) {
                    continue;
                }
                q.push(next);
                dist[next]=dist[cur]+1;
            }
        }

        return;
    }

연결 그래프가 아닐 때의 순회

    vector<vector<int>> adj_list(n+1); // 1-based
    vector<bool> is_visited(n+1);

    void bfs(int v)
    {
        queue<int> q;
        for (int i = 1; i<=v; ++i) {
            if (is_visited[i]) {
                continue;
            }

            q.push(i);
            is_visited[i]=true;
            while (!q.empty()) {
                int cur = q.front();
                q.pop();
                cout << cur << ' ';

                for (int next : adj_list[cur]) {
                    if (is_visited[next]) {
                        continue;
                    }
                    q.push(next);
                    is_visited[next]=true;
                }
            }
        }

        return;
    }

그래프를 사용한 DFS

모든 정점이 queue에 1번씩 들어가므로, 인접 행렬에서의 시간복잡도는 O(V²), 인접 리스트에서의 시간복잡도는 O(V+E)
연결 그래프에서의 순회(비재귀 방법)
- 연결된 정점이 여러 개일 때, BFS와 유사하게 동작
- 일반적인 DFS 동작과 차이가 있음

    vector<vector<int>> adj_list(n+1); // 1-based
    vector<bool> is_visited(n+1);

    void dfs()
    {
        stack<int> s;
        s.push(1);
        is_visited[1]=true;
        while (!s.empty()) {
            int cur = s.top();
            s.pop();
            cout << cur << ' ';

            for (int next : adj_list[cur]) {
                if (is_visited[next]) {
                    continue;
                }
                s.push(next);
                is_visited[next]=true;
            }
        }

        return;
    }

연결 그래프에서의 순회(재귀 방법)
- 일반적인 DFS 동작 코드 I

    vector<vector<int>> adj_list(n+1); // 1-based
    vector<bool> is_visited(n+1);

    is_visited[1]=true;
    dfs(1);
   
    ...

    void dfs(int cur)
    {
        cout << cur << ' ';

        for (int next : adj_list[cur]) {
            if (is_visited[next]) {
                continue;
            }
            is_visited[next]=true;
            dfs(next);
        }

        return;
    }

연결 그래프에서의 순회(비재귀 방법)
- 일반적인 DFS 동작 코드 II

    vector<vector<int>> adj_list(n+1); // 1-based
    vector<bool> is_visited(n+1);

    void dfs()
    {
        stack<int> s;
        s.push(1);
        while (!s.empty()) {
            int cur = s.top();
            s.pop();
            if (is_visited[cur]) {
                continue;
            }
            is_visited[cur]=true;
            cout << cur << ' ';

            for (int next : adj_list[cur]) {
                if (is_visited[next]) {
                    continue;
                }
                s.push(next);
            }
        }

        return;
    }

연결 그래프가 아닐 때의 순회

    vector<vector<int>> adj_list(n+1); // 1-based
    vector<bool> is_visited(n+1);

    void dfs(int v)
    {
        stack<int> s;
        for (int i = 1; i<=v; ++i) {
            if (is_visited[i]) {
                continue;
            }

            s.push(i);
            while (!s.empty()) {
                int cur = s.top();
                s.pop();
                if (is_visited[cur]) {
                    continue;
                }
                is_visited[cur]=true;
                cout << cur << ' ';

                for (int next : adj_list[cur]) {
                    if (is_visited[next]) {
                        continue;
                    }
                    s.push(next);
                }
            }
        }

        return;
    }

연습문제

[BOJ] 연결 요소의 개수
(소스코드 - BFS)
(소스코드 - DFS 비재귀 I)
(소스코드 - DFS 비재귀 II)
(소스코드 - DFS 재귀) - 추천

// BFS
#include <bits/stdc++.h>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin>>n>>m;
    vector<vector<int>> adj_list(n+1);
    for (int i = 1; i<=m; ++i) {
        int u, v;
        cin>>u>>v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }

    vector<bool> is_visited(n+1);
    queue<int> q;
    int res = 0;
    for (int i = 1; i<=n; ++i) {
        if (is_visited[i]) {
            continue;
        }
        
        ++res;
        q.push(i);
        is_visited[i]=true;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();

            for (int next : adj_list[cur]) {
                if (is_visited[next]) {
                    continue;
                }
                q.push(next);
                is_visited[next]=true;
            }
        }
    }
    cout << res;

    return 0;
}

// DFS 1 - BFS 유사 동작 
#include <bits/stdc++.h>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin>>n>>m;
    vector<vector<int>> adj_list(n+1);
    for (int i = 1; i<=m; ++i) {
        int u, v;
        cin>>u>>v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }

    vector<bool> is_visited(n+1);
    stack<int> s;
    int res = 0;
    for (int i = 1; i<=n; ++i) {
        if (is_visited[i]) {
            continue;
        }

        ++res;
        s.push(i);
        is_visited[i]=true;
        while (!s.empty()) {
            int cur = s.top();
            s.pop();

            for (int next : adj_list[cur]) {
                if (is_visited[next]) {
                    continue;
                }
                s.push(next);
                is_visited[next]=true;
            }
        }
    }
    cout << res;

    return 0;
}

// DFS 2 - 일반적인 DFS 동작
#include <bits/stdc++.h>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin>>n>>m;
    vector<vector<int>> adj_list(n+1);
    for (int i = 1; i<=m; ++i) {
        int u, v;
        cin>>u>>v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }

    vector<bool> is_visited(n+1);
    stack<int> s;
    int res = 0;
    for (int i = 1; i<=n; ++i) {
        if (is_visited[i]) {
            continue;
        }

        ++res;
        s.push(i);
        while (!s.empty()) {
            int cur = s.top();
            s.pop();
            if (is_visited[cur]) {
                continue;
            }
            is_visited[cur]=true;

            for (int next : adj_list[cur]) {
                if (is_visited[next]) {
                    continue;
                }
                s.push(next);
            }
        }
    }
    cout << res;

    return 0;
}

// DFS Rec.
#include <bits/stdc++.h>

using namespace std;

void dfs(int cur);

vector<bool> is_visited;
vector<vector<int>> adj_list;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin>>n>>m;
    adj_list=vector<vector<int>>(n+1);
    for (int i = 1; i<=m; ++i) {
        int u, v;
        cin>>u>>v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }

    is_visited=vector<bool>(n+1);
    int res = 0;
    for (int i = 1; i<=n; ++i) {
        if (is_visited[i]) {
            continue;
        }
        
        ++res;
        is_visited[i]=true;
        dfs(i);
    }
    cout << res;

    return 0;
}

void dfs(int cur)
{
    for (int next : adj_list[cur]) {
        if (is_visited[next]) {
            continue;
        }
        is_visited[next]=true;
        dfs(next);
    }

    return;
}

이전 - Two Pointer	목록	다음 - Tree

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

graph

graph

README.md

Graph

그래프

그래프를 사용한 BFS

그래프를 사용한 DFS

연습문제

Files

graph

Directory actions

More options

Directory actions

More options

Latest commit

History

graph

Folders and files

parent directory

README.md

Graph

그래프

그래프를 사용한 BFS

그래프를 사용한 DFS

연습문제