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

Primitive data structure, Primitive Data Structure These are the basic ...

Primitive Data Structure These are the basic structure and are directly operated upon by the machine instructions. These in general have dissimilar representations on different

Graphs, floyd warshall algorithm

floyd warshall algorithm

Maximum degree of any vertex in a simple graph, The maximum degree of any v...

The maximum degree of any vertex in a simple graph with n vertices is (n-1) is the maximum degree of the vertex in a simple graph.

Determine the output of vehicles algorithm, Draw trace table and determine ...

Draw trace table and determine the output from the below flowchart using following data (NOTE: input of the word "end" stops program and outputs results of survey):  Vehicle = c

Linked list, write an algorithm for multiplication of two sparse matrices u...

write an algorithm for multiplication of two sparse matrices using Linked Lists

Help with Assignment, Need help with Data Structures assignment requiring C...

Need help with Data Structures assignment requiring C++ program

Inorder and preorder traversal to reconstruct a binary tree, Q. Using the f...

Q. Using the following given inorder and preorder traversal reconstruct a binary tree Inorder sequence is D, G, B, H, E, A, F, I, C

A sort which relatively passes by a list, A Sort which relatively passes by...

A Sort which relatively passes by a list to exchange the first element with any element less than it and then repeats with a new first element is called as      Quick sort.

Process of analysis, The objective analysis of an algorithm is to determine...

The objective analysis of an algorithm is to determine its efficiency. Efficiency is based on the resources which are used by the algorithm. For instance, CPU utilization (Ti

Deletion of a node from an avl tree, For AVL trees the deletion algorithm i...

For AVL trees the deletion algorithm is a little more complicated as there are various extra steps involved in the deletion of node. If the node is not a leaf node, then it contain

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