- Open Bookshelf Cover Page
- Preface
- Getting Started
- Introduction to Recursion
- Divide and Conquer Algorithms
- Dynamic Programming
-
Binary Trees
- Intro to Trees
- Binary Trees
- Types of Binary Trees
- Divide & Conquer in Tree Problems
- Practice: Binary Tree Height
- Tree Traversal: DFS and BFS
- Practice: Preorder Traversal
- Practice: Inorder Traversal
- Practice: Postorder Traversal
- Practice: Level Order Traversal
- Binary Search Tree
- Practice: Find Node in a BST
- Graphs
- Backtracking
- Conclusion
- Share on
Types of Graphs
Graphs are versatile data structures with various types suited for different tasks. Let's explore some common ones:
Directed and Undirected Graphs
- Undirected Graphs: The edges (connections) between vertices (points) don't have a specific direction. For example, in social networks, friendships are mutual connections, meaning both parties acknowledge the relationship equally.
- Directed Graphs: Each edge has a direction, indicated by an arrow. For example, in social media, following someone doesn't imply they follow you back, creating a one-way relationship where the direction matters.
Neighbour Nodes in Directed and Undirected Graphs
A neighbor node is any vertex that is directly connected to another vertex by an edge.
-
In Undirected Graphs, neighbor vertices are straightforward: if there is an edge between two vertices, they are considered neighbors. For example, in the graph below, vertices
1and2are neighbors to each other.
-
In Directed Graphs, the concept of neighbor vertices is more nuanced. If there is a directed edge from vertex A to vertex B, then vertex A is considered an incoming neighbor to vertex B. If there is a directed edge from vertex B to vertex C, then vertex C is considered an outgoing neighbor of vertex B.
Let's look at this graph and consider the neighbors of vertex2. Vertex1has an edge going to it, so vertex1is an incoming neighbor. Vertex4has an edge going from it, so vertex4is considered an outgoing neighbor of vertex2.
Weighted and Unweighted Graphs
- Unweighted Graphs: In these types of graphs, the connections exist without any associated weights. Every edge is treated equally, simplifying the graph structure and calculations.
- Weighted Graphs: In these graphs, each edge has a weight representing a value like distance, cost, or time. These weights allow for more complex calculations and optimizations. For example, in Google Maps, the weights of edges help find the shortest route.
Cyclic and Acyclic Graphs
-
Cyclic Graphs: These graphs have at least one loop where you can start and end at the same vertex. This property is useful for modeling systems that can return to their initial state. In the graph below, there is a cycle among vertices
1,2,4, and3.
- Acyclic Graphs: These graphs have no loops; once you go down a path, there's no way back up. They are often used to represent hierarchical structures or processes with a clear direction and no repetition.
