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
Define the term - Array A fixed length, ordered collection of values of same type stored in contiguous memory locations; collection may be ordered in several dimensions.

With the help of a program and a numerical example explain the Depth First Traversal of a tree.

Algorithm for insertion of any element into the circular queue: Step-1: If "rear" of the queue is pointing at the last position then go to step-2 or else Step-3 Step-2: make

Deletion in a RBT uses two main processes, namely, Procedure 1: This is utilized to delete an element in a given Red-Black Tree. It involves the method of deletion utilized in

For AVL trees the deletion algorithm is a little more complicated as there are various extra steps involved in the deletion of node. If the node is not a leaf node, then it contain

Insertion: Records has to be inserted at the place dictated by the sequence of keys. As is obvious, direct insertions into the main data file would lead to frequent rebuilding of

How many nodes in a tree have no ancestors 1 node in atree have no ancestors.

Define container in terms of  object-oriented terms A Container is a broad category whose instances are all more specific things; there is never anything which is just a Contai

System defined data types:- These are data types that have been defined by the compiler of any program. The C language contains 4 basic data types:- Int, float,  char and doubl

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program