Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » Data File StructureRSS Feeds

Files and Graphs

Posted By: Amalasand Miller     Category: C++ Programming     Views: 5352

This article defines and also provides example of files and graphs terms.

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.

  
Share: 


Didn't find what you were looking for? Find more on Files and Graphs Or get search suggestion and latest updates.

Amalasand Miller
Amalasand Miller author of Files and Graphs is from Frankfurt, Germany.
 
View All Articles

 

Other Interesting Articles in C++ Programming:


 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
No Comment Found, Be the First to post comment!