An introduction to graphs and graph theory
What is a graph? You may be thinking of a functional graph (the kind you see in math). But the graphs that appear in graph theory, a popular computer science domain with millions of applications, are wildly different.
Here is one example of a graph in CS:
Looks weird? Let’s talk about its components. A graph theory graph is a collection of nodes (the circles) connected by edges (the lines). One typical graph task is graph traversal, where you move from one node to the next via an edge connecting them.
Special Graphs
First, graphs can have different types of edges. A bidirectional edge connects nodes both ways; if a bidirectional edge connects nodes A and B, you can use a bidirectional edge to traverse from A to B or from B to A. In contrast, a directed edge only allows traversal in the arrow’s direction. If a directional edge goes from A to B, you can only travel from A to B.
Certain types of graphs have unique properties that make them useful in particular domains. A tree is a graph where every node is connected, and if there are N nodes, there are also exactly N-1 edges. You can think of a tree as having started from a single node, and every new node is added to the tree using a single edge. Trees have been heavily studied and have an expansive set of algorithms. We encourage you to google additional information, as they are outside the scope of this event. A directed acyclic graph (or DAG) is another type of graph. “Directed” means it only has directed edges, and “acyclic” means there are no cycles in the graph-- there is no way to reach the same node twice using graph traversal. DAGs also have a lot of unique properties (one of which you can read about in the "Google Maps" article).
Note: These are only two specific types of graphs. We encourage everyone to google additional information if interested. Some examples include a null graph, trivial graph, non-directed graph, complete graph, wheel graph, and many more!
So what is the purpose of graphs? They are helpful in a wide array of computing problems ranging from finding the shortest path from one place to another (Dijkstra’s algorithm) to sorting and updating a set of numbers (balanced binary search tree). Understanding graphs can make learning the frameworks and programs that our world runs on much more manageable. In addition, understanding graphs make the following modules on this website much more understandable!
Join our discord server for updates, announcements, future event planning, to ask questions, or just for fun!
Copyright ©2021 Howard County Hour of Code