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.                                                                                                               


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
Define Merge Sort  Merge sort is a perfect example of a successful application of the divide and conquer method. It sorts a given array A[0...n-l] by separating it into two ha

Book to refer: Introduction to Algorithms, 3rd Ed, by Clifford Stein, Thomas H. Cormen, Ronald Rivest, Charles E. Leiserson Question: Tic Tac Toe game -Design a GUI and implement

It is a naturally occurring sorting method exemplified through a card player arranging the cards dealt to him. He picks up the cards like they are dealt & added them into the neede

Define the term array. An array is a way to reference a series of memory locations using the same name. Each memory location is represented by an array element. An  array eleme

#quCreate a flowchart to show the process that will allow the implementation of Queue, Enqueue, and Dequeue operations.estion..

hello, i need help in data mining assignment using sas em and crisp-dm

Write a detailed description of a function that takes in an integer as an argument, then prints out the squares of all positive integers whose squares are less than the input. (The

The complexity of multiplying two matrices of order m*n and n*p is    mnp

Post-order Traversal This can be done both iteratively and recursively. The iterative solution would need a change of the in-order traversal algorithm.

What are the things require to implement ADT Abstract data types are very useful for helping us understand the mathematical objects which we use in our computations but, of cou