Graphs - AlgoViz

Home
Graphs

Graph algorithms

Overview

A graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

They consist of a fixed number of vertices (or nodes), which represent the data points and edges, which show the relation between vertices. These edges can be directed or undirected.

For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person A can shake hands with a person B only if B also shakes hands with A. In contrast, if any edge from a person A to a person B corresponds to A owes money to B, then this graph is directed, because owing money is not necessarily reciprocated. The former type of graph is called an undirected graph while the latter type of graph is called a directed graph.

Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

Search

Graph Traversal

A graph traversal algorithm visits every vertex it can reach from its starting point, effectively traversing the entire graph if there are no disconnected vertices.

Breadth-first search

Breadth-first search starts at the root node (or any specified node) and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Time Complexity:O(|V|+|E|)
Space Complexity:O(|V|)

Depth-first search

Depth-first search starts at the root node (or any specified node) and explores the node branch as far as possible before being forced to backtrack and expand other nodes.

Time Complexity:O(|V|+|E|)
Space Complexity:O(|V|)

Minimum Spanning Tree

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Prim's algorithm

Prim's algorithm operates by building the MST one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Time Complexity:
adjacency matrix:O(|V|²)
binary heap & adjacency list: O(|E|log|V|)
fibonacci heap & adjacency list: O(|E|+|V|log|V|)

Kruskal's algorithm

Kruskal's algorithm works by stepping through all edges and adding the next lowest-weight edge that will not form a cycle to the MST.

Time Complexity:O(|E|+|V|log|V|)

Strongly Connected Components

A strongly connected component is a subset of vertices such that any two vertices of this subset are reachable from each other.

Kosaraju's algorithm

Kosaraju's algorithm is a DFS-based algorithm used to find Strongly Connected Components (SCC) in a graph. It is based on the idea that if one is able to reach a vertex v starting from vertex u, then one should be able to reach vertex u starting from vertex v, and if such is the case, one can say that vertices u and v are strongly connected - they are in a strongly connected sub-graph.

Time Complexity:
adjacency matrix:O(|V|²)
adjacency list:O(|E|+|V|)

Tarjan's algorithm

Tarjan's algorithm is based on depth-first search (DFS). The vertices are indexed as they are traversed by the DFS procedure. While returning from the recursion of DFS, every vertex V gets assigned a vertex L as a representative. L is a vertex with the least index that can be reached from V. Nodes with the same representative assigned are located in the same strongly connected component.

Time Complexity:
O(|E|+|V|)