Question

Java Implementation

It uses adjacency list representation, and already has the loadAdjList() function implemented for reading adjacency lists from standard input (make sure you understand the input format and how loadAdjList() works). You need to complete the function printAdjMatrix().

import java.util.LinkedList;
	import java.util.Scanner;
	import java.util.Iterator;
	class Graph {
	private int totalVertex;
	private LinkedList<LinkedList<Integer>> adjList;
	//adjacency list of edges
	public Graph() { totalVertex = 0; }
	public void loadAdjList() {
	Scanner in = new Scanner(System.in);
	totalVertex = in.nextInt();
	adjList = new LinkedList<LinkedList<Integer>>();
	for(int i = 0; i < totalVertex; i ++) {
	LinkedList<Integer> tmp = new LinkedList<Integer>();
	int idx1 = in.nextInt() - 1;
	int degree = in.nextInt();
	//System.out.println("mark idx1 = " + idx1 + " degree = " + degree);
	for(int j = 0; j < degree; j ++) {
	int idx2 = in.nextInt() - 1;
	tmp.add(idx2);
	}
	adjList.add(tmp);
	}
	in.close();
	}
	public void printAdjMatrix() {
	Integer[][] adjMatrix = new Integer[totalVertex][totalVertex];
	//complete the following
	}
	}
	//change class name GraphRepresentation to Main() for submission to AIZU
	public class GraphRepresentation {
	public static void main(String argv[]) {
	Graph g = new Graph();
	g.loadAdjList();
	g.printAdjMatrix();
	}
	}

Answer 1

first of all lets in brief discuss about adjacency list and adjacency matrix representation of a graph..

adjacency list representation is : an array/ linked list of linked lists which stores for every vertex in the graph in the graph we store it's neighbouring vertices ( current vertex and neighbouring vertex are connected by an edge)

that is each vertex gets its own linked list in which all the neighbouring vertices are stored..

for a graph with n vertices we will have n separate linked lists which will be joined by a single linked list / single array

adjacency matrix representation : if there are n vertices then we will have a n * n matrix adjMatrix in which if there is an edge from i->j then adjMatrix[i][j] = 1 else if there is no edge from i to j then adjMatrix[i][j] = 0]

in case of undirected graph : edges are bidirectional i.e., if i is a neighbour to j then j is also a neighbour of i, it was not mentioned here so we will be taking an directed graph i.e., if i is a neighbour to j then it does not imply j is also a neighbour of i.

a sample illustartion :

suppose if our graph is like this then the corresponding adjacency list and adjacency matrix will be like this :

after getting an idea about them we can solve this question : what we have to do :

1understanding the working of loadAdjList function given , which is used to create the adjacency list of the graph

2 we should complete a function printAdjMatrix , which given an adjacency list prints the adjacency matrix of the adjacency list

1. here's what the function is doing .. initially we have no graph,

that's why we will initialise an empty linkedList of (linkedList of (nodes) )

* ask the user enter no of vertices in our graph -  totalVertex

*for each vertex i ask the no of neighbouring vertices of this vertex i - degree

* now initialise an empty LinkedList of integers - tmp

* ask the user to enter neighbouring vertices of this graph one by one they should be a total of degree number of vertices

* add each neighbouring vertex to our current vertex LinkedList tmp

* after adding each vertex into tmp LinkedList we will have our current vertex i's corresponding linkedList of nodes

* now we should add this tmp LinkedList(nodes) to our adjList (LinkedList)

* after doing this for every vertex i>=0 and i <totalVertex we will have our final adjacency list in adjList.

i have included some comments and print statements to make the code and input more clear :

public void loadAdjList(){

Scanner in = new Scanner(System.in);

System.out.println("enter total no of vertices in graph\n");

totalVertex = in.nextInt();

adjList = new LinkedList<LinkedList<Integer>>(); //initialising adjList data member

                                                // linked list of totalVertex no of linked lists

                                                // each linked list is for each vertex

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

LinkedList<Integer> tmp = new LinkedList<Integer>(); // for each vertex a linked list

System.out.println("enter the to node number : "+ (i+1));

int idx1 = in.nextInt() - 1;

// if we are treating it as a zeros based naming like first node if 0

System.out.println("enter no nodes connected to node : "+ (i+1));

int degree = in.nextInt();   // no of connections/outward- edges this node has

System.out.println("mark idx1 = " + idx1 + " degree = " + degree);

System.out.println("enter "+  degree +" no nodes connected to this node : ");

for(int j = 0; j < degree; j ++) { // for each connection/edge

int idx2 = in.nextInt() - 1; // we are getting each node other side of the connection

tmp.add(idx2); // we are adding each node connected to our current node i to the linked list tmp

}

adjList.add(tmp); // as tmp is contains our linked list of vertices connected to our current node i

                // we will add it to our adjacency list..

                // here we are adding the linked list tmp to adjacency list adjList

}

in.close(); //closing the input scanner

}

input format :

no_of vertices in the graph n

for each vertex it will ask the number of its vertex ( the user views the starting the vertex as 1 ans in the code it will be 0)

degree of each vertex d

d no of vertices connected to current vertex ..

sample input for the graph in above explanation after adding useful comments:

enter total no of vertices in graph
6
enter the node number : 1
1
enter no nodes connected to node : 1
2
mark idx1 = 0 degree = 2
enter 2 no nodes connected to this node :
2 3
enter the node number : 2
2
enter no nodes connected to node : 2
2
mark idx1 = 1 degree = 2
enter 2 no nodes connected to this node :
3 4
enter the node number : 3
3
enter no nodes connected to node : 3
1
mark idx1 = 2 degree = 1
enter 1 no nodes connected to this node :
5
enter the node number : 4
4
enter no nodes connected to node : 4
2
mark idx1 = 3 degree = 2
enter 2 no nodes connected to this node :
2 5
enter the node number : 5
5
enter no nodes connected to node : 5
3
mark idx1 = 4 degree = 3
enter 3 no nodes connected to this node :
6 4 3
enter the node number : 6
6
enter no nodes connected to node : 6
1
mark idx1 = 5 degree = 1
enter 1 no nodes connected to this node :
3

now printing adjacency matrix..

*first we will initialise an matrix adjMatrix[totalVertex][totalVertex] and keep all 0<= i , j < totalVertex ; adjMatrix[i][j] = 0

then for each linked list of nodes in our adjList - tmp

for each node in tmp - neighbour

adjMatrix[ current vertex] [neighbour] = 1

then later print the whole matrix.

public void printAdjMatrix() {

Integer[][] adjMatrix = new Integer[totalVertex][totalVertex];

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

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

        adjMatrix[i][j] = 0; // initialise all adjMatrix[i][j] = 0

LinkedList<Integer> tmp ; // linked list of nodes

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

    tmp = adjList.get(i); // linked list of each node for i =0 to i<totalVertex

    for(int node :tmp ){

        adjMatrix[i][node] = 1;

    }

}

System.out.println("the adjacency matrix for the graph is ");

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

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

        System.out.print(adjMatrix[i][j]+ " "); // printing the whole matrix

    }

    System.out.print("\n");

}

}

output for sample graph given above :

the adjacency matrix for the graph is

0 1 1 0 0 0
0 0 1 1 0 0
0 0 0 0 1 0
0 1 0 0 1 0
0 0 1 1 0 1
0 0 1 0 0 0

please provide your valuable feedback.