File
File is a sequence of related or group or logical records mapped onto disk blocks.
File Organization
File organization is a technique to organize the files in a way that corresponds closely to the manner in which we expect data to be accessed and to reduce block-access time.
Sequential File Organization
Sequential file organization is an organization in which records are stored and access in sequential order, as we don’t have any reference for any record.
Direct or Random File Organization
Direct file organization is an organization in which records can be access randomly with the help of some key. The correspondence is maintained by direct address indexing or key indexing which help us to access any record directly based on address or key mentioned in the index of that particular record.
Index
Index is a special kind of stored file in which each entry consists of precisely two values – a data value and a pointer. Data value is a value for some field of the indexed file and the pointer identifies the corresponding record of that file.
Semi-Random or Indexed Sequential File Organizations
Semi-Random file organization is an organization in which there is reference for the major records so we can access them directly but for sub record there is no reference so we have to follow sequential approach for them.
Garbage
During the program execution blocks of storage that once were needed but which at some later time became unnecessary and unused are called garbage.
Garbage Collection
Garbage collection is a method that makes use of special routine to as to find all the garbage nodes and to add them to the list of free nodes.
Dangling Pointers
If a node is being pointed by pointer p and q is pointer which points to p, so now if we free the pointer p, then the memory for pointer p is also freed. So now q no longer points to desired location. So such pointer q is called dangling pointer.
Accumulation
Sometimes if some request for storing some program or variable comes which demands number of loss more than available storage blocks. At that time that storage request is being rejected but still if we free the previously occupied unused block he feel that the storage request could have been satisfied. A request just had been rejected due to the method that is being used for freeing unused storage. This problem is called accumulation.
Reference Counter
Reference counter is nothing but it is maintaining the number of references to a particular block. If the block is to be deleted than its reference counter must be zero. It solves both accumulation and dangling pointer problems.
Graph
Graph is a non-linear data structure consists of non-empty set V which is called set of vertices and a set of edges E and a mapping between each and every members of E to the set of two nodes from V.
Adjacent Nodes
The member nodes of V of a graph connected by the member of edge E is called adjacent nodes.
Directed Graph
If each and every member edge is directed edge then the graph is called directed graph.
Undirected Graph
If number o9f directed edge is 0 then the graph is called undirected graph.
Mixed Graph
If there are five edges and out of them two are directed and rest are undirected then it is called mixed graph.
Initial Node
Let (V,E) be a graph and let x belongs to E be a directed edge associated with the ordered pair of nodes (u,v). The node u is called the initial node.
Terminal Node
Let (V,E) be a graph and let x belongs to E be a directed edge associated with the ordered pair of nodes (u,v). The node v is called the initial node.
Incident
An edge x belongs to E which joins the nodes u and v is said to be incident to the nodes u and v.
Loop
Any edge whose initial and terminal nodes are same is called loop.
Similar Edges
The two edges which are parallel and whose initial nodes are same are called similar edges.
Distinct Edges
The two edges which are parallel but whose initial nodes are not same are called distinct edges.
Parallel Edges
The edges which are having initial and terminal nodes from same set is called parallel edges.
Multigraph
Any graph which is containing parallel edges is called multigraph.
Weight
The number on any edge is called the weight of that graph. They are the number of paths from one node to another.
Weighted Graph
Whenever the graph shows the weight for each and every edge is called weighted graph.
Isolated Node
Any node which is not associated with any edge is called isolated node.
Null Graph
A graph containing only isolated nodes is called null graph.
Indegree
The total number of edges which are subset of set E of given graph G which is having V as terminal node is called indegree.
Outdegree
The total number of edges which are subset of set E of given graph G which is having V as initial node is called outdegree.
Total Degree
The total number of edges which are associated with a particular node is called total degree.
Path
Path is sequence of edges or traversal through edges in which terminal node of one edge is initial node for next edge in sequence.
Length of Path
The total number of edges which are traverse in a path is called length of path.
Cycle
Cycle is a path whose initial and terminal node is same.
Simple Path
A path which contains all distinct edges is called simple path.
Elementary Path
Any path in which member nodes are not repeated is called elementary path.
Adjacent Matrix
It is a tabular or matrix representation of a given graph which gives us the information about each and every adjacent node is called adjacent matrix.
Reachable Set
If there is a path from u to v then v is said to be reachable set.
BFS (Breadth First Search)
Breadth First Search is the technique to find the shortest distance between some starting node and the remaining nodes of the graph. This shortest distance is the minimum number of edges traversed in order to travel from the start node to the specific node being examined. It is called BFS because the distances are given breadth wise. It is the faster search technique as the representation of the nodes and the edges are in the form of adjacency list representation. We can also use this technique for searching.
DFS (Depth First Search)
A depth first search of an arbitrary graph can be used to perform a traversal of a general graph. The strategy is as follows. A node s is picked as a start node and marked. An unmarked adjacent node to s is now selected and marked, becoming the new start node; possibly leaving the original start node with unexplored edges for the present. The search continues in the graph until the current path ends at a node with outdegree zero or at a node with all adjacent nodes already marked. Then the search returns to the last node which still has unmarked adjacent nodes and continues marking until all nodes are marked. Since adjacent nodes are needed during the traversal, the most efficient representation again is an adjacency list.
Spanning Trees
A spanning tree of a graph is an undirected tree consisting of only those edges necessary to connect all the edges in the original graph. The particular spanning tree for a graph depends on the criteria used to generate it. If a depth first search is used, those edges traversed by the algorithm form the edges of the tree, referred to as a depth first spanning tree. If a breadth first search is used, the spanning tree is formed from those edges traversed during the search, referred to as a breadth first spanning tree.