Graphs
A tree is actually a type of graph, but not all graphs are trees. Simply put, a tree is a connected graphs without cycles.
A graph is simply a collection of nodes with edges between (some of) them
- graphs can be either directed (like the following graph) or undirected. While directed edges are like a one-way street, undirected edges are like a two-way street.
- The graph might consist of multiple isolated subgraphs. If there is a path between every pair of vertices, it is called a “connected graph”
- the graph can also have cycles. An “acyclic graph” is one without cycles
Adjacency List
This is the most common way to represent a graph. Every vertes(or node) stores a list of adjacent vertices. In an undirected graph, an edge like(a,b) would be stored twice : once in a’s adjacent vertices and once in b’s adjacent vertices.
- In order to implement of simple graph, the graph class is used because, unlike in a tree, you can’t necessarily reach all the nodes from a single node. You don’t necessarily need any additional classes to represent a graph. An array(or a hash table) of lists(arrays, arraylists, linked lists, etc.) can store the adjacency list.
But it isn’t quite as clean. We tend to use node classes unless there’s a compelling reason not to.
Adjacency matrices
An adjacency matrix is an NxN boolean matrix (where N is the number of nodes), where a true value at matrix[i][j] indecates an edge from node i to node j( you can also use an integer matrix with 0s and 1s.)
In an undirected graph, an adjacency matrix will be symmetric. In a directed graph, it will not(necessarily)be.
