Graph Algorithms



Shortest Paths

Dijkstra find single-source shortest paths

AllPairsShortestPath find shortest paths simultaneously for all pairs

ShortestPath sequence of vertices that define the shortest path

BellmanFord ▪ Eccentricity ▪ Radius ▪ Diameter ▪ Girth

ParentsToPaths ▪ GraphCenter ▪ GraphPower

Minimum Spanning Trees

MinimumSpanningTree find a minimum spanning tree of a graph

NumberOfSpanningTrees number of spanning trees

InitializeUnionFind ▪ FindSet ▪ UnionSet

Cofactor ▪ ShortestPathSpanningTree ▪ MaximumSpanningTree

NetworkFlow maximum flow through a graph

ResidualFlowGraph construct a directed graph for a graph with respect to flow

StableMarriage optimal stable marriage defined by lists of permutations

MaximalMatching compute maximal matching of a graph

BipartiteMatching find a maximum bipartite matching

NoPerfectMatchingGraph ▪ AlternatingPaths ▪ BipartiteMatchingAndCover

PartialOrderQ ▪ TopologicalSort ▪ TransitiveClosure ▪ TransitiveReduction

Graph Traversals

DepthFirstTraversal depth-first traversal of a graph

BreadthFirstTraversal breadth-first traversal of a graph

Partial Orders

HasseDiagram ▪ BooleanAlgebra ▪ IsomorphicQ ▪ InversionPoset

DominatingIntegerPartitionQ ▪ DominationLattice ▪ PartitionLattice

MinimumChainPartition ▪ MaximumAntichain

Graph Isomorphism

Isomorphism find isomorphism between two graphs

Equivalences vertex equivalence classes between two graphs

IdenticalQ ▪ IsomorphismQ ▪ Neighborhood ▪ Distances ▪ SelfComplementaryQ

DegreesOf2Neighborhood ▪ NumberOf2Paths ▪ NumberOfKPaths

New to Mathematica? Find your learning path »
Have a question? Ask support »