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.

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 A^T , then for undirected graph G as above, A = A^T.

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

Ask an Expert

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

Write your message here..

Related Questions

Define the term - array, Define the term - Array A fixed length, ord... 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.

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

Algorithm for insertion into the circular queue, Algorithm for insertion of... 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 from a red-black tree, Deletion in a RBT uses two main processes, ... 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

Deletion of a node from an avl tree, For AVL trees the deletion algorithm i... 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

Operations on sequential files, Insertion: Records has to be inserted at t... 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 ancestor, How many nodes in a tree have no... How many nodes in a tree have no ancestors 1 node in atree have no ancestors.

Define container in terms of object-oriented terms, Define container in te... 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, System defined data types:- These are data t... 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

Total impedent of the circuit, an electrical student designed a circuit in... 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