Trees and Graphs Definition video (10 minutes) (Spring 2021)
In computer science, the word graph refers to a set of nodes/vertices connected by edges/links.
The same meaning of graph shows up in Discrete mathematics and Graph theory. We are not talking about the x-axis/y-axis graphs, or the "stocks go up" type of graph.
A graph can be simply thought of as "things, with connections".
The things are called nodes, or vertices (we will use the word node in this class). For example, intersections in a city or people.
The connections are called edges. For example, roads between intersections or friend ships.
Graphs can be undirected, or directed.
Undirected graphs have edges that do not have a direction. This indicates a two-way relationship, like a two-way street in the city intersections example. You can travel from each node to the other.
Directed graphs have edges with direction. This indicates a one-way relationship, and the edge can only be traversed in a single direction, like a one-way street in the city intersections example.
Graphs can have cycles. A cycle means that there is a path in the graph from at least one node back to itself.
Cyclic graphs have cycles, like intersections in a city.
Acyclic graphs do not have cycles, like your family tree (where family members are nodes and the parent-child relationships are edges).
You can think of a computer's file system as a graph. From the root folder, down, each folder may contain multiple folders. Folders can be thought of as nodes.
A file system is an acyclic graph (ignoring symlinks), and has a tree-like structure of hierarchy.
For example, on a typical Linux file system, the "/" directories contains the "/bin", "/home", and "/etc" directories along with many others and "/home" will contain a directory for various users (e.g. "/home/mikel" on my laptop). Each of these directories is a node we can think of each connection as an edge.
Another example is the internet: Each website or page can be a node and every link to another website or page is an edge.
Thanks to Brian Foster for typing up the rough draft of these notes based on the lecture video.