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
Prepare a GUI called Hotplate GUI that holds a central panel that draws a rectangular grid that represents Element objects which should be held in a 2-dimensional array. The applic

Each of the comparison in the binary search decrease the number of possible candidates where the key value can be searched by a factor of 2 as the array is divided into two halves

red black tree construction for 4,5,6,7,8,9

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

What is a Spanning tree of a graph? A Spanning Tree is any tree having of vertices of graph tree and some edges of graph is known as a spanning tree.

Draw trace table and determine output from the subsequent flowchart using below data:  X = 5, -3, 0, -3, 7, 0, 6, -11, -7, 12

Determine about the logic gates Many electronic circuits operate using binary logic gates. Logic gates essentially process signals that represent true or false or equivalent i.

Describe an algorithm to play the Game of Nim using all of the three tools (pseudocode, flowchart, hierarchy chart)

how to write a function of area of a circle using python

The complexity of searching an element from a set of n elements using Binary search algorithm is   O(log n)