Adjacency list representation, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Adjacency list representation

Proof, prove that n/100=omega(n)

prove that n/100=omega(n)

Linked list implementation of a queue, The fundamental element of linked li...

The fundamental element of linked list is a "record" structure of at least two fields. The object which holds the data & refers to the next element into the list is called a node .

Stack making use of the linked list, Q. Implement a stack making use of the...

Q. Implement a stack making use of the linked list. Show the PUSH and POP operations both. A n s . Stack implemantation using linked list # include # include

Write an algorithm to illustrate this repeated calculation, The below formu...

The below formula is used to calculate n: n = (x * x)/ (1 - x). Value x = 0 is used to stop the algorithm. Calculation is repeated using values of x until value x = 0 is input. The

Insert function, INSERT FUNCTION /*prototypes of insert & find function...

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

Algorithm to merge the lists together, Q. Let X = (X1, X2, X3,....Xn) and Y...

Q. Let X = (X1, X2, X3,....Xn) and Y= (Y1, Y2, Y3,....Xm) be the two linked lists respectively. Write down an algorithm to merge the lists together to get the linked list Z such th

Sparse matrices, SPARSE MATRICES Matrices along with good number of zer...

SPARSE MATRICES Matrices along with good number of zero entries are called sparse matrices. Refer the following matrices of Figure (a)

Explain class p problems, Explain class P problems Class  P  is  a  cla...

Explain class P problems Class  P  is  a  class  of  decision  problems  that  can  be  solved  in  polynomial time  by(deterministic) algorithms. This class of problems is kno

Compare two functions, Comp are two functions n 2    and  2 n  / 4...

Comp are two functions n 2    and  2 n  / 4  for distinct values of n.   Determine When s ec on d function b ec om es l a r g er th an f i r st functi

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd