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

Last updated