방향이 틀린 그래프의 연결된 구성 요소 수

Question

일부 그래프 알고리즘 (이것은 숙제가 아니며 알고리즘과 데이터 구조)를 닦고 있습니다. 질문이 있습니다.

var graph = { 
    9: [19, 26], 
    13: [19, 5], 
    17: [], 
    26: [11, 18], 
    18: [9], 
    19: [], 
    23: [24], 
    24: [], 
    11: [], 
    18: [] 
}; 

그래프는 기본적으로 다음과 같습니다 :

얼마나 많은 연결-구성 요소는이 그래프에 나는 다음과 같은 무향 그래프가 가정? 그래프를 보는 것에서부터 3 가지 구성 요소가있는 것처럼 보입니다. 그러나 실제로 알고리즘을 구현하면 (각 꼭지점을 반복하고, 그 꼭지점을 시작점으로 사용하는 bfs를 수행하면 이라면 버텍스가 발견되지 않은) bfs는 발견 된 모든 꼭지점을 표시합니다.

9으로 시작하면 다음 노드를 발견하게됩니다 : [19, 26, 11, 18]. 그러나 13은 19의 인접 목록에 없기 때문에 검색되지 않습니다. 그러나 19은 13의 인접 목록에 있습니다. 이것이 내가 하나의 추가 구성 요소로 끝나는 이유입니다.

이 정보가 맞습니까? 실제로 4 개의 개별 구성 요소가 있습니까? 그렇다면 연결 구성 요소에 대한 제 이해가 잘못 되었습니까?

Answer 1

문제는 방향성 그래프의 인접리스트 표현을 위해, 당신은 새로운 가장자리 ab에 넣는 경우 중 하나

(1) 대칭 인접 목록을 사용, 즉, adjlist[a]및에 b를 추가해야한다는 것입니다 그 반대의 경우도 마찬가지

또는

는

(2) 모든 정점 '인접리스트는 가장자리의 존재를 찾고있는 전자 everytim 통과.

(2)가 끔찍하게 비효율적이므로 대개 (1)을 사용합니다. 이것은 또한 일반적으로 사용되는 adj 목록에 대한 규칙입니다. 내가 adj 목록으로 제시 되었다면, 그래프가 지시되었다고 가정 할 수 있습니다.

Answer 2

인접 목록 표현을 변경할 수 있으며 표현은 '지시'이지만 사진은 전달되지 않습니다.