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

Limitation of binary search, Limitation of Binary Search: - (i)  The co...

Limitation of Binary Search: - (i)  The complexity of Binary search is O (log2 n). The complexity is similar irrespective of the position of the element, even if it is not pres

What is quick sort, What is quick sort? Quick sort is a sorting algorit...

What is quick sort? Quick sort is a sorting algorithm that uses the idea if split and conquer. This algorithm chooses an element called as pivot element; search its position in

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

State the ruby programming language, The Ruby Programming Language Alth...

The Ruby Programming Language Although data structures and algorithms we study aren't tied to any program or programming language, we need to write particular programs in speci

Inorder traversal, Inorder traversal: The left sub tree is visited, then t...

Inorder traversal: The left sub tree is visited, then the node and then right sub-tree. Algorithm for inorder traversal is following: traverse left sub-tree visit node

Types of a linked list, A linked list can be of the following types:- ...

A linked list can be of the following types:-  Linear linked list or one way list Doubly linked list or two way list. Circular linked list Header linked list

Arrays, This unit discussed about data structure called Arrays. The easiest...

This unit discussed about data structure called Arrays. The easiest form of array is a one-dimensional array which may be described as a finite ordered set of homogeneous elements

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

Illustrate the back face detection method, Illustrate the Back Face Detecti...

Illustrate the Back Face Detection Method A single polyhedron is a convex solid, which has no external angle between faces less  than 180° and there is a simple object space me

Frequency count, what is frequency count with examble

what is frequency count with examble

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