如何在线性时间内反转图形？ [英] How to reverse a graph in linear time?

问题描述

我知道有两种方式来表示我的图：一种是使用矩阵，另一种是使用列表。

如果我使用矩阵，我必须翻转矩阵中的所有位。这不需要O（V ^ 2）时间吗？

如果我使用一个列表，我不必逐一遍历每个列表，并创建一套新的？这似乎需要O（V + E）时间，这是线性的。我是否正确？

所以，我在这里得到了另一个问题。例如，考虑在图上使用Dijkstra算法（矩阵或列表），并且我们使用优先级队列来处理场景后面的数据结构。图表表示与数据结构的使用有任何关系吗？它会影响算法的性能吗？

假设我将为Dijkstra算法使用一个表示和一个优先级队列，那么矩阵和使用Dijkstra的优先级队列？

我猜它只涉及 makeQueue 操作吗？或者它们没有什么不同？

解决方案

可以在线性时间内完成有向​​图的邻接表逆转。我们只遍历图表一次。复杂度的顺序是O（| V | + | E |）。

1. 维护Adjaceny的HashMap列表，其中键是顶点标签，并且该值是关键顶点相邻顶点的ArrayList。
   
2. 对于反转，创建一个新的相同类型的HashMap。扫描原始哈希映射和您遇到的每个密钥，遍历相应的列表。


3. 对于在值列表中找到的每个顶点，在新的哈希映射中添加一个密钥，原始HashMap作为ArrayList中与新HashMap中的新键相对应的条目。
   

  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（）; （char oldLabel：oldLabelSet）
 
 
 {
 ArrayList< Character> oldLabelList = g.adjListMap.get（oldLabel）; （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; 
} 
  

I know there are two ways to represent my graph: one is using a matrix, and the other one is using a list.

If I use a matrix, I have to flip all the bits in the matrix. Doesn't that take O(V^2) time?

If I use a list, wouldn't I have to traverse each list, one by one, and create a new set? That would seem to take O(V+E) time which is linear. Am I correct?

So, I got another question here. Consider, for example, that I use the Dijkstra algorithm on my graph (either a matrix or a list), and we use a priority queue for the data structure behind the scene. Is there any relation of graph representation and the use of data structure? Will it affect the performance of the algorithm?

Suppose I were to use a list for representations and a priority queue for the Dijkstra algorithm, would there be a difference between matrix and use priority queue for Dijkstra?

I guess it relates to makeQueue operation only? Or they don't have different at all?

解决方案

Reversing the adjacency lists of a Directed Graph can be done in linear time. We traverse the graph only once. Order of complexity will be O(|V|+|E|).

1. Maintain a HashMap of Adjaceny Lists where the key is the vertex label and the value is an ArrayList of adjacent vertices of the key vertex.
2. For reversing, create a new HashMap of the same kind. Scan the original hash map and for each key you come across, traverse the corresponding list.
3. For each vertex found in the value list, add a key in the new hashMap, putting the key of the original HashMap as an entry in the ArrayList corresponding to the new key in the new HashMap.

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;
}

这篇关于如何在线性时间内反转图形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！