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

Two sparce matrices multipilcation algorithm, Write an algorithm for multi...

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Enumerate about the carrier set members, Enumerate about the carrier set me...

Enumerate about the carrier set members Ruby is written in C, so carrier set members (which is, individual symbols) are implemented as fixed-size arrays of characters (which is

find shortest path from a to z using dijkstra''s algorithm., Q.  In the gi...

Q.  In the given figure find the shortest path from A to Z using Dijkstra's Algorithm.    Ans: 1.  P=φ;  T={A,B,C,D,E,F,G,H,I,J,K,L,M,Z} Let L(A)

Insertion of element into a linked list, ALGORITHM (Insertion of element in...

ALGORITHM (Insertion of element into a linked list) Step 1 Begin the program Step 2 if the list is empty or any new element comes before the start (head) element, then add t

Test whether a binary tree is a binary search tree, Q. Write down an algori...

Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

Binary search, In a sorted list, Binary search is carried out by dividing t...

In a sorted list, Binary search is carried out by dividing the list into two parts depends on the comparison of the key. Since the search interval halves each time, the iteration o

Sorting, Retrieval of information is made simpler when it is stored into so...

Retrieval of information is made simpler when it is stored into some predefined order. Therefore, Sorting is a very important computer application activity. Several sorting algorit

Representation of arrays?, A representation of an array structure is a mapp...

A representation of an array structure is a mapping of the (abstract) array with elements of type T onto the store which is an array with elements of type BYTE. The array could be

Doubly linked lists-implementation, In any singly linked list, each of the ...

In any singly linked list, each of the elements contains a pointer to the next element. We have illustrated this before. In single linked list, traversing is probable only in one d

Randomized algorithm, need an expert to help me with the assignment

need an expert to help me with the assignment

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