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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b.bencuan.me/abstract-data-types/graphs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.