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

Write a procedure that produces independent stack, Write a procedure (make-...

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g. (define stack1 (make-stack))  (define stack2 (make-stack)) W

Illustrate an example of algorithm, Illustrate an example of algorithm ...

Illustrate an example of algorithm Consider that an algorithm is a sequence of steps, not a program. You might use the same algorithm in different programs, or express same alg

Progrrame, how to write a code for for a company , for calculate the salary...

how to write a code for for a company , for calculate the salary pay

Abstract data type- queue, A significant aspect of Abstract Data Types is t...

A significant aspect of Abstract Data Types is that they explain the properties of a data structure without specifying the details of its implementation. The properties might be im

Insertion sort, Data array A has data series from 1,000,000 to 1 with step ...

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Sequential files, In this section, we will discuss about Sequential file or...

In this section, we will discuss about Sequential file organization. Sequential files have data records stored in a particular sequence. A sequentially organized file might be stor

Algorithm, Example of worse case of time

Example of worse case of time

Array implementation of lists, In the array implementation of the lists, we...

In the array implementation of the lists, we will use the array to hold the entries and a separate counter to keep track of the number of positions are occupied. A structure will b

Procedures, what is far and near procedures in system programming?

what is far and near procedures in system programming?

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