Graphs in Data Structures

  • Data sometimes contains a relationship between pairs of elements which is not necessarily hierarchical in nature, e.g. an airline flights only between the cities connected by lines. This data structure is called Graph.
  • A graph is an abstract data structure that is used to implement the mathematical concept of graphs. It is basically a collection of vertices (also called nodes) and edges that connect these vertices.
  • A graph is often viewed as a generalization of the tree structure, where instead of having a purely parent-to-child relationship between tree nodes, any kind of complex relationship can exist.
  • A graph may be either undirected or directed. Intuitively, an undirected edge models a "twoway" or "duplex" connection between its endpoints, while a directed edge is a one-way connection, and is typically drawn as an arrow.
  • A directed edge is often called an arc. Mathematically, an undirected edge is an unordered pair of vertices, and an arc is an ordered pair. The maximum number of edges in an undirected graph without a self-loop isn(n - 1)/2 while a directed graph can have at most n 2 edges
  • Graphs can be classified by whether or not their edges have weights. In Weighted graph, edges have a weight.

Graph Terminology

  • Adjacent Vertices:- Vertex v1 is said to be adjacent to a vertex v2 if there is an edge(v1, v2) or (v2, v1).
  • Path:- A path from vertex w is a sequence of vertices, each adjacent to the next.
  • Cycle:- A cycle is a path in which first and last vertices are the same.
  • Connected graph:- A graph is called connected if there exists a path from any vertex to any other vertex. These are graphs which are unconnected.
  • Degree:- The number of edges incident on a vertex determine its degree.
  • Complete graph:- A graph G is said to be complete if all its nodes are fully connected. That is, there is a path from one node to every other node in the graph. A complete graph has n(n–1)/2 edges, where n is the number of nodes in G.
  • Weighted graph:- A graph is said to be weighted graph if every edge in the graph is assigned some weight or value.
  • Tree:- A graph is a tree if it has two properties :
  1. It is connected, and
  2. There are no cycles in the graph.

Graph Representation

There are two standard ways of maintaining a graph G in the memory of a computer.

  1. The sequential representation (Adjacency Matrix)
  2. The linked representation (Adjacency List)

Adjacency Matrix Representation

  • An adjacency matrix is one of the two common ways to represent a graph. The adjacency matrix shows which nodes are adjacent to one another.
  • Two nodes are adjacent if there is an edge connecting them. In the case of a directed graph, if node j is adjacent to node i, there is an edge from i to j . In other words, if j is adjacent to i, you can get from i to j by traversing one edge.
  • For a given graph with n nodes, the adjacency matrix will have dimensions of nxn. For an unweighted graph, the adjacency matrix will be populated with Boolean values.

Adjacency List Representation

  • The adjacency list is another common representation of a graph. There are many ways to implement this adjacency representation.
  • One way is to have the graph maintain a list of lists, in which the first list is a list of indices corresponding to each node in the graph. Each of these refer to another list that stores a the index of each adjacent node to this one.
  • It might also be useful to associate the weight of each link with the adjacent node in this list.

Adjacency Multi-lists

  • Adjacency Multi-lists are an edge, rather than vertex based, graph representation. In the Multilist representation of graph structures; these are two parts, a directory of Node information and a set of linked list of edge information.
  • There is one entry in the node directory for each node of the graph. The directory entry for node i points to a linked adjacency list for node i. each record of the linked list area appears on two adjacency lists: one for the node at each end of the represented edge.

Graph Traversal

Graph traversal is the problem of visiting all the nodes in a graph in a particular manner, updating and/or checking their values along the way. The order in which the vertices are visited may be important, and may depend upon the particular algorithm.

The two common traversals:

  • Breadth-first search
  • Depth-first search

Breadth-first search

  • Breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighbouring nodes. Then for each of those nearest nodes, the algorithm explores their unexplored neighbour nodes, and so on, until it finds the goal.
  • A breadth-first search (BFS) explores nodes nearest the root before exploring nodes further away.

Applications of Breadth-First Search Algorithm

Breadth-first search can be used to solve many problems such as:

  • Finding all connected components in a graph G.
  • Finding all nodes within an individual connected component.
  • Finding the shortest path between two nodes, u and v, of an unweighted graph.
  • Finding the shortest path between two nodes, u and v, of a weighted graph.

Depth First Search

  • The depth-first-search algorithm is similar to the standard algorithm for traversing binary trees; it first fully explores one subtree before returning to the current node and then exploring the other subtree.
  • Another way to think of depth-first-search is by saying that it is similar to breadth-first search except that it uses a stack instead of a queue.

Applications of Depth-First Search Algorithm

Depth-first search is useful for:

  • Finding a path between two specified nodes, u and v, of an unweighted graph.
  • Finding a path between two specified nodes, u and v, of a weighted graph.
  • Finding whether a graph is connected or not.
  • Computing the spanning tree of a connected graph.

Shortest Path algorithm

  • The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
  • This is analogous to the problem of finding the shortest path between two intersections on a road map: the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment.
  • The Minimal Spanning Tree problem is to select a set of edges so that there is a path between each node. The sum of the edge lengths is to be minimized.
  • The Shortest Path Tree problem is to find the set of edges connecting all nodes such that the sum of the edge lengths from the root to each node is minimized.

 Applications of Graph

Graphs are constructed for various types of applications such as:

  • In circuit networks where points of connection are drawn as vertices and component wires become the edges of the graph.
  • In transport networks where stations are drawn as vertices and routes become the edges of the graph.
  • In maps that draw cities/states/regions as vertices and adjacency relations as edges.
  • In program flow analysis where procedures or modules are treated as vertices and calls to these procedures are drawn as edges of the graph.
  • Once we have a graph of a particular concept, they can be easily used for finding shortest paths, project planning, etc.
  • In flowcharts or control-flow graphs, the statements and conditions in a program are represented as nodes and the flow of control is represented by the edges.

Algorithms