Any language just specify which Thank you and will thumb up

Any language, just specify which. Thank you and will thumb up!

A graph is specified as follows. First ask the user to input a number n. This is the number of vertices - the vertices are numbered 1, 2, ..., n. Now, ask the user the enter the number m - this is the number of edges. Now ask the user to enter the edge data, m times. For example you can ask the user to enter one endpoint, followed by the question to enter the second endpoint. For example the user could enter n = 4, m = 3 and the edges as between (1, 3), (2, 3), (4, 3). Once this is done, output the following: Output the adjacency list representation of the graph in the format, v: v_1 v_2 ... v_k one per line for each vertex v. For example from the graph above the output will be: Output the adjacency matrix representation of the graph as a matrix of 0\'s and l\'s where row i corresponds to vertex i and column i also corresponds to vertex i. For example, for the graph above your code should output: 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 Count the number of triangles in G. A triangle is a set of 3 vertices which are all adjacent to each other. For example, for the graph above the answer should be 0. Make your algorithm as fast as possible - give an estimate of its running time as a function of n, m (or other parameters of the graph): you may output this as a final sentence after your answer. For example you could answer: The graph has 0 triangles The running time is 0 (n * n)

Solution

nober of traingles given adjacency matrix is tr(A3)/6

hence complexity cannot be reduced to n^2

import java.util.Scanner;

public class graphs {

   public static void main(String[] args) {

       Scanner in = new Scanner(System.in);

       System.out.println(\"Enter vertices\");

       int v = in.nextInt();

       System.out.println(\"Enter no of edges\");

       int e = in.nextInt();

       int[][] graph = new int[v][v];

       // input for edges

       for (int i = 0; i < e; i++) {

           System.out.println(\"Enter 1st vertex for \" + (i + 1) + \" edge\");

           int f = in.nextInt();

           System.out.println(\"Enter 2nd vertex for \" + (i + 1) + \" edge\");

           int s = in.nextInt();

           graph[f - 1][s - 1] = 1;

           graph[s - 1][f - 1] = 1;

       }

       print(graph, v);

       printadjacency(graph, v);

       System.out.println(\"The graph has \"+triangleInGraph(graph,v)+\" triangles\");

   }

   static void print(int[][] a, int r) {

       for (int i = 0; i < r; i++) {

           {

               System.out.print((i + 1) + \":\\t\");

               for (int j = 0; j < r; j++) {

                   if (a[i][j] == 1)

                       System.out.print((j + 1) + \"\\t\");

               }

               System.out.println();

           }

       }

   }

   static void printadjacency(int[][] a, int r) {

       for (int i = 0; i < r; i++) {

           for (int j = 0; j < r; j++)

               System.out.print(a[i][j] + \"\\t\");

           System.out.println();

       }

   }

   // Utility function for calculating number of triangles in graph

   public static int triangleInGraph(int graph[][], int v) {

       // To Store graph^2

       int[][] aux2 = new int[v][v];

       // To Store graph^3

       int[][] aux3 = new int[v][v];

       //

       // // Initialising aux matrices with 0

       // for (int i = 0; i < V; ++i)

       // for (int j = 0; j < V; ++j)

       // aux2[i][j] = aux3[i][j] = 0;

       // aux2 is graph^2 now printMatrix(aux2);

       multiply(graph, graph, aux2, v);

       // after this multiplication aux3 is

       // graph^3 printMatrix(aux3);

       multiply(graph, aux2, aux3, v);

       int trace = getTrace(aux3, v);

       return trace / 6;

   }

   static int getTrace(int graph[][], int v) {

       int trace = 0;

       for (int i = 0; i < v; i++)

           trace += graph[i][i];

       return trace;

   }

   // Utility function for matrix multiplication

   static void multiply(int A[][], int B[][], int C[][], int v) {

       for (int i = 0; i < v; i++) {

           for (int j = 0; j < v; j++) {

               C[i][j] = 0;

               for (int k = 0; k < v; k++)

                   C[i][j] += A[i][k] * B[k][j];

           }

       }

   }

}