2. Red Blob Games - Grids and Graphs

  3. Red Blob Games - Introduction to the A* Algorithm



A graph is a way of describing the relationship between things. Graphs don’t really have to represent a way to get to a place. That’s a kind of graph, but you could have graphs that only just say that something is related to another thing.


A node is a unit of data, it could be used to represent anything. In programming terms, it could be an object. Nodes are also called Vertices.


An edge is a connection between 2 nodes. An edge can be visualized as the relationship between things.

Neighbour Nodes#

A Neighboring node is a node that is connected to the current node by an edge.

Types of Graphs#

Directed Graphs#

A directed graph shows the direction of the relationship between nodes. You can only travel in the direction that is shown on the graph.

Undirected Graphs#

These are graphs wherein the direction has no importance. So you can travel in any direction and the relationship is the same.

Representation of Graphs#

An adjacency list (something like a hashmap) is used to repesent a graph. It shows how each node is related to other nodes.

```json {

“a”: [“b”, “c”], “b”: [“d”], “c”: [“e”], “d”: [], “e”: [“b”], “f”: [“d”]

Graph Traversals#

Traversal of a graph is a way of moving around in a graph.

Depth First Traversal#


This uses a stack.