CODEWITHSUNDEEP
javaadjacency-list
Jw123
Jw123

Reputation: 57

Java implementation of adjacency list

I have a n*m matrix with integer value at each node and its an undirected graph. I want to build an adjacency list for it. How do I do that? Any help is much appreciated.

Upvotes: 2

Views: 29836

Answers (2)

Sumeet
Sumeet

Reputation: 8292

Here is a simple implementation for creating adjacency list.According to the problem:

There will be n linked lists each of variable size.

First Initialize an ArrayList of linked lists of integers:

ArrayList<LinkedList<Integer>> adj_list = new ArrayList<LinkedList<Integer>>();

Then simply add linked lists by repeating following code:

adj_list.add(new LinkedList<Integer>());

If you are using it to represent graph,then no of linked lists=no of vertices.So you must repeat the above line n(no of vertices) times.

Say now you want to add numbers 3,4,5 to your first linked lists.Do the following:

adj_list.get(0).add(3);
adj_list.get(0).add(4);
adj_list.get(0).add(5);

It simply means there is an edge in your graph from vertex 0 to 3,4,5.

Upvotes: 3

Gene
Gene

Reputation: 47020

First your description seems to be of an adjacency matrix except you're saying m by n. Adjacency matrices are always square, so we must assume m==n. The matrix elements are the edge weights.

An adjacency list representation of a graph is (usually) an array adj of sets of pairs. The set adj[i] contains pair <j, w> iff there is a directed edge i--w-->j, i.e. from vertex i to j with weight w in the represented graph.

With this definition, it's clear you must start with n empty adjacency sets adj[i] and then iterate over the matrix elements m[i][j] = w. For each of these add <j, w> to adj[i].

The java code for this is pretty trivial, so I won't write it. The type for a graph represented with adjacency lists is something like ArrayList<HashMap<Integer, Integer>> adjacencies. The pairs <j,w> in adj[i] are mappings j -> w stored in the hash table adjacencies.get(i). The code to create such an adjacency will be adjacencies.get(i).put(j, w).

This method allows you to iterate over the vertices adjacent to i by iterating over keys in the hash table adjacencies.get(i), look up the weight of a given edge i--w-->j with w = adjacencies.get(i).get(j), and so on for all the usual graph operations.

Upvotes: 2

Related Questions