Graph
A graph can be defined as a group of vertices and edges that are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent child relationship.
A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G) represents the set of edges which are used to connect these vertices. A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is shown in the following figure.
Directed and undirected graph
A graph can be directed or undirected. However, in an undirected graph, edges are not associated with the directions with them. An undirected graph does not have any edges in directions. If an edge exists between vertex A and B then the vertices can be traversed from B to A as well as A to B.
In a directed graph, edges form an ordered pair. Edges represent a specific path from some vertex A to another vertex B. Node A is called the initial node while node B is called the terminal node.
Graph terminology
- Path
- Closed Path
- Cycle
- Connected Graph
- Weighted Graph
- Digraph
- Adjacent Node
- Degree of the node
- Graph Represention
Path
A path can be defined as the sequence of nodes that are followed in order to reach some terminal node V from the initial node U.
Closed Path
A path will be called a closed path if the initial node is the same as the terminal node. A path will be a closed path if V0=VN.
Simple Path If all the nodes of the graph are distinct with an exception V0=VN, then such path P is called as closed simple path.
Cycle
A cycle can be defined as the path which has no repeated edges or vertices except the first and last vertices.
Connected Graph
A connected graph is the one in which some path exists between every two vertices (u, v) in V. There are no isolated nodes in the connected graph.
Complete Graph
A complete graph is the one in which every node is connected with all other nodes. A complete graph contains n(n-1)/2 edges where n is the number of nodes in the graph.
Weighted Graph
In a weighted graph, each edge is assigned with some data such as length or weight. The weight of an edge e can be given as w(e) which must be a positive (+) value indicating the cost of traversing the edge.
Digraph
A digraph is a directed graph in which each edge of the graph is associated with some direction and the traversing can be done only in the specified direction.
Adjacent Nodes
If two nodes u and v are connected via an edge e, then the nodes u and v are called neighbours or adjacent nodes.
Degree of the Node
A degree of a node is the number of edges that are connected with that node. A node with degree 0 is called an isolated node.
Graph Representation
By Graph representation, we simply mean the technique which is to be used in order to store some graphs into the computer's memory.
There are two ways to store Graph into the computer's memory. In this part of this tutorial, we discuss each one of them in detail.
1. Sequential Representation
In sequential representation We use an adjacency matrix to store the mapping represented by vertices and edges. In the adjacency matrix, the rows and columns are represented by the graph vertices. A graph having n vertices, will have a dimension n x n.
Representation of weighted directed graph
Representation of weighted directed graphs is different. Instead of filling the entry by 1, the Non- zero entries of the adjacency matrix are represented by the weight of respective edges.
Directed graph
In a directed graph, the sum of lengths of all the adjacency lists is equal to the number of edges present in the graph. In the case of weighted directed graphs, each node contains an extra field that is called the weight of the node. The adjacency list representation of a directed graph is shown in the following figure.
Adjacency matrix
Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight.
Adjacency multi list
It is represented by M Vertex-1 Vertex-2 List-1 List-2 Where M = Visited Vertex -1 = start vertex of edge (m,n) = m Vertex-2 = start vertex of edge (m,n) = n List -1 = List where vertex 1 is present List -2= List where vertex 2 is present
Graph traversal
Traversing the graph means examining all the nodes and vertices of the graph. There are two standard methods by which we can traverse the graphs. Let's discuss each one of them in detail.
- Breadth First Search
- Depth First Search
Breadth first search
Breadth first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes.
The algorithm follows the same process for each of the nearest nodes until it finds the goal. The algorithm of breadth first search is given below. The algorithm starts with examining the node A and all of its neighbours.
In the next step, the neighbours of the nearest node of A are explored and the process continues in the further steps. The algorithm explores all neighbours of all the nodes and ensures that each node is visited exactly once and no node is visited twice.
Breadth first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes.
The algorithm follows the same process for each of the nearest nodes until it finds the goal. The algorithm of breadth first search is given below. The algorithm starts with examining the node A and all of its neighbours.
In the next step, the neighbours of the nearest node of A are explored and the process continues in the further steps. The algorithm explores all neighbours of all the nodes and ensures that each node is visited exactly once and no node is visited twice.
Depth First Search algorithm
is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.
Here, the word backtrack means that when you are moving forward and there are no more nodes along the current path, you move backwards on the same path to find nodes to traverse. All the nodes will be visited on the current path till all the unvisited nodes have been traversed after which the next path will be selected.
The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. The DFS algorithm works as follows:
- Start by putting any one of the graph's vertices on top of a stack.
- Take the top item of the stack and add it to the visited list.
- Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack.
- Keep repeating steps 2 and 3 until the stack is empty.
Also Read
- What Means Data structure,What is the linear and non-linear Data Structure
- Array Data structure,sorting of array using bubble sort,merge sort,quick sort and searching array using binary search,linear search.
- Stack Data Structure,push and pop operations.
- Linked list Data Structure,Singly linked list and doubly linked list.
- Tree Data Structure, Learn Binary tree,Binary Search tree and Binary search tree algorithem.
Comments
Post a Comment
Please give us feedback through comments