선형 시간에 그래프를 뒤집는 방법은 무엇입니까?

그래프를 표현하는 두 가지 방법이 있습니다 : 하나는 매트릭스를 사용하고 다른 하나는리스트를 사용하는 것입니다.선형 시간에 그래프를 뒤집는 방법은 무엇입니까?

행렬을 사용하는 경우 행렬의 모든 비트를 뒤집어 써야합니다. 그게 O (V^2) 시간 걸리지 않니?

목록을 사용하는 경우 각 목록을 하나씩 트래버스하고 새 세트를 만들지 않아도됩니까? 그것은 선형 인 O (V + E) 시간이 걸릴 것으로 보입니다. 나 맞아?

그래서 여기에 또 다른 질문이 있습니다. 예를 들어, 그래프 (매트릭스 또는 목록)에 Dijkstra 알고리즘을 사용하고 장면 뒤의 데이터 구조에 우선 순위 큐를 사용한다고 가정합니다. 그래프 표현과 데이터 구조의 관계가 있습니까? 알고리즘의 성능에 영향을 미칩니 까?

Dijkstra 알고리즘의 표현과 우선 순위 대기열에 목록을 사용한다고 가정하면 Dijkstra의 행렬과 사용 우선 순위 대기열간에 차이가 있습니까?

나는 makeQueue 수술과 관련이 있다고 생각하십니까? 아니면 그들은 전혀 다르지 않습니까?

출처

2013-04-23 Timothy Leung

는 E = O (V^2)와 같은 일반 선형 시간에 발생하지 않습니다. – collapsar

@ collapsar * * 항상 * 정점 * 및 모서리와 관련하여 선형 시간으로 발생합니다. 시간이 입력의 다른 부분과 직접적으로 관련되어있을 때 (특히 정점) (명시 적으로 언급하지 않고) 입력의 일부에만 시간 복잡성을 정의하는 것은 다소 비논리적 인 것처럼 보입니다 (그러나 나는 많은 것을 주장 할 수 없습니다. 사람들은 당신이 그랬던 것처럼 그것을 정의 할 수 있습니다.) 그리고 E = O (V^2)는 밀도가 높은 그래프입니다. 스파 스 그래프는 E = O (V)입니다. – Dukeling

@dukeling 문제의 '크기'를 단일 스칼라로 줄이면 정밀도가 떨어지는 것을 지적하는 것이 옳습니다. otoh, big-Oh 표기법은 최악의 경우를 설명하고 그래프를 고려하면 추가 제약없이 최악의 경우는 E = O (V^2)를 의미합니다. O (V^2)는 인접 행렬의 에지 역전에 대해서도 올바르지 않다. - 표현이 플래그 행 - 전공 대 전공 - 전공을 자랑한다면, 전치는 O (1)이다. – collapsar

선형화 그래프의 인접성 목록을 역전시키는 것은 선형 시간으로 수행 할 수 있습니다. 그래프를 한 번만 트래버스합니다. 복잡도의 순서는 O (| V | + | E |)가됩니다.

키가 정점 레이블이고 값이 키 정점의 인접한 정점의 ArrayList 인 Adjaceny List의 HashMap을 유지 관리합니다.
반대의 경우, 같은 종류의 새로운 HashMap을 작성하십시오. 원래 해시 맵을 스캔하고 각 키에 대해 해당 목록을 탐색합니다.
값 목록에있는 각 정점에 대해 새 HashMap에 키를 추가하여 원래 HashMap의 키를 새 HashMap의 새 키에 해당하는 ArrayList의 항목으로 만듭니다. 순회 인접리스트의

public static HashMap<Character,ArrayList <Character>> getReversedAdjLists(RGraph g) 
{ 
    HashMap <Character, ArrayList<Character>> revAdjListMap = new HashMap <Character, ArrayList<Character>>(); 
    Set <Character> oldLabelSet = g.adjListMap.keySet(); 

    for(char oldLabel:oldLabelSet) 
    { 
     ArrayList<Character> oldLabelList = g.adjListMap.get(oldLabel); 

     for (char newLabel : oldLabelList) 
     { 
      ArrayList<Character> newLabelList = revAdjListMap.get(newLabel); 

      if (newLabelList == null) 
      { 
       newLabelList = new ArrayList<Character>(); 
       newLabelList.add(oldLabel); 
      } 
      else if (! newLabelList.contains(oldLabel)) 
      { 
       newLabelList.add(oldLabel); 
      } 

      revAdjListMap.put(newLabel, newLabelList); 
     } 
    } 

    return revAdjListMap; 
}

출처

2013-07-06 02:46:52 Rama

좋은 답변입니다. 나는 처음에 정적 인 2D 배열을 사용하여이 작업을 수행하려고했지만 역전을 수행하기 위해 해당 행렬의 전 환은 O (n^2)입니다. 나는 꽤 확신합니다. – scottyseus

각 버텍스에 대해 (V-1) 개의 가장자리를 추가하거나 삭제해야하므로 목록을 탐색하여 그래프를 뒤집는 것이 O (V)라고 생각합니다.

Dijkstra의 알고리즘에 대해서는 이해할 수있는 것처럼 그래프를 행렬 또는 목록으로 표현하면 알고리즘은 O (V)가되지만 일부 다른 데이터 구조는 빠릅니다. 가장 빠른 것으로 알려진 피보나치 힙은 O (E + VlogV)를 제공합니다.

출처

2013-04-23 01:35:59 Beta

두 목록을 보관하는 것은 어떻습니까? 들어오는 가장자리 목록과 나가는 가장자리 목록은 좋은 생각 인 것 같습니다. –

@TimothyLeung : 왜? 하나의 나가는 가장자리에 대해 어떤 이점이 있는지를 나는 알지 못한다. – Beta

@ 베타 그래프가 밀집된 경우에만 O (V^2)가 될 것이라고 상상합니다. 가장자리가없는 것으로 간주하십시오. 모든 정점에서 O (1) 작업 만하므로 O (V)를 수행합니다. 따라서 복잡성에서 가장자리가 작용해야합니다. – Dukeling

선형 시간에 그래프를 뒤집는 방법은 무엇입니까?

답변

관련 문제