Techletter #25 | May 19, 2023
PART 1
What is a graph?
A graph is a non-linear data structure that consists of a set of vertices (also called nodes) and a set of edges that connect these vertices. Graphs are used to represent relationships between objects or entities.
It can be visualized as a collection of nodes (vertices) connected by lines (edges). The nodes represent the entities or objects, while the edges represent the relationships or connections between them.
Graphs can have weighted or unweighted edges
What is linear & non-linear data structure?
Linear Data Structure: Here, the elements or nodes are arranged in a sequential manner, where each element is connected to its immediate predecessor and successor (except for the first and last elements). Eg: Arrays, Linked Lists, Stacks & Queues.
Non-Linear Data Structure: The elements or nodes are connected in a more complex manner, without a sequential arrangement. Here, each element can have multiple paths to connect to other elements. Eg: Trees, Graphs, Maps, etc.
What is the difference between a graph & a tree?
-
Graphs: Elements (vertices/nodes) are connected by edges, forming a network-like structure. The relationships between nodes can be one-to-one, one-to-many, or many-to-many.
-
Trees: Elements are organized in a hierarchical manner, with a single root node and child nodes branching out from the root. Each node can have one or more child nodes, but there is no cyclic relationship.
Why do you need graph traversal?
-
Reachability Analysis: Traversal algorithms allow you to determine whether a specific node or set of nodes is reachable from a given source node. This is important in various applications such as finding connected components, detecting cycles, or identifying if there is a path between two nodes.
-
Path Finding: Traversal algorithms can be used to find paths between nodes in a graph. For example, in route planning or navigation systems.
Hope the above two applications motivates us to learn Graph & graph traversal
BFS Algorithm
Breadth First Search (BFS) explores all the vertices of a graph in breadth-first order. It starts at a given source vertex and visits all its neighbors first before moving on to their neighbors. So basically, it completes visiting nodes based on each level. Completes each level and moves to the next.
- Choose a starting vertex as the source.
- `Enqueue` the source vertex into a queue and mark it as visited.
- While the `queue` is not empty, do the following:
- `Dequeue` a vertex from the front of the queue.
- Process the dequeued vertex
- Enqueue all the unvisited neighbors of the dequeued vertex into the queue and mark them as visited. Add the adjacent vertices of the removed element to the queue.
- Repeat step 3 until the queue becomes empty.
Here, we are making use of queue data structure. We will implement it soon.
What is queue, enque, & dequeue?
-
queue: A linear data structure that follow First In First Out principle.
-
enqueue: Adding elements to the queue.
-
dequeue: Removing elements from the queue.
Lets go in depth, while understanding queues.
Needed while implementing
An
adjacent vertexrefers to a vertex that is directly connected to another vertex by an edge.
DFS Algorithm
DFS explores the depth of a graph before moving on to the next branch. It uses a stack or recursion to maintain the order of visited vertices.
- Choose a starting vertex.
- Mark the starting vertex as visited.
- For each unvisited neighbor of the current vertex, do the following:
- Apply the DFS algorithm recursively starting from the neighbor.
- Repeat step 3 until there are no unvisited neighbors.
- If there are remaining unvisited vertices, choose another unvisited vertex as the starting vertex and repeat steps 2-4.
- When all vertices have been visited, the traversal is complete.
Will be continued in the next article…
Resources