Graph Theory

A graph is a bunch of nodes (the circles) connected by edges (the lines).

Quite similar to the binary search tree terminology

A path is some nodes connected by edges.

AECF is a path. It is a simple path, because it has no repeated nodes.

ADEA is a path. It is a cycle, because it revisits the node A

Directed edges are one-way edges.

A path such as FED is invalid, because the edge between E and F goes from E to F, not F to E.

Edges which do not look like arrows are two way edges.

See how there is an edge from A to B? In the adjacency matrix, in the Ath row and Bth column, there is a 1, which represents this.

See how there isn't an edge from C to A? In the adjacency matrix, in the Cth row and Ath column, there is a 0, which represents this.

A graph is connected if every node can reach every other node

A graph is made up of connected components.

A tree is a special kind of graph without cycles. If it has n nodes, it has exactly n - 1 edges.

A complete graph has all possible edges

A dense graph has many edges, while a sparse one has a few

A tree is a graph which has one less edge than nodes. A tree has only one simple path between two nodes and no cycles

A directed graph with no cycles is called a DAG (directed acyclic graph)