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

Determine the warnock algorithm, Warnock's Algorithm A divide and conqu...

Warnock's Algorithm A divide and conquer algorithm Warnock (PolyList PL, ViewPort VP) If (PL simple in VP) then Draw PL in VP, else Split VP vertically and horiz

Determine the importance of array, Determine the importance of array Ar...

Determine the importance of array Arrays are significant since they allow many values to be stored in a single data structure whereas providing very fast access to each value.

The search trees are abstract data types, the above title please send give ...

the above title please send give for the pdf file and word file

If a node having two children is deleted from a binary tree, If a node havi...

If a node having two children is deleted from a binary tree, it is replaced by?? Inorder successor

Write an algorithm to find outputs number of cars, A company is carrying ou...

A company is carrying out a survey by observing traffic at a road junction. Every time a car, bus or lorry passed by road junction it was noted down. 10 000 vehicles were counted d

Data type, Q. Define the terms data type and abstract data type. Comment up...

Q. Define the terms data type and abstract data type. Comment upon the significance of both these.   Ans: We determine the total amount of memory to reserve by determining

Explain the prim''s minimum spanning tree algorithm, Question 1. Explai...

Question 1. Explain the different types of traversal on binary tree 2. Explain the Prim's minimum spanning tree algorithm 3. Differentiate fixed and variable storage allo

What are the specific needs for realism, Normal 0 false false...

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Methods of physically storing data in the files, This unit dealt along with...

This unit dealt along with the methods of physically storing data in the files. The terms fields, records & files were described. The organization types were introduced. The sev

Algorithm, algorithm to search a node in linked list

algorithm to search a node in linked list

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