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.