About Graph & BFS,DFS

그래프가 제일 어렵구나........ ㅜㅜ

먼저 그래프란 무엇인가..?

A graph is a data structure that consists of the following two components:

1. A finite set of verices also called as nodes. 

2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not the same as (v, u) in case of a directed graph(di-graph, -> oneway graph) . The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. (u->v) . The edges may contain weight/value/cost.

그리고 2종류의 most commonly used representations of a graph 가 있다. (아래의 dfs/bfs표는 잠시 무시 ;)

DFS	BFS
Stack 사용	Queue 사용
재귀 사용	최단거리, 최소 횟수를 구하는 문제.
어떤 경우의 수를 구하는 문제에 사용
시간복잡도 : 인접행렬 일때 O(|V|^2), 인접 리스트일때 O(|V|+|E|)

그래프의 표현법은 2가지가 있다. 

보통 가장 많이 사용되는 방법은 2차원 배열로 구성된 인접 행렬(Adjacency matrix)이나 링크드 리스트(linked list)로 구현한 인접 리스트(Adjacency list) 라고 한다.

 

(a)는 그래프이고, 

(b)는 인접 행렬 표현,

(c)는 인접 리스트 표현이다. 

인접 행렬 표현의 가장 큰 장점은, 정점의 번호 u,v 가 주어졌을 때, 두 정점을 잇는 간선이 있는지를 한 번의 배열 접근만으로 확인 할 수 있다는 것입니다. |V| x |V| 크기의 2차원 배열을 사용하기 때문에, 실제 간선의 개수와 상관없이 O(|V|^2) 크기의 공간을 사용한다는 문제점이 있다. 

* in english : 

Adjacency Matrix Pros and Cons.

PROS : Representation is easier to implement and follow. Removing an edge takes O(1) time !  Queries like whether there is an edge from vertex'u' to vertex'v' are efficient and can be done O(1). 

CONS : Consumes more spce O(V^2). Even if the graph is sparse(contains less number of edges), it consumes the same space. Adding a vertex is O(V^2) time. Computing all neighbors of a vertex takes O(V) time. 

반면 인접 리스트의 경우는  ,간선 (u,v) 가 존재하는지 확인하기 위해서는, 연결 리스트를 처음부터 읽어가면서 각 원소를 일일히 확인해야한다. 하지만 인접 리스트 표현은 |V|개의 연결 리스트에 실제 간선 수만큼 원소가 들어있으므로 (쓸 만큼만 공간을 할당해서 쓴다는 의미) 전체 O(|V| + |E|)의 공간만을 사용한다. 물론 간선의 개수가 |V|^2와 비슷하다면 두 표현 방식은 비슷한 메모리를 사용한다. 

PROS : Save space O(|V| + |E|). Adding a vertex is easier. 

CONS : Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).

 

 

 

백준 그래프 가장 기초적인 문제인 DFS & BFS문제를 풀어보자.

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

먼저 DFS가 솔루션이 더 짧아보이니 DFS를 츄라이해본다.

#include <stdio.h>
#define MAX_VERTICS 1001
int DFS_V[MAX_VERTICES] = {0, };
int BFS_V[MAX_VERTICES] = {0, };
int graph[MAX_VERTICES][MAX_VERTICES] = {0,};
// 인접 행렬로 풀었다. 
/*    1  2  3  4
 * 1     1  1  1
 * 2  1        1
 * 3  1        1
 * 4  1  1  1
 */
int queue[MAX_VERTICES];
void dfs(int v, int vertices);
void bfs(int v, int vertices);

int main() {
    int vertices, edges, vertex, i, j;
                     /*    4   ,   5   ,    1   */
    scanf("%d %d %d", &vertices, &edges, &vertex);
                     /*   요소 ,  간선 ,  시작점*/

    while(edges--) { // 양쪽에 다 간선 연결하는 역할
        scanf("%d %d", &i, &j);
        graph[i][j] = 1;
        graph[j][i] = 1;
    }
    dfs(vertex, vertices);
    printf("\n\n\n");
    bfs(vertex, vertices);
    return 0;
}

void dfs(int v, int vertices) {
    int w;
    DFS_V[v] = 1;
    printf("..... vertex :%d \n", v);
    for( w = 1; w <= vertices; w++) {
        printf("graph[%d][%d]: %d, DFS_V[%d] : %d\n",
                v, w, graph[v][w], w, DFS_V[w]);
        if(graph[v][w] == 1 && DFS_V[w] == 0)
            dfs(w, vertices);
    }
}

void bfs(int v, int vertices)
{
	int w;
    int front, rear, pop;
    front = rear = 0;
    printf("%d ", v);
    BFS_V[v] = 1;
    queue[0] = v;
    rear++;
    while (front < rear) {
        pop = queue[front];
        front++;

        for ( w = 1; w <= vertices; w++) {
            printf("graph[%d][%d]: %d, BFS_V[%d] : %d\n",
                v, w, graph[v][w], w, BFS_V[w]);
            if( graph[pop][w] == 1 && BFS_V[w] == 0 ) {
                printf("%d \n", w);
                queue[rear] = w;
                rear++;
                BFS_V[w] = 1;
            }
        }
    }

}

출력 결과값 

DFS: 
..... vertex :1 
graph[1][1]: 0, DFS_V[1] : 1
graph[1][2]: 1, DFS_V[2] : 0
..... vertex :2 
graph[2][1]: 1, DFS_V[1] : 1
graph[2][2]: 0, DFS_V[2] : 1
graph[2][3]: 0, DFS_V[3] : 0
graph[2][4]: 1, DFS_V[4] : 0
..... vertex :4 
graph[4][1]: 1, DFS_V[1] : 1
graph[4][2]: 1, DFS_V[2] : 1
graph[4][3]: 1, DFS_V[3] : 0
..... vertex :3 
graph[3][1]: 1, DFS_V[1] : 1
graph[3][2]: 0, DFS_V[2] : 1
graph[3][3]: 0, DFS_V[3] : 1
graph[3][4]: 1, DFS_V[4] : 1
graph[4][4]: 0, DFS_V[4] : 1
graph[1][3]: 1, DFS_V[3] : 1
graph[1][4]: 1, DFS_V[4] : 1



BFS: 
1 
graph[1][1]: 0, BFS_V[1] : 1
graph[1][2]: 1, BFS_V[2] : 0
2 
graph[1][3]: 1, BFS_V[3] : 0
3 
graph[1][4]: 1, BFS_V[4] : 0
4 
graph[1][1]: 0, BFS_V[1] : 1
graph[1][2]: 1, BFS_V[2] : 1
graph[1][3]: 1, BFS_V[3] : 1
graph[1][4]: 1, BFS_V[4] : 1
graph[1][1]: 0, BFS_V[1] : 1
graph[1][2]: 1, BFS_V[2] : 1
graph[1][3]: 1, BFS_V[3] : 1
graph[1][4]: 1, BFS_V[4] : 1
graph[1][1]: 0, BFS_V[1] : 1
graph[1][2]: 1, BFS_V[2] : 1
graph[1][3]: 1, BFS_V[3] : 1
graph[1][4]: 1, BFS_V[4] : 1