A graph is a non-linear data structure that consists of a finite set of nodes and a set of edges connecting them. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes.
A graph is a set of (V,E) pairs, where
V - set of vertices - Represented as Circles - Also know as Nodes
E - set pf edges - Represented as Lines - connecting lines of vertices/nodes
Example 1:
Note :
Tree : For a tree if N nodes are there then (N-1) edges will be there, one edge for each parent-child relationship.
Graph : For a Graph there are no rules for connections.
Example 2:
Fig 1 Fig 2
Note : In the above two figures Fig 1 is a Tree and a Graph as well. Where as Fig 2 is only a Graph.
A pair (x,y) is referred to as an edge, which communicates that the x vertex connects to the y vertex.
A graph G is an ordered pair of set V of vertices and a set E of edges.
G=(V,E)
Ordered pair:
(a,b) is not equal to (b,a), if a is not equal to b
Unordered pait:
{a,b}={b,a}
Graphs are used to solve real-life problems that involve representation of the problem space as a network. Examples of networks include telephone networks, circuit networks, social networks (like LinkedIn, Facebook etc.).
Ex : Undirected Graph
For example, a single user in Facebook can be represented as a node (vertex) while their connection with others can be represented as an edge between nodes. Each node can be a structure that contains information like user’s id, name, gender, etc.
Above Graph showis a Social Network (Nodes as users and Edges show connection)
Terminology
Node - Also know as vertex
Edge - Connecting line between any two nodes
These are two types. Directed Edge in which connection is one way and Undirected edge in
which connection is two way.
Directed Edge (u,v) and Undirected Edge {u,v}
Adjacent nodes - which are connected to both ends of an edge
Degree of a Node - No of edges connected to a node
Size of a graph - total no of edges in a graph
Path - A path is a sequence of vertices where each adjacent pair is connected by an edge.
Types of Graphs
Directed Graph(unidirectional)
Un-Directed Graph(bidirectional) - no direction is specified on edges
Weighted Graph - weight is specified for each edge
Unweighted Graph - weight is not specified for any edge
Cyclic Graph - A graph which contains cycles(loops)
Acyclic Graph - A graph which do not contain cycles(loops)
Directed Graph
In a directed graph, nodes are connected by directed edges – they only go in one direction. For example, if an edge connects node 1 and 2, but the arrow head points towards 2, we can only traverse from node 1 to node 2 – not in the opposite direction.
Un-Directed Graph
In an undirected graph, nodes are connected by edges that are all bidirectional. For example if an edge connects node 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1.
Ex : Directed Graph is useful in Web-Crawling is nothing but Graph Traversal , It is an act of visiting all nodes in a graph.
Weighted Graph - weight is specified for each edge
Unweighted Graph - weight is not specified for any edge (or) All edges are having same edge
(OR)
A weighted graph with all edges having weight=1 unit
UnDirected Graph :
Ex :Intercity Road Network : Network of Highways and 3 ways between cities.
Directed Graph :
Ex: Intracity Road Network : Network within a city. One way roads.It is a weighted .
.
Edges in the above graph are waited and it is called as weighted graph.
**Social Network is unweighted and undirected graph
**WWW is unweighted and directed graph
Cyclic Graph - A graph which contains cycles(loops)
Types of Graph Representations:
Adjacency List
To create an Adjacency list, an array of lists is used. The size of the array is equal to the number of nodes.
A single index, array[i] represents the list of nodes adjacent to the ith node.
We make use of Linked List to represent "Adjacency List". For each vertex one Linked List is maintained.
Ex1:
Ex2:
Adjacency Matrix:
An Adjacency Matrix is a 2D array of size V x V where V is the number of nodes in a graph. A slot matrix[i][j] = 1 indicates that there is an edge from node i to node j.
[OR]
It is a Matrix a[n][n], where n is number of Vertices and a[i][j]=1 if i & j are adjacent
other wise a[i][j]=0.
Ex:
The Matrix representation of above Graph is given below
Graph Traversal
Graph traversal is a technique used for a searching vertex in a graph. The graph traversal is also used to decide the order of vertices is visited in the search process. A graph traversal finds the edges to be used in the search process without creating loops. That means using graph traversal we visit all the vertices of the graph without getting into looping path.
There are two graph traversal techniques and they are as follows...
DFS (Depth First Search)
BFS (Breadth First Search)
DFS (Depth First Search)
DFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph without loops. We use Stack data structure with maximum size of total number of vertices in the graph to implement DFS traversal.
We use the following steps to implement DFS traversal...
Back tracking : Means coming back to the vertex from which we reached the current vertex.
Step 1 - Define a Stack of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.
Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack and push it on to the stack.
Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of the stack.
Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from the stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph
Ex : consider the following example
