인접행렬(adjacency matrix)

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

• 0 : 두 정점 사이 경로가 없음
• 1 : 두 정점 사이 경로가 있음
• a[from][to] = 0 or 1

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 << "까지 경로 존재";
            // 탐색 로직
            bfs(i);
            dfs(i);    
        }
    }
}

문제

Q. 3번 노드에서 5번 노드까지 가는 단방향 노드 표현

a[3][5] = 1;

Q. 3번 노드에서 5번 노드까지 가는 양방향 노드 표현

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

Q. 정점의 개수가 20개인 노드가 있고 인접행렬로 표현할 때, 메모리를 최소로 쓴다면 어떻게 ?

bool a[20][20]

Q. 인접행렬을 기반으로 탐색하기

1번. 정점은 0번부터 9번까지 10개의 노드가 있다. 1-2/ 1-3/ 3-4 경로가 있다. 인접행렬로 표현

bool a[10][10];

a[1][2] = 1;
a[2][1] = 1;
a[1][3] = 1;
a[3][1] = 1;
a[3][4] = 1;
a[4][2] = 1;

2번. 0번부터 방문 안한 노드를 찾고 해당 노드부터 방문, 연결된 노드를 이어서 방문해서 출력하는 재귀함수를 만들고 싶다면 어떻게 해야할까? 또한, 정점을 방문하고 다시 방문하지 않게 만드려면 어떻게 해야할까?

bool visited[10];
int V = 10;

void Visit(int u)
{
	visited[u] = true;
    
    for(int v=0; v<V; i++)
    {	
    	if (visited[v])
        	continue;
    	if (a[u][v])
        	Visit(v);
    }
    
    return;
}


int main()
{
	for(int i=0; i<V; i++)
    {
    	for(int j=0; j<V; j++)
        {
        	if (a[i][j] && !visited[i])
	        	Visit(i);
        }
    }

}