Graph in Data Structure

 Graph in Data Structure

Introduction

Graph is a collection of nodes (vertices) and edges. Edge is a pair of vertices, if u and v are two vertices of a Graph, G, and u is adjacent to v, then uv is an edge (e) of G, e = (u,v). Graphs can be used to represent cities and highways connecting to them, circuit board, and many more things.

A path in a graph is a sequence of distinct vertices adjacent to next.

A cycle is a path containing at least three vertices, the last vertex is adjacent to the first.

Graph Representation

•                  The set representation: Two sets are used: one to represent vertices, another to represent edges.

•                  Adjacency Table: Two dimensional boolean array can be used to represent graph. The vertices are represented by the index of array, starting from 0 to n-1, where n is the number of vertices of the graph. Boolean graph [n][n]; g[u][v] = true --> u is adjacent to v; u and v are array indices representing vertices of graph

•                  Adjacency List: List containing distinct vertices and another list to show adajcent vertices for each vertex.

Topological Sort

Topological sorting is arrangement of vertices of the directed graph with no directed circle in such a way that if there is an edge from vertex u to vertex v then u precedes v in the sequential listing. Topological sorting can be used to represent jobs which can be done in sequence only; one job can't be started without completing jobs before it.

Cycle Detection in a Undirected Graph

•  cycleDetectionDFS(a)

•  num(a) = j++;//assign a unique number to a

•  for all vertices b adjacent to a

•      if num(a) == 0 then

•        add edge ab to list edges;

•        cycleDetectionDFS(b);

•      else

•        cycleDetected

Minimum Spanning Tree

Suppose graph, G, represents roads connections between five cities. For some reasons, as many of road connections have to be closed but still able to reach from one city to other cities. To solve this problem, we have to create a tree with minimum number of road connections. We have to create a spanning tree.

Minimum Spanning Tree is a spanning tree with all the nodes of graphs connected somehow and in which the weights of the edges is minimal.

Kruskal's Algorithm for Minimum Spanning Tree

•  All the edges of the graph are ordered by weight

•  for each edge arranged in the ordered sequence

•       if (adding of that edge to the tree under construction form cycle == false) then

•         the edge is added to the tree

•      otherwise discard that edge.