Intro
Graphs are an AbstractDataType representing a collection of vertices (nodes) connected by edges (links). A common and simple example is to visualize a map as a series of nodes (locations) connected by edges (routes or paths).
It’s a great way of visualizing relationships between different items and/or values.
Trees
Acyclic graphs, graphs that don’t form a cycle in which we can traverse all over the graph back to the starting point, are known as Trees. Because they have a starting node, known as the Root.
Definition
Mathematically a Graph is represented as an ordered pair where
- is a set of vertices (also called nodes or points).
- is a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with two distinct vertices).
Types
There’s quite a few types of graphs, the ones that are worth your attention are:
- Connected graph: a graph where there is a path available between any two vertices. // no disjointed nodes sitting alone
- Cyclic graph: a graph containing at least one cycle
- Acyclic graph: a graph containing no cycles
- Tree: any connected + acyclic graph
- Complete graph: every pair of vertices is connected by an edge
- Weighted graph: every edge has an associated value.
A type of graph that’s very relevant in Comp Sci is the DirectedGraph.
Directed Graphs (DAG)
These are graphs where the edges are directional and move in a single direction. Directed Acyclic graphs are acyclic DAGs, meaning no cycles.
DAGs are commonly utilized in Topological Sort problems.
Topological Sort
TopoSort refers to problems that are comprised of various tasks, each with its own set of dependencies that need to be completed first. Tasks depend on prerequisite tasks, can’t do B until completed A. So need to find a linear ordering of the tasks that satisfies all dependencies.
An example of Topo Sort is the Getting Dressed problem