Introduction to Graphs
Let’s understand the Graphs pattern, its real-world applications, and some problems we can solve with it.
About the pattern
A graph is a nonlinear data structure that represents connections between entities. In graph theory, entities are represented as vertices (or nodes), and the connections between them are expressed through edges.
Let’s go over some basic components and common properties of graphs:
Name | Description |
Vertex (node) | It is the fundamental unit of a graph, usually represented as a point that holds some information or data. |
Edge | It is a connection between two nodes. An edge may have a direction (directed edge) or not (undirected edge). |
Weight | Each edge has a weight assigned to it, which indicates a cost or value associated with the connection. |
Degree | It is the number of edges incident to a node. |
In-degree | It is the number of edges coming towards the node (In directed graphs only). |
Out-degree | It is the number of edges going away from the node (In directed graphs only). |
Adjacent nodes | Those nodes that are directly connected to each other by an edge. |
Path | It is a sequence of nodes where each adjacent pair is connected by an edge. |
Cycle | It is a path that starts and ends at the same node. |
Types of graphs
There are various types of graphs, each tailored to represent different relationships and scenarios. Let’s explore the key types:
Undirected graph: A graph in which the edges have no direction, representing a two-way relationship between nodes. For example, if we consider each person on Instagram as a node and their connection with other users as edges, a two-way relationship occurs when person A follows person B and person B also follows person A.
Directed graph: A graph in which the edges have a direction, indicating a one-way relationship between nodes. For example, if person A follows person B but person B doesn’t follow person A, it’s a one-way relationship.
Weighted graph: A graph in which each edge has a numerical value assigned to it, indicating the cost, distance, or some other relevant measure associated with that connection. For example, if each person’s connection with the other person has some weight assigned to it, then the weight of
represents a strong connection between person A and person B and the weight of ...