인접행렬 (1 / 2)

1. 그래프 : 정점과 간선으로 이루어져 있는 자료구조

    1-1. 정점 : 노드

    1-2. 간선 : 단방향 간선, 양방햔 간선(= 무방향 간선)

 

2. 인접행렬 : 정점과 간선을 컴퓨터에게 그래프로 알려주기 위한 방법

      - 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미

      - 정사각형 행렬의 각 요소가 0 또는 1이라는 값을 가짐을 의미

      - 표기법

         a[from][to] = 1 : from ~ to로가는 간선이 있음, 0이면 없음

         ex:)

         a[0][1] = 1, 0에서 1로 가는 간선이 존재

         a[2][0] = 1, a[2][1] = 1 ..

 

         0  1  1  1

         1  0  1  0

         1  1  0  0

         1  0  0  0

 

         - c++ 코드 예시

x, y = 4;

bool a[x][y] = {
   {0, 1, 1, 1},
   {1, 0, 1, 0},
   {1, 1, 0, 0},
   {1, 0, 0, 0},
};



# a[0][1] = 1
# a[2][1] = 1
# a[3][0] = 1
# ...

for(int i = 0; i < x; i++) { # y를 중심으로 x를 본다 (= 가로로 탐색)
	for(int j = 0; j < y; j++) {
        if(a[i][j]) {
            cout << i << "부터 " << j << "까지 경로가 있습니다.\n";
            // 해당 정점(=i)으로부터 탐색하는 로직
            bfs(i);
            dfs(i);
        }
    }
    
}

 

출처 : 인프런 강의, CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조, 강사 : 큰돌