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

Representation of a polynomial with a singly linked list, List areutilized ... List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4   - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

Write an algorithm of value in tax using pseudocode, A town contains a tota... A town contains a total of 5000 houses. Every house owner has to pay tax based on value of the house. Houses over $200 000 pay 2% of their value in tax, houses over $100 000 pay 1.

Define rule-based expert system, 1. Define the following terms in a rule-ba... 1. Define the following terms in a rule-based expert system? a) Knowledge base b) Inference engine 2. What is a fuzzy rule? Explain the difference between classical and fuzzy

Circular queue, explain implementation of circular queue insert,delete oper... explain implementation of circular queue insert,delete operations

State flowchart that take temperature input using pseudocode, Write an algo... Write an algorithm using pseudocode which takes temperatures input over a 100 day period (once per day) and output the number of days when the temperature was below 20C and the num

Algorithm of binary search, Step 1: Declare array 'k' of size 'n' i.e. k(n)... Step 1: Declare array 'k' of size 'n' i.e. k(n) is an array which stores all the keys of a file containing 'n' records Step 2: i←0 Step 3: low←0, high←n-1 Step 4: while (l

Multiplication, Implement multiple stacks in a single dimensional array. Wr... Implement multiple stacks in a single dimensional array. Write algorithms for various stack operations for them.

Linked lists, algorithms algorithms

Discrete time simulation of a queue, In this project you will write a progr... In this project you will write a program to produce a discrete time simulation of a queue as shown in Fig. 1. Time is slotted on the input and the output. Each input packet follows

Graph, adjacency multilist adjacency multilist