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

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 

Posted Date: 7/13/2012 2:23:03 AM | Location : United States







Related Discussions:- Hash function, sparse matrix, reachability index, Assignment Help, Ask Question on Hash function, sparse matrix, reachability index, Get Answer, Expert's Help, Hash function, sparse matrix, reachability index Discussions

Write discussion on Hash function, sparse matrix, reachability index
Your posts are moderated
Related Questions
The process of accessing data stored in a serial access memory is same to manipulating data on a By using stack  method.

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

Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a prog

Implement multiple queues in a single dimensional array. Write algorithms for various queue operations for them.

Graphs are data structures which consist of a set of vertices & a set of edges which connect the vertices. A graph where the edges are directed is called directed graph. Or else, i

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

Varieties of Arrays In some languages, size of an array should be established once and for all at program design time and can't change during execution. Such arrays are known a

Question 1 Discuss the advantages of implementation checks preconditions Question 2 Write a ‘C' program to search for an item using binary search Question 3 Show that To

(i)  Consider a system using flooding with hop counter. Suppose that the hop counter is originally set to the "diameter" (number of hops in the longest path without traversing any

write an algorithm for stack using array performing the operations as insertion ,deletion , display,isempty,isfull.