How to reverse a graph in linear time?

Question

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?

Answer 1

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