Graph Theory

1.  Introduction:- Graph data structure and traversal
2. Ordering:-  of dependent nodes using topological ordering 
3. Shortest path:- algorithm in weighted and non-weighted graphs
4. Spanning Tree:- algorithms to connect all nodes in a graph 

• Graphs are excellent tools for modelling complex relationships 
• Adjacency matrix is most common way of representing Graph
• Adjacent List and Adjacent Sets are alternative data structures 
• Traversing of graph 1) Depth-first 2) Breath-first

Relationship between entities example:- 

Rob drives a Car.

    Entities:- {Rob, Car}

    Relationship:- {Drives}

A graph can be used to represent above relationship where 

• (V)ertices ->  entities
• (E)dges -> relationship

=> G=(V,E)

Directed and Undirected Graph

Directed (Twitter):- Rob drives his car => one directional relationship (car cannot drive Rob) => Rob -----> Car

Undirected (Facebook):- David and Dave plays football => (Bidirectional )Both way relationship => Dave <------> David

Connected Graph:- if there is a path between any two of its nodes

Complete Graph:- if every node u in G is adjacent to every other node v in G. A complete graph has n(n-1)/2 edges 

Multigraph:- is not a graph. a graph that contains 

1) multiple edges or 

2) loops

Adjacent Nodes:- e=[u,v]. then the nodes u and v are called the endpoints of e, and u and v are said to be adjacent nodes or neighbours.

In Degree:- number of nodes coming inside

Out Degree:- number of nodes going out

Tree Graph:- A connected graph T without any cycles is called a Tree graph or Free graph or simply a tree.This means, in particular, that there is a unique simple path P between any two nodes u and v in T. Furthermore, if T is a finite tree with m nodes, then T will have m-1 edges.

Forest:- A set of discount trees is called Forest