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
Decision Tree A decision tree is a diagram that shows conditions and actions sequentially and therefore shows which condition is to be considered first, second and so on. It is

what are grounded header linked lists?

What is the time complexity of Merge sort and Heap sort algorithms? Time complexity of merge sort is O(N log2 N) Time complexity of heap sort is   O(nlog2n)

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

* Initialise d & pi* for each vertex v within V( g ) g.d[v] := infinity  g.pi[v] := nil g.d[s] := 0; * Set S to empty * S := { 0 }  Q := V(g) * While (V-S)

ESO207: Programming Assignment 1 Due on 6 Sept, 2015. To be submitted online. Problem In this assignment you are required to implement k-way Merge Sort algorithm. In this version p

Merge sort is also one of the 'divide & conquer' classes of algorithms. The fundamental idea in it is to split the list in a number of sublists, sort each of these sublists & merge

Document processing is quickly becoming one of the dominant functions of computers. Computers are utilized to edit, search & transport documents over the Internet, and to display d

Explain the Memory Function method The Memory Function method seeks to combine strengths of the top  down and bottom-up approaches  to  solving  problems  with  overlapping  su

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program