Hash function, sparse matrix, reachability index, Data Structure & Algorithms

Assignment Help:

Q. Define the graph, adjacency matrix, adjacency list, hash function, adjacency matrix, sparse matrix, reachability matrix.                                                                                                               

Ans.

Graph is explained below

A graph G, comprises of 2 sets V & E. V is a finite non-empty set of vertices. E is a set of pairs of vertices, these pairs are known as edges.

Adjacent Matrix can be defined as follows:-

Let G=(V,E) be graph with n vertices, n>=1.

In The Adjacency Matrix of G is a 2- dimensional which are n*n array , say A, with the property that A(i,j) = 1 iff the edge (vi,vj) ( < vi, vj> for the directed graph) is in E(G). A(i,j)= 0 if there is no edge in G.

Adjacency Lists can be defined as follows

In this type of representation the n rows of the adjacency matrix are represented as n linked list. There is only one list for each vertex in G. The nodes in list signifies the vertices that are neighbouring from vertex i.

Hash Function is described below

A hash function h is simply a mathematical formula which manipulates the key in

some form to compute or calculate the index for this key in the hash table Commonly, we say that a hash function h maps the universe U of keys into the slots of a hash table T[0....n-1]. This process of mapping keys to appropriate slots in a hash table is called hashing.

Sparse Matrix is described below

A m x n matrix A is called to be sparse if and only if  most of its elements are zero. A matrix which is not sparse is known as the dense matrix. for example:

1739_sparse matrix.png 

Reachability Matrix /Path Matrix is described below:-

Let G be a easy directed graph with m nodes, V1, V2, V3........Vm. The reachability matrix of G is the m -square matrix P=(Pij) explained below

362_sparse matrix1.png 


Related Discussions:- Hash function, sparse matrix, reachability index

Difference between prism''s and kruskal''s algorithm, Difference among Pris...

Difference among Prism's and Kruskal's Algorithm In Kruskal's algorithm, the set A is a forest. The safe edge added to A is always a least-weight edge in the paragraph that lin

..#title, whate is meant by the term heuristic

whate is meant by the term heuristic

Analysis of algorithms, A common person's faith is that a computer can do a...

A common person's faith is that a computer can do anything. It is far from truth. In realism computer can carry out only definite predefined instructions. The formal illustration o

Simulation of queues, Simulation of queues: Simulation is the process of f...

Simulation of queues: Simulation is the process of forming an abstract model of a real world situation in order to understand the effect of modifications and the effect of introdu

Determine yiq colour model, Determine YIQ Colour Model Whereas an RGB m...

Determine YIQ Colour Model Whereas an RGB monitor requires separate signals for the red, green, and blue components of an image, a television monitor uses a single composite si

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

Acyclic graph, Tree is a widely used data structure employed for representi...

Tree is a widely used data structure employed for representing several problems. We studied tree like a special case of acyclic graph. Though, rooted trees are most prominent of al

Numerical - algorithm, Q. What is the smallest value of n such that an algo...

Q. What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine.    A n

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