Data Structures - For my Ninth Grader – Part 5

Data Structures - For my Ninth Grader – Part4

Data Structures - For my Ninth Grader – Part3

Data Structures - For my Ninth Grader – Part 2

Data Structures - For my Ninth Grader – Part 1

Graph: Imagine, map of public transport (bus or train) of your city. What picture emerges! I see a mish mash of lines connecting various routes and each intersecting point as bust stop or railway station. I also see lot of loops. How to represent this mish mash as data structure!!

Graph is the answer.

To understand let us make a simpler graph.

The letters are held in what are called the vertices/nodes of the graph. Vertices can be connected to other vertices. A connection between 2 vertices is called an edge/arc

In the above graph, edges are directionless. In real life they must have direction.  Either uni-directional or bi-directional.

In a directed graph, one can move (traverse) in the direction of arrow only.

A graph data structure consists of a finite set of ordered pairs, called edges/arcs, of certain entities called nodes/vertices. An edge (x,y) is said to point or go from x to y.

One can do following operations on a tree:

• adjacent(x, y): tests whether there is an edge from node x to node y.
• neighbors(x): lists all nodes y such that there is an edge from x to y.
• addEdge(x, y): adds edge from x to y, if it is not there.
• addNode(x,y): adds a child node y to parent node x
• delete( x, y): removes the edge from x to y, if it is there.
• IsReachable(x,y): find out, is node x is reachable from y.
• getNodeValue(x): returns the value associated with the node x.
• setNodeValue(x, a): sets the value associated with the node x to a.
• getEdges(x): gets all edges connected to node x
• getNodes(x): returns the set of nodes connected to node x 
• getEdgeValue(p, q): returns the value associated to the edge (p,q).
• setEdgeValue(p, q, v): sets the value associated to the edge (p,q) to v.

A graph can be represented as:

Adjacency list: Nodes are stored as records, and every node stores a list of adjacent nodes. This representation allows the storage of additional data on the nodes.

Adjacency matrix:  A two-dimensional matrix, in which the rows represent source nodes and columns represent destination nodes.

Incidence list: Nodes and edges are stored as records. Each Node stores its incident edges, and each edge stores its incident nodes. This data representation allows the storage of additional data on nodes and edges.

Incidence matrix: A two-dimensional Boolean matrix, in which the rows represent the Node and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.