Graphs are one of the most powerful and flexible data structures used in computer science. They are used to represent relationships or connections between various entities and are incredibly useful in applications like social networks, web page linking, route mapping, and more. A Graph is made up of vertices (or nodes) and edges that connect pairs of vertices. This simple yet powerful structure allows for a wide variety of problems and algorithms, such as shortest path, network flow, and graph traversal.
A Graph is a collection of nodes (also called vertices) and edges (also called arcs) that connect pairs of nodes. It is used to model pairwise relationships between objects in various fields, such as computer science, engineering, and social sciences.
Graphs can be classified in several ways, based on the directionality of the edges, the presence of cycles, and other characteristics.
In a directed graph, the edges have a direction. Each edge points from one vertex to another. For example, in a social network, an edge may represent a "follow" relationship, which is one-way.
In an undirected graph, the edges do not have a direction. An edge between two vertices represents a bidirectional relationship.
A weighted graph is a graph where each edge has a weight or cost associated with it. This is useful in problems like finding the shortest path or optimal routing, where the edges represent distances or costs.
In an unweighted graph, edges do not carry any weight. This type of graph is simpler and is often used in basic graph traversal algorithms.
A cyclic graph contains at least one cycle. A cycle is a path that starts and ends at the same vertex.
An acyclic graph is a graph that does not contain any cycles. These are often used in scheduling, dependency resolution, etc.
A bipartite graph is a graph whose vertices can be divided into two distinct sets such that no two vertices within the same set are adjacent.
Graphs can be represented in multiple ways, depending on the type of graph and the algorithm to be used. The two most common methods of representing graphs are:
An adjacency matrix is a 2D array (matrix) used to represent a graph. If there are n vertices, the matrix is of size n x n. Each element of the matrix represents an edge between two vertices.
matrix[i][j] == matrix[j][i]).In a weighted graph, the matrix stores the weights of the edges. For an unweighted graph, it typically stores 1 for the presence of an edge and 0 for its absence.
Example of an Adjacency Matrix (undirected, unweighted graph):
A B C D
A [0, 1, 1, 0]
B [1, 0, 1, 1]
C [1, 1, 0, 1]
D [0, 1, 1, 0]
An adjacency list is a collection of lists or arrays. Each vertex in the graph has a list that contains all of its adjacent vertices (i.e., all vertices connected by an edge).
u and v, then both u's list and v's list will include each other.Example of an Adjacency List (undirected graph):
A -> B -> C
B -> A -> C -> D
C -> A -> B -> D
D -> B -> C
An edge list is a collection of all the edges in the graph. Each edge is represented as a pair of vertices (for an undirected graph) or an ordered pair (for a directed graph).
Example of an Edge List (undirected graph):
[ (A, B), (A, C), (B, C), (B, D), (C, D) ]
Graph traversal is the process of visiting all the vertices of a graph in a systematic way. The two most commonly used graph traversal algorithms are Depth-First Search (DFS) and Breadth-First Search (BFS).
DFS explores as far down a branch as possible before backtracking. It is typically implemented using recursion or a stack.
O(V + E), where V is the number of vertices and E is the number of edges.DFS Algorithm:
BFS explores all the neighbors of a vertex before moving on to their neighbors. It uses a queue to keep track of the vertices to visit next.
O(V + E).BFS Algorithm:
Graphs have wide applications in various fields. Some of the key applications include: