Adjacency list representation, Data Structure & Algorithms

Adjacency list representation

An Adjacency list representation of Graph G = {V, E} contains an array of adjacency lists mentioned by adj of V list. For each of the vertex u?V, adj[u] contains all vertices adjacent to u in the graph G.

Consider the graph of Figure.

636_Adjacency list representation.png

Figure: A Graph

Given is the adjacency list representation of graph of above Figure:

adj [1] = {2, 3, 5}

adj [2] = {1, 4}

adj [3] = {1, 4, 5}

adj [4] = {2, 3, 5}

 adj [5] = {1, 3, 4}

An adjacency matrix representation of a Graph G=(V, E) is a matrix

The adjacency matrix for the graph of Figure is following:

 

1

2

3

4

5

1

0

1

1

0

1

 

2

 

1

 

0

 

0

 

1

 

1

 

3

 

1

 

0

 

0

 

1

 

1

 

4

 

0

 

1

 

1

 

0

 

1

 

5

 

1

 

0

 

1

 

1

 

0

 

 

 

 

 

 

Observe that the matrix is symmetric along the main diagonal. If we described the adjacency matrix as A and the transpose as AT , then for undirected graph G as above, A = AT.

Posted Date: 4/11/2013 3:46:05 AM | Location : United States







Related Discussions:- Adjacency list representation, Assignment Help, Ask Question on Adjacency list representation, Get Answer, Expert's Help, Adjacency list representation Discussions

Write discussion on Adjacency list representation
Your posts are moderated
Related Questions
ST AC K is explained as follows : A stack is one of the most usually used data structure. A stack is also called a Last-In-First-Out (LIFO) system, is a linear list in

Worst Case: For running time, Worst case running time is an upper bound with any input. This guarantees that, irrespective of the type of input, the algorithm will not take any lo

Comparison of Gouraud and Phong Shading Phong shading requires more calculations, but produces better results for specular reflection than Gouraud shading in the form of more r

1. In computer science, a classic problem is how to dynamically store information so as to let for quick look up. This searching problem arises frequently in dictionaries, symbol t

Importance of Object-Oriented over java Java is basically based on OOP notions of classes and objects. Java uses a formal OOP type system that should be obeyed at compile-t

Write the algorithm for compound interest

Q. Write down an algorithm to delete the specific node from binary search tree. Trace the algorithm to delete a node (10) from the following given tree. Ans. Algor

You will write functions for both addition and subtraction of two numbers encoded in your data structure. These functions should not be hard to write. Remember how you add and subt

Compare zero-address, one-address, two-address, and three-address machines by writing programs to compute: Y = (A – B X C) / (D + E X F) for each of the four machines. The inst

basic calculation for algorith.