Directed and Undirected Graphs — the backbone of everything from Google Maps to "who blocked whom" in your group chat.

Whether you're navigating a course registration system, coding a social network, or building a bus route planner for the frozen kingdom of USask, graphs are everywhere — and understanding the difference between directed and undirected graphs is a must if you don’t want your algorithms to cry in O(n²).

---

Directed vs Undirected Graphs: The Social Dynamics of Computer Science

“A directed graph is when I message you first.
An undirected graph is when we both pretend we messaged each other at the same time.”
— University of Saskatchewan Philosophy, Algorithms Division

Let’s break this down like we’re building connections — literally.

---

🧭 What Is a Graph (in CS terms)?

A graph is a data structure made up of:

• Vertices (nodes) → the “people” or “places”

• Edges (connections) → the relationships between them

Think of it like:

• 🧑 Nodes = people at USask

• 🕸️ Edges = who follows who on Instagram

But here’s the kicker: the direction of the edge changes everything.

---

🔁 Undirected Graphs: The Mutual Vibes

“If I’m connected to you, you’re connected to me.”

In an undirected graph, the edge between two nodes doesn’t have direction. It’s a two-way relationship.

Real-world examples:

• Facebook friends

• Shared bus stops

• Two-way streets

• Group projects where everyone contributes (lol)

In code (Java-style pseudocode):

java
CopyEdit
graph.addEdge("Alice", "Bob"); // Alice <--> Bob

Here, both Alice and Bob list each other as neighbors.

Properties:

• Each edge is bidirectional

• Degree of a node = number of connections

• Often represented with symmetric adjacency matrices

---

➡️ Directed Graphs: The One-Way Energy

“I follow you, but you don’t follow me back. Pain.”

In a directed graph (or digraph), edges have direction — like arrows from one node to another.

Real-world examples:

• Twitter follows

• One-way streets

• Prerequisite courses (e.g., CMPT 141 → CMPT 270)

• Supply chain logistics

• USask TA emails that never get a reply

Java-style:

java
CopyEdit
graph.addDirectedEdge("Alice", "Bob"); // Alice → Bob

Now, Alice follows Bob, but unless you add the reverse edge, Bob does not follow Alice.

Properties:

• Edges are ordered pairs

• Nodes have in-degree and out-degree

• Often used in algorithms like topological sort, Dijkstra’s, and strongly connected components

---

🧠 Key Differences (Let’s TL;DR It Real Quick)

---

🧪 When to Use What (Real CS Scenarios)

✅ Use Undirected Graphs when:

• Relationships are inherently mutual

• You’re modeling non-hierarchical structures

• Performance doesn't need strict directionality

Examples:

• Physical road networks

• Collaboration networks

• Maze generation algorithms

---

✅ Use Directed Graphs when:

• You need to represent cause and effect

• There's a flow or hierarchy involved

• You want to track influence or data direction

Examples:

• Course prerequisites

• Call graphs in Java programs

• Task dependencies in project planning (hello, Agile boards)

---

📐 Representing Graphs in Java

Let’s throw some quick Java-style code snippets at the wall.

Undirected Graph using Adjacency List:

java
CopyEdit
Map<String, List<String>> graph = new HashMap<>();
graph.putIfAbsent("A", new ArrayList<>());
graph.putIfAbsent("B", new ArrayList<>());

graph.get("A").add("B");
graph.get("B").add("A"); // Mirror edge for undirected

Directed Graph:

java
CopyEdit
graph.get("A").add("B"); // No reverse edge

Using a Graph Class:

java
CopyEdit
class Graph {
    Map<String, List<String>> adjList = new HashMap<>();
    boolean isDirected;

    void addEdge(String src, String dest) {
        adjList.putIfAbsent(src, new ArrayList<>());
        adjList.get(src).add(dest);

        if (!isDirected) {
            adjList.putIfAbsent(dest, new ArrayList<>());
            adjList.get(dest).add(src);
        }
    }
}

---

🧪 Graphs in Real-World Systems (aka "This Isn't Just Theory")

• Map apps: Directed graph with weights (e.g. Google Maps)

• Compiler optimizations: DAGs (Directed Acyclic Graphs)

• Dependency graphs: Managing your Java project’s class dependencies

• Social networks: Different graph types based on platform

You think you’re not using graphs daily?
Your computer thinks otherwise.

---

😅 Common Mistakes in Graph Problems

• Treating directed edges as undirected (ouch)

• Forgetting to initialize nodes before adding edges

• Confusing in-degree with out-degree

• Not checking for cycles in directed graphs (especially in topological sort problems — RIP)

---

🧠 TL;DR (Too Lazy, Didn’t Traverse)

• Undirected Graph: mutual connections (Alice ↔ Bob)

• Directed Graph: one-way connections (Alice → Bob)

• Use directed graphs when modeling flow, influence, or order

• Use undirected graphs when relationships are inherently mutual

• Java loves adjacency lists (for performance + clarity)

---

🎓 Final Thoughts From the Algorithm Abyss

Understanding the difference between directed and undirected graphs is like understanding the difference between:

• A group project (undirected)

• A prof emailing you but not replying to you (directed)

Once you know the rules of connection, everything else in graph theory starts to make sense — shortest path, DFS, BFS, cycles, topological sorting... all of it.

So yeah. Graphs. They slap. Learn them. Love them. Traverse them.