Graphs and Graph Traversal Algorithms for Dummies by a Dummy
What are Graphs?
Graphs are Non-linear data structures made up of a collection of nodes and edges. Each element in a graph is a node and the links between the nodes are known as edges. The nodes are also referred to as vertices. Graph data structures are used from social networks to logistics problems to find optimal solutions.
Graph data structures can be represented by (V,E), V is the collection of all vertices, E is the collection of all edges represented as (u,v).
Graph Terminology:
Path: The edges that allow you to go from vertex A to vertex B is called a path
Adjacency: A vertex is said to be adjacent to another vertex if there is a edge connecting them
Graphs May be directed or undirected,
Directed graphs have edges with arrows where (u,v) exists but (v,u) doesn’t.
Undirected graphs have edges where both (u,v) and (v,u) exist.
Graphs May be weighted or unweighted,
Weighted graphs are graphs with each edge assigned a numerical value
Unweighted graphs have edges with no weights.
Weighted graphs are useful when parameters like distance, time etc between the vertices are required to perform calculations.
Graphs may be sparse or dense,
Dense graphs have lots of edges .
Sparse graphs have few edges.
The maximum number of edges a graph can have is |V|*|V|, where |V| is the number of vertices.
A path that takes you back to the node you started with is known as a cycle.
Graph Representation
There are two ways of representing a graph,
- Adjacency List
- Adjacency Matrix
Adjacency Lists
Adjacency Lists are used to represent sparse graphs. The adjacency list representation of a graph G=(V,E) consists of an array Adj of |V| lists, one for each vertex V. For each vertex u in V , the adjacency list Adj[u] contains all the vertices v such that there is an edge (u,v) that belongs to E. Adj[u] consists of all the vertices adjacent to u in the graph G.
Adjacency Matrices
Adjacency Matrices are used to represent dense graphs. For the adjacency matrix representation of a graph G= (V,E) , we assume that the vertices are numbered 1,2,3,…,|V|
In some arbitrary manner. Then the adjacency matrix representation of a graph G consists of a |V|x|V| matrix A=(a ij) such that
a ij = 1 , if edge exists. a ij = 0, if there is no edge.
Graph Traversal Algorithms :
There are two main types of graph traversal techniques they are
- Breadth First Traversal
- Depth First Traversal
Breadth First Traversal
Breadth First traversal is one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms.
Given a Graph G=(V,E) and a distinguished source vertex s, breadth first traversal starts from the source vertex and moves to the child nodes of the source vertex are added to the output, these vertices are then added to a queue (to make sure that all of these nodes are explored as well), the child nodes are than explored and added to the output, and the new nodes are enqueued while the predecessor nodes are dequeued. This process goes on until all the nodes are explored and the queue is empty.
Depth First Traversal
Depth first search as the name implies , it is to search deeper. In Breadth first search all the child nodes of the source vertex are visited first, but in Depth first traversal the algorithm starts from the source vertex and explores as far as possible along each branch, it then backtracks and sees how far it can go in alternate paths. It will keep exploring and backtracking in a loop until no node is left unmarked or visited.
Conclusion:
Graph data structures are used for a variety of different purposes as they make networks and various other processes easier to understand.
References:
1.Introduction To Algorithms , Thomas H. Cormen
2.programiz.com
