CS61B Guide

Searchâ€¦

Object Oriented Programming

Abstract Data Types

Sorting

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.

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!

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

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

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 modified 2yr ago

Copy link

On this page

Introduction

Graph Properties

Graph Queries

More on Graphs