Graph Traversal

Graph in the simplest terms is a representation of some real world fact in terms of nodes and edges. It consists of a collection of nodes and a set of edges connecting them. In a general graph, there is no restriction on  type of nodes that can be connected by an edge.


Tree on the other hand are special case of graph where there exists exactly one path between each pair of nodes. A tree is just connected. Adding even a single edge results in a cycle. So a tree with n nodes has n-1 edges.

Traversal
When graph represent some real world entity and we want to examine all the nodes which are connected to each other then its called traversing a graph. Since a general graph can contain a cycle, hence algorithms do exists to avoid such issues. In this blog i will be covering about most recognized graph traversal algorithms. Many of these algorithms are also related to tree traversal. We will be discussing about following graph traversal algorithms
1. Breadth First Search (BFS)
2. Depth First Search (DFS)
3. Prim' Algorithm
4. Kruskal's Algorithm
5. Dijkstra's Algorithm (Single Source Shortest Path )
6. Bellman Ford Algorithm ( Single Source Shortest Path )
7. Floyd Warshall Algorithm (All Pair Shortest Path )

Some of coomon terminology used are
SSSP i.e. Single source shortest path in which we try to find optimum traversal strategy so that all the nodes are at a shortest distance from a particular node.
All Pair is the generalized form of SSSP algorithm. In this, we try to find shortest path between all pair of vertices. i.e. overall distance is minimum.
----------------------------------------------------------------------------------------------
1. Breath First Search


2. Depth First Search


3. Prim's Algorithm
It finds spanning tree in only one of connected graph.

4. Kruskal's Algorithm
If the graph consist of multiple disjoint connected graph then it finds minimum spanning tree in each of graph at once.

5. Dijkstra's Algorithm
SSSP where each node has non negative weight

6. Bellman Ford Algorithm
SSSP where nodes can have negative weight but any cycle with negative value should not exist.
It is interesting to know that a similar problem i.e. graph where negative weight cycle exists, and shortest path finding such that no edge appears twice is NP complete problem

7. Floyd Warshall's Algorithm

Chromatic Number For different types of Graph

Chromatic Number: Minimum no of colors to color a node.

Graph Type                                      Chormatic no.
--------------------------------------------------------------------------
Complete Graph (G(kn) )                           n
Cyclic Graph (Cn)                                     3           (n = odd)
                                                               2           (n = even)
Star Graph (Sn)                                        2
Wheel Graph (Wn)                                    3           (n = odd)
                                                               4           (n = even)
Bipartile Graph                                          2

Terminology in Graph Theory

Some Of Graph Theory Related Terminology.

* Loop: An edge connecting a vertex to itself.

* Directed Edge: Each edge has a direction.

* Simple Graph: Graph with no loops or multi-edges.

* Walk: A sequence v0e1v1 . . . envn.

* Trail: A walk with distinct edges.

* Path: A trail with distinct vertices.

* Connected Graph: A graph where there exists a path between any two vertices.

* Component: A maximal connected subgraph.

* Tree: A connected acyclic graph.

* Free tree: A tree with no root.

* DAG: Directed acyclic graph.

* Eulerian Graph: Graph with a trail visiting each edge exactly once.

* Hamiltonian Graph: Graph with a cycle visiting each vertex exactly once.

* Cut: A set of edges whose removal increases the number of components.

* Cut-set: A minimal cut.

* Cut-edge: A size 1 cut.

* k-Connected: A graph connected with the removal of any k − 1 vertices.

* k-Regular: A graph where all vertices have degree k.

* k-Factor: A k-regular spanning subgraph.

* Matching: A set of edges, no two of which are adjacent.

* Clique: A set of vertices, all of which are adjacent.

* Independent set: A set of vertices, none of which are adjacent.

* Vertex cover: A set of vertices which cover all edges.

* Planar graph: A graph which can be embeded in the plane.

* Plane graph: An embedding of a planar graph.