앞에서 Graph, Tree, BST에 대해서 공부했다. 그렇다면, 이것들을 어떻게 컴퓨터에 입력할 수 있을까??

<aside> 💡 정답은 인접행렬과 인접리스트이다.

</aside>

※ 인접해있다 : 연결되어 있다

인접행렬

• 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미합니다.
• 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐을 의미하며, 0은 두 정점 사이의 경로가 없음을 의미하며, 1은 두 정점 사이의 경로가 있음을 의미한다.

• 다음 그래프를 한번 살펴보자.
• 1 - 1, 2 - 2를 보면 0으로 되어있는 것을 볼 수 있는데 자기자신을 나타내는 것이며 해당 정점의 사이클이 없을 때는 0, 사이클이 있을 때는 1로 표기를 합니다.
• 0 - 1 이 연결되어있기 때문에 a[0][1] = 1이 됩니다. 그러나 1 - 3은 연결되어있지 않기 때문에 a[1][3] = 0이 됩니다.

이것을 코드로 표현하자면 이렇게 된다.

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

Code로 인접행렬 사용해보기

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);
		}
	}
}