Graphs
A graph is a data structure made of nodes connected to other nodes. Unlike trees, graphs can form cycles.
Graph Terminology
- Node/Vertex: An object that stores data and links to child nodes/vertices.
- Edge: A link between two nodes.
- Adjacent nodes: Two nodes connected by an edge.
- Directed graphs: Edges in directed graphs only point in one direction.
- Undirected graphs: Edges in undirected graphs point both ways.
Graph Representation
In code, there are two main ways of representing graphs. Graphs can be represented as adjacency lists or adjacency matrices.
Adjacency List
In an adjacency list, the graph is stored as a list of nodes. Each individual node contains a list of its adjacent nodes.
Adjacency Matrix
In an adjacency matrix, the graph is represented as a 2D array of boolean values. If \(graph[i][j] == true\), then node \(i\) has an edge to node \(j\).
More Resources
Below are some more resources to learn about graphs:
Written on August 2, 2021