Introduction to Graphs

Learn about graphs, their applications, and their operations.

Graphs overview

In this module, we study two representations of graphs and basic algorithms that use these representations.

Mathematically, a (directed) graph is a pair G=(V,E)G = (V ,E) where VV is a set of vertices and EE is a set of ordered pairs of vertices called edges. An edge (i,j)(i,j) is directed from ii to jj; ii is called the source of the edge and jj is called the target. A path in GG is a sequence of vertices v0,...,vkv_0,..., v_k such that, for every i{1,...,k}i \in \{1,...,k\}, the edge (vi1,vi)(v_{i−1}, v_i) is in EE. A path v0,...,vkv_0,..., v_k is a cycle if, additionally, the edge (vk,v0)(v_k , v_0) is in EE. A path (or cycle) is simple if all of its vertices are unique. If there is a path from some vertex viv_i to some vertex vjv_j, then we say that vjv_j is reachable from viv_i. An example of a graph with twelve vertices is shown below. Vertices are drawn as numbered circles and edges are drawn as pointed curves pointing from the source to the target.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy