인접 목록 목록 표현에서 중복 버텍스 및 자체 루프를 제거하는 그래프 알고리즘

Question

directed multigraph의 인접성 목록 표현에 O (V + E) 알고리즘이있어 방향이없는 단순 그래프로 변환 할 수 있습니까? 알고리즘은 최소한의 공간 만 사용해야합니다.

Answer 1

[EDIT 2013년 6월 5일 : 치료 [η] 일관 2D 배열한다.]

예, 나열된 각 인접 내의 버텍스가 정렬 된 순서에있는 많아야 하나 개의 에지가 제공 될 수있다 한 쌍의 꼭지점 사이. 나는 [I] [J]는 정점의 j 번째 아이를 가정 :이 시점에서

# First make sure each edge appears only in the lower endpoint's adjacency list. 
# We don't care if this duplicates vertices in a list. 
For each vertex i: 
    j = 1 
    For each k from 1 to len(a[i]): 
     a[i][j] = a[i][k] 
     If a[i][k] > i: 
      j = j + 1  # Only save space for edges to higher vertices 

     If a[i][k] < i: 
      Append i to a[a[i][k]] 

    Adjust len(a[i]) to j - 1 

, 모든 인접 목록은 대부분이 개 정렬 된 서브 시퀀스로 구성 - 어떤 높은 정점 자식 정점의 원래 목록 (제거 될 수 있습니다), 상위 꼭지점의 인접 목록에 추가 된 상위 꼭지점 목록이 뒤를 잇을 수 있습니다. 두 번째 시퀀스의 시작은 이전 요소보다 작은 첫 번째 요소를 찾아서 선형 시간으로 찾을 수 있습니다. 발견되면 두 개의 서브 시퀀스를 같은 크기의 버퍼를 사용하여 선형 시간으로 병합 할 수 있습니다 (또는 여분의 공간을 사용하지 않고 로그 선형 시간으로 정렬하거나 버킷 정렬 및 대수 여분 공간을 사용하여 선형 시간으로 정렬). 이웃이 두 번 이상 나타날 수 없으며 병합 중에 병합 된 항목을 제거 할 수 있습니다.