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.

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 1 and 2 are 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 of 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 vertex 2. Vertex 1 has an edge going from it, so vertex 1 is an incoming neighbor. Vertex 4 has an edge going to it, so vertex 4 is considered an outgoing neighbor of vertex 2.

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 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, and 3.

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.