A graph consists of vertices (or nodes) and edges (or paths)
Edges
- are connections between vertices
- e.g., roads between cities
- can have one-way direction or can be bidirectional
- can have weights
- e.g., time to travel between two cities
A directional graph has edges that are all directional (i.e., if there's an edge from A to B, there might not be one from B to A)
An acyclic graph contains no cycles (in a directed graph, there's no path starting from some vertex v that will take you back to v)
A weighted graph contains edges that hold a numerical value (e.g., cost, time, etc.)
A complete graph is a graph where each vertex has an edge to all other vertices in the graph
There are two main ways to represent a graph:
- Adjacency matrix
- Adjacency list
An adjacency matrix uses a 2-dimensional array to represent edges between two vertices
There are many ways to use an adjacency matrix to represent a matrix, but we will look at two variations
Pros
- Easy to check if there is an edge between i and j
- calling
matrix[ i ][ j ]will tell us if there is a connection
- calling
Cons
- To find all neighbors of vertex i, you would need to check the value of
matrix[ i ][ j ]for all j - Need to construct a 2-dimensional array of size N x N
Rather than making space for all N x N possible edge connections, an adjacency list keeps track of the vertices that a vertex has an edge to.
We are able to do this by creating an array that contains ArrayLists holding the values of the vertices that a vertex is connected to.
Pros
- Saves memory by only keeping track of edges that a vertex has
- Efficient to iterate over the edges of a vertex
- Doesn't need to go through all N vertices and check if there is a connection
Cons
- Difficult to quickly determine if there is an edge between two vertices
A tree is a special kind of graph that exhibits the following properties:
- Acyclic graph
- N vertices with N-1 edges
The graphs above that we used for BFS and DFS were both trees.
Above is another example of a tree.