> 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.](/files/-M70kFtR2guXM3GC-K7X)

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!](/files/-M70yfiORuJ8R_hARala)

## 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](/files/-M71OLX3hEAv37ehFkVF)

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](/files/-M71Od_NH8cIl2lQSKE3)

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.

![](/files/-M71PFB4L9kUMJXNV1Zp)

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