> For the complete documentation index, see [llms.txt](https://cs61b.bencuan.me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b.bencuan.me/abstract-data-types/graphs.md).

# 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.](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M70hCvCGRHE-E3FA5he%2F-M70kFtR2guXM3GC-K7X%2Fimage.png?alt=media\&token=efe0791c-aa33-4591-861b-ee102e29db10)

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!](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M70hCvCGRHE-E3FA5he%2F-M70yfiORuJ8R_hARala%2Fimage.png?alt=media\&token=82b5c405-fa2a-422b-93ce-003b6841b339)

## 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](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M70hCvCGRHE-E3FA5he%2F-M71OLX3hEAv37ehFkVF%2Fimage.png?alt=media\&token=8d09d3e3-cb02-4da7-8782-bba1b15f3c3c)

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](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M70hCvCGRHE-E3FA5he%2F-M71Od_NH8cIl2lQSKE3%2Fimage.png?alt=media\&token=11859c75-1743-4261-af61-62337c33c182)

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.

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M70hCvCGRHE-E3FA5he%2F-M71PFB4L9kUMJXNV1Zp%2Fimage.png?alt=media\&token=b86e5eb8-12fd-414d-8c83-1ae9a7165dc7)

## 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)](/algorithms/searching/depth-first-search-dfs.md), [Breadth First Search (BFS)](/algorithms/searching/breadth-first-search-bfs.md), [Minimum Spanning Trees](/algorithms/minimum-spanning-trees.md), [Shortest Paths](/algorithms/shortest-paths.md), [Dijkstra's Algorithm](/algorithms/shortest-paths/dijkstras-algorithm.md), [A\* Search](/algorithms/shortest-paths/a-search.md), [Prim's Algorithm](/algorithms/minimum-spanning-trees/prims-algorithm.md), and [Kruskal's Algorithm](/algorithms/minimum-spanning-trees/kruskals-algorithm.md) all rely on graphs. Graphs are a super useful concept!!!