Graphs

Introduction

Graphs are simply a collection of vertices connected by edges. They're very similar to trees, but are much more versatile and don't require hierarchical relationships like trees do.

A very simple graph.

For most purposes, we will be working with simple graphs that follow two rules:

• There are no loops (a connection of a node to itself).

• There are no parallel edges (two edges that connect the same two vertices).

Don't make these graphs pls. Keep life simple!

Graph Properties

Graphs can be described by some properties that they could have. Here are the important ones:

A graph can be directed if edges are arrows and have a direction, or undirected if you can cross edges in any direction.

A graph is cyclic if the edges form a loop, or acyclic if there are no loops (like in a tree).

Direction vs. Cycles

Graphs can have edge labels if edges are numbered (great for distances). They can also have vertex weights if vertices are numbered (great for priorities or costs).

Edge labels vs. Weights

Graphs are connected if all of the vertices are connected with edges, such that you can freely move from one vertex to any other vertex.

Graph Queries

Here are some cool things you can do with graphs:

• Is there a path between two vertices? (s-t path)

• What is the shortest route between two vertices? (shortest s-t path)

• Are there cycles? (cycle detection)

• Can you visit each vertex/edge exactly once? (Euler tour / Hamilton tour)

• Is a graph connected? (connectivity problem)

• Is a vertex that disconnects the graph when removed? (single point of failure / biconnectivity)

• Are two graphs isomorphic?

• Can a graph be drawn with no crossing edges? (planarity)

More on Graphs

Depth First Search (DFS), Breadth First Search (BFS), Minimum Spanning Trees, Shortest Paths, Dijkstra's Algorithm, A* Search, Prim's Algorithm, and Kruskal's Algorithm all rely on graphs. Graphs are a super useful concept!!!