Graph Theory

Graph (Programming)

A graph consists of nodes and edges. See Graph Representation for actual implementation details.

Directed Graph

A directed graph (or digraph) is a set of vertices and a set of directed edges between some of the pairs of vertices.

indegree - number of incoming edges at a digraph vertex outdegree - number of outgoing edges at a digraph vertex

To solve a DAG problem, use Topological Sort + DFS.

Other Definitions

A graph is connected if there is a path between any two nodes. Also see Strong Connectivity.

The connected parts of a graph are called its components.

Search Algorithms

Graph Traversal

• Depth-First Search (DFS)
• Breadth-First Search (BFS)

Weighted Shortest Path

• Bellman-Ford Algorithm
• Dijkstra’s Algorithm
• Floyd-Warshall Algorithm

Directed Graphs

• Topological Sort
• Successor Graph
• Cycle Detection
• Strong Connectivity
  • Kosaraju’s Algorithm

Other graph algorithms

• A* Algorithm

Related

• Graph Theory
• Tree
• Binary Tree

From LeetCode

Shortest path with at most k edges https://stackoverflow.com/questions/69356130/given-a-graph-return-the-shortest-path-from-start-to-end-that-has-at-most-k-edg

Interesting problems

This is like a shortest amount of time that two people meet in the middle. https://codeforces.com/contest/2014/problem/E

• That’s so easy, you’re stupid, just do djikstra’s from the two people’s original positions, and then afterwards, check for all nodes and get the max