如何在线性时间内反转图形？

Question

我知道有两种表示图形的方法:一种是使用矩阵,另一种是使用列表.

如果我使用矩阵,我必须翻转矩阵中的所有位.这不是需要O(V ^ 2)时间吗？

如果我使用列表,我不是必须逐个遍历每个列表,并创建一个新集合吗？这似乎需要O(V + E)时间是线性的.我对么？

所以,我在这里有另一个问题.例如,考虑我在我的图形上使用Dijkstra算法(矩阵或列表),并且我们使用优先级队列作为场景后面的数据结构.图表表示与数据结构的使用有关系吗？它会影响算法的性能吗？

假设我使用Dijkstra算法的表示和优先级队列列表,Dijkstra的矩阵和使用优先级队列之间会有区别吗？

我想makeQueue这只与手术有关？或者他们没有什么不同？

Answer 1

反转有向图的邻接列表可以在线性时间内完成.我们只遍历图表一次.复杂度的顺序为O(| V | + | E |).

1. 维护Adjaceny Lists的HashMap,其中键是顶点标签,值是键顶点的相邻顶点的ArrayList.
2. 对于反转,创建一个相同类型的新HashMap.扫描原始哈希映射,并为您遇到的每个密钥遍历相应的列表.
3. 对于值列表中找到的每个顶点,在新的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;
}