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.

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).

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).

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).

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!!!