인접 행렬 이란?

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

정사각형 행렬의 각 요소가 0 또는 1이라는 값을 가진다.

여기서 0은 두 정점 사이에 간선이 없음을 의미하며 1은 두 정점 사이에 간선이 존재함을 의미한다.

이 그래프를 이차원 배열로 만든다면?

bool a[4][4] = {
		{1, 1, 1, 1},
		{1, 1, 1, 0},
		{1, 1, 1, 0},
		{1, 0, 0, 1}
};

a[1][0] : 1번 노드에서 0번 노드 사이의 간선 존재 여부

경로 탐색 로직의 예

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

Q. 3번 노드에서 5번 노드로 가는 단방향 경로가 있고, 이를 인접행렬로 표현한다면?

a[3][5] = 1;

Q. 3번 노드에서 5번 노드로 가는 양방향 경로가 있고, 이를 인접행렬로 표현한다면?

a[3][5] = 1;
a[5][3] = 1;