Graphs

From programming_contest
Revision as of 06:34, 31 August 2016 by imported>Kmk21
Jump to navigation Jump to search

Graph problems are so ubiquitous that its unimaginable to have a contest set without multiple graph based problems. To be successful, you must become comfortable working with graphs, representing them, transforming them, and executing well known algorithms on them.

What is a Graph

Graph Properties

Directionality

weightedness

Flow

Bipartite

DAGs

Trees

Graph Representation

Adjacency Matrix

Adjacency List

Implied Graphs

Standard Graph Algorithms

Topological Sort

Breadth First Search

==Depth First Search

Minimum Spanning Tree

Distance Algorithms

Dijkstra

Bellman Ford

Floyd-Warshall

Strongly Connected Components

Bi-Connected Components

Flow and Matching Algorithms

Max Flow

Min Cost Max Flow

Bipartite Matching/Vertex Cover

Min Cost Matching