We again consider directed graphs, also assuming that edges carry a positive \"l

Question

We again consider directed graphs, also assuming that edges carry a positive "length"; this time our goal is to reverse the edges. That is, given a graph (V, E) where the nodes in V are numbered l..n, we want to construct a graph (V, E') such that for all i and k in V, Ef contains an edge with length d from i to k iff E contains an edge with length d from k to i. Your task Is to write pseudo-code to implement this specification, and analyze the algorithm's running time, as a function of n and of a (the number of edges in E). You should do that when the graph is represented as an adjacency matrix A (that is, A(i,k) = d if the graph has an edge from i to k with length d: if there Ls no edge from i to k, A(i,k) = 0) when the graph Ls represented as adjacency lists L (that is, for each i A l..n, L[i] is a list that contains the edges from i, where an edge is a pair (A, d) with k the target and d the length of the edge: you may assume a function Cons that adds an edge to a list of edges.)

Explanation / Answer

1)

Reversing the edges of Directed Graph when it is represented in Adjacency matrix form can be done in     O(|V|*|V|).

It is similar to taking the transpose of Adjacency matrix of the graph. here is the java code

import java.util.Scanner;

public class TransposeOfGraph
{
    private int transposeMatrix[][];
    private int numberOfVertices;

    public TransposeOfGraph(int numberOfVertices)
    {
        this.numberOfVertices = numberOfVertices;
        transposeMatrix = new int[numberOfVertices + 1][numberOfVertices + 1];
    }

    public int[][] transpose(int adjacencyMatrix[][])
    {
        for (int source = 1; source <= numberOfVertices; source++)
        {
            for (int destination = 1; destination <= numberOfVertices; destination++)
            {
                transposeMatrix[source][destination] = adjacencyMatrix[destination][source];
            }
        }
        return transposeMatrix;
    }

    public static void main(String... arg)
    {
        int number_of_nodes;
        Scanner scanner = null;

        System.out.println("Enter the number of nodes in the graph");
        scanner = new Scanner(System.in);
        number_of_nodes = scanner.nextInt();

        int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
        int transpose_matrix[][];
        System.out.println("Enter the adjacency matrix");
        for (int i = 1; i <= number_of_nodes; i++)
            for (int j = 1; j <= number_of_nodes; j++)
                adjacency_matrix[i][j] = scanner.nextInt();

        TransposeOfGraph transposeOfGraph = new TransposeOfGraph(number_of_nodes);
        transpose_matrix = transposeOfGraph.transpose(adjacency_matrix);

        System.out.println("The transpose of the given graph");
        for (int i = 1; i <= number_of_nodes; i++)
            System.out.print(" " + i);

        System.out.println();
        for (int source = 1; source <= number_of_nodes; source++)
        {
            System.out.print(source +" ");
            for (int destination = 1; destination <= number_of_nodes; destination++)
            {
                System.out.print(transpose_matrix[source][destination] + " ");
            }
            System.out.println();
        }
        scanner.close();
    }
}

2)

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

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.