Advanced Algorithms

Graph Terminology

Graph
A non-linear data structure made up of vertices and edges. Formally, a graph \(G\) is defined by its set of vertices \(V\) and its set of edges \(E\), and is written as \(G(V,E)\).
Vertex
Also called a node, is a basic element of a graph that represents an individual entity. For example, in social networks, vertices may correspond to people, whereas in road networks, they can represent intersections or specific locations.
Edge
Sometimes called an arc, is a link between two vertices in a graph that can be either directed or undirected; directed edges establish a specific one-way connection, while undirected edges represent a simple, bidirectional relationship.
Order
The total number of vertices contained in a graph. Denoted by: \(∣V∣\).
Size
The total number of edges contained between vertices in a graph. Denoted by: \(|E|\).
Directed Graph
A graph where edges have a specific direction, meaning they only allow traversal from one specific starting vertex to another specific terminal vertex.
Undirected Graph
A graph where edges have no specific direction, meaning the connection between two vertices can be traversed in either direction.
Path
A way to go from one vertex to another by following the edges of the graph, without repeating vertices.
Cycle
A path in a graph that starts and ends at the same vertex, with all other vertices and edges in the path being distinct.
Loop
An edge that connects a vertex to itself.
Acyclic Graph
A graph that contains no cycles, meaning it’s impossible to begin at any vertex, follow a sequence of edges, and return to that same starting vertex.
Cyclic Graph
A graph that contains at least one cycle, which means you can traverse a set of edges and eventually get back to the initial node.
Weighted Graph
A graph in which a numerical value, called a weight or cost, is assigned to each edge to represent a measure such as distance, time, or capacity.
Connected Graph
An undirected graph in which there is a path between every pair of distinct vertices.
Disconnected Graph
An undirected graph in which at least one pair of vertices has no path connecting them.
Tree
A connected acyclic graph.
Spanning Tree
Subgraph \(T\) of a connected undirected graph \(G\) that includes all the vertices of \(G\) and is itself a tree. A spanning tree for a connected graph with \(n\) vertices always has exactly \(n−1\) edges.
Minimum Spanning Tree (MST)
A spanning tree of a weighted, connected, undirected graph where the sum of the weights of all its edges is the smallest possible total among all other spanning trees for that graph.
Complete Graph
A undirected graph in which every pair of distinct vertices is connected by a unique edge. If \(n = |V|\), then the number of edges in a complete graph is: $$ |E| = \binom{n}{2} = \frac{n(n - 1)}{2} $$ The number of distinct spanning trees \(T_n\) that can be made from a complete graph with \(n\) vertices \((n \ge 2)\) is given by Cayley’s Formula: $$ T_n = n^{n-2} $$
Representation of Graph Data Structure

Adjacency Matrix: A square two-dimensional array used to represent a graph where the entry at row \(i\) and column \(j\) indicates whether an edge exists between vertex \(i\) and vertex \(j\).

Adjacency List: A collection of linked lists or dynamic arrays used to represent a graph where each vertex is stored with a list of its neighboring vertices.

References