인접리스트(adjacency list)

각 정점마다 연결된 정점들 배열로 만들기

const int V = 4;
vector<int> adj[V];

// 0 : 1,2
adj[0].push_back(1);
adj[0].push_back(2);

// 1: 0
adj[1].push_back(0);

// 2: 0
adj[2].push_back(0);

연결리스트 VS 벡터

• 마지막 요소에 삽입, 삭제 : O(1)
• 특정 요소 탐색 : O(n)

연결리스트

• n번째 인덱스에 삽입, 삭제 : O(1)
• n번째 요소 참조 : O(n)

벡터

• n번째 인덱스에 삽입, 삭제 : O(n)
• n번째 요소 참조 : O(1)

인접리스트를 구현할 때 많이 사용되는 연산은

• 마지막 요소에 삽입
• 특정 요소 탐색
  이기 때문에 벡터로 구현해도 무방함.

문제

인접리스트 기반으로 탐색하기

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

const int V = 10;
vector<int> adj[10];

adj[1].push_back(2);
adj[1].push_back(3);

adj[2].push_back(1);

adj[3].push_back(1);
adj[3].push_back(4);

adj[4].push_back(3);

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

bool visited[V];

Visit(int u)
{
	visited[u] = true;
    
    for(int i : adj[u])
    {
    	if (visited[i])
        	continue;
        Visit(i);
    }
    
    return;
}


for(int i=0; i<V; i++)
{
	if (adj[i].size() && !visited[i]) Visit(i);
}