Algorithms On Graphs

Week 1

Graph Basics

Graph

A graph is a set of vertices and a set of edges, each of which connects two vertices.

Loop

An edge that connects a vertex to itself

Simple Graph

A graph with no loops and no more than one connection between any set of vertices.

Representing Graphs

We can store a graph as a list of edges. It can also be stored as a matrix. Or a list of lists, the top list being all the vertices and each sub list being the vertices it's connected to.

Density

Edges / vertices²

Exploring Graphs

Finding routes, ensuring connectivity, solving mazes.

Path

A sequence of vertices such that each vertex is connected to the next by an edge.

Goes through algorithm to find all connected nodes.

DFS: Depth first search.

Component; A set of connected vertices within a graph, the islands.

We can mark each vertex with a number when we arrive and a number when we leave. So a parent with one child is 1/4 and the child is 2/3. This gives us useful data about the order and structure of the spanning tree.

Week 2

Directed Graphs

DAG

directed acyclic graph.

Any DAG can be linearly ordered.

Source

Vertex with to incoming links

Sink

Vertex with no outgoing links

Week 3

Distances

BFS

Breadth first search

This is how to find distance. You can also build a minimum-spanning tree this way.