Terminology

A graph is a collection of nodes with edges between some of them.

• Directed vs undirected:
• Connected vs. unconnected: there exists a path between any two vertices
• Containing cycles vs. acyclic

Graph Representation

Adjacency List

Adjacency Matrix

Graph Traversal

Depth-First Search (DFS)

• Recursive
• Implementation is simpler than BFS
• Choose, if you want to visit every node of a graph.

Breadth-First Search (BFS)

• Choose if you have to find the shortest path between two nodes
• Not recursive
• Uses a queue