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

A Booth''s, Draw a flowchart of a Booth''s multiplication algorithm and exp...

Draw a flowchart of a Booth''s multiplication algorithm and explain it.

Implementation of stack, Implementation of Stack :- Stacks can be execu...

Implementation of Stack :- Stacks can be executed in the 2 ways: a)  Arrays b)  Linked List

Queues, what is queues? how it work? and why it used? i want an assignment...

what is queues? how it work? and why it used? i want an assignment on queue .....

#title., Ask quapplication of data structure estion #Minimum 100 words acce...

Ask quapplication of data structure estion #Minimum 100 words accepted#

Graphs, floyd warshall algorithm

floyd warshall algorithm

What is an unreachable code assertion, What is an unreachable code assertio...

What is an unreachable code assertion An unreachable code assertion can be placed at the default case; if it's every executed, then program is in an erroneous state. A loop in

Program for linear search, Program for Linear Search. Program: Linear S...

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

State a algorithm that inputs the heights of all 500 student, As part of an...

As part of an experiment, a school measured heights (in metres) of all its 500 students. Write an algorithm, using a flowchart that inputs the heights of all 500 students and ou

Sorting, Define Hashing. Store the following values in a hash table of tabl...

Define Hashing. Store the following values in a hash table of table size 11 using division method: 25, 42, 96, 101, 102, 162, and 197. In case of collision, use other hash functio

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