Directed vs undirected graphs in Data Structures Theory - Key Differences Explained

Introduction

Imagine you want to show connections between places or people. Sometimes the connection goes both ways, and sometimes it only goes one way. Understanding these two types of connections helps us model many real-world problems.

Explanation

Undirected Graphs

In an undirected graph, connections between points (called nodes) have no direction. This means if node A is connected to node B, you can move from A to B and also from B to A freely. These graphs are useful when relationships are mutual, like friendships or roads where traffic flows both ways.

Undirected graphs represent two-way, mutual connections between nodes.

Directed Graphs

Directed graphs have connections that go one way only. Each connection has a direction, like an arrow from one node to another. This shows that you can move from the start node to the end node, but not necessarily back. Directed graphs model situations like one-way streets or follower relationships on social media.

Directed graphs represent one-way connections with a clear direction from one node to another.

Edges and Arrows

In undirected graphs, connections are called edges and are shown as simple lines between nodes. In directed graphs, connections are called arcs or directed edges and are shown as arrows pointing from one node to another. This visual difference helps quickly understand the type of relationship.

Edges in undirected graphs are lines; in directed graphs, they are arrows showing direction.

Use Cases

Undirected graphs are used when relationships are mutual, like in social networks where friendship is two-way. Directed graphs are used when relationships have direction, like web page links or task dependencies where one task must happen before another.

Choosing directed or undirected graphs depends on whether relationships are one-way or two-way.

Real World Analogy

Think of a neighborhood with streets. Some streets allow cars to go both ways, like undirected connections. Other streets are one-way, allowing cars to go only in one direction, like directed connections.

Undirected Graphs → Two-way streets where cars can travel back and forth freely

Directed Graphs → One-way streets where cars can only travel in the direction of the arrow

Edges and Arrows → Lines for two-way streets and arrows for one-way streets on a map

Use Cases → Choosing street types based on traffic rules and flow needs

Diagram

Diagram

  Undirected Graph       Directed Graph

  A─────B               A ──▶ B
   \   /                 
    C                   C     
                         

This diagram shows an undirected graph with lines connecting nodes both ways, and a directed graph with arrows showing one-way connections.

Key Facts

Undirected Graph → A graph where edges have no direction and connections are mutual.

Directed Graph → A graph where edges have a direction, showing one-way connections.

Edge → A connection between two nodes in an undirected graph.

Arc → A directed edge with a specific direction from one node to another.

Use Case → The practical situation where a directed or undirected graph is applied.

Code Example

Data Structures Theory

class Graph:
    def __init__(self, directed=False):
        self.directed = directed
        self.adj_list = {}

    def add_node(self, node):
        if node not in self.adj_list:
            self.adj_list[node] = []

    def add_edge(self, start, end):
        self.add_node(start)
        self.add_node(end)
        self.adj_list[start].append(end)
        if not self.directed:
            self.adj_list[end].append(start)

    def display(self):
        for node, neighbors in self.adj_list.items():
            print(f"{node} -> {neighbors}")

# Undirected graph example
g1 = Graph(directed=False)
g1.add_edge('A', 'B')
g1.add_edge('A', 'C')
g1.display()

print('---')

# Directed graph example
g2 = Graph(directed=True)
g2.add_edge('A', 'B')
g2.add_edge('A', 'C')
g2.display()

Common Confusions

Believing that undirected graphs can represent one-way relationships.

Believing that undirected graphs can represent one-way relationships. Undirected graphs always represent two-way connections; one-way relationships require directed graphs.

Thinking that edges and arcs are the same in all graphs.

Thinking that edges and arcs are the same in all graphs. Edges are undirected connections, while arcs are directed and show a clear direction.

Summary

Undirected graphs show two-way connections where movement is possible in both directions.

Directed graphs show one-way connections with arrows indicating direction from one node to another.

Choosing between directed and undirected graphs depends on whether relationships are mutual or one-sided.

Practice

1. Which of the following best describes a directed graph?

easy

A. Edges have a direction from one vertex to another

B. Edges connect vertices without any direction

C. Edges are weighted but have no direction

D. Edges connect only vertices of the same type

Solution

1. Step 1: Understand edge direction in graphs

   Directed graphs have edges that point from one vertex to another, showing direction.

2. Step 2: Compare with undirected graphs

   Undirected graphs have edges without direction, connecting vertices both ways equally.

3. Final Answer:

   Edges have a direction from one vertex to another -> Option A

4. Quick Check:

   Directed graph = edges with direction [OK]

Hint: Directed means edges point one way only [OK]

Common Mistakes:

• Confusing directed with weighted edges
• Thinking undirected edges have direction
• Assuming all graphs have directions

2. Which of the following is the correct way to represent an undirected edge between vertices A and B?

easy

A. (A → B) only

B. (A, B) only

C. (B, A) only

D. (A, B) and (B, A) both included

Solution

1. Step 1: Understand undirected edge representation

   Undirected edges connect two vertices both ways, so both (A, B) and (B, A) are included.

2. Step 2: Compare with directed edge representation

   Directed edges include only one direction, like (A → B), not both.

3. Final Answer:

   (A, B) and (B, A) both included -> Option D

4. Quick Check:

   Undirected edge = both directions stored [OK]

Hint: Undirected edges need both directions listed [OK]

Common Mistakes:

• Listing only one direction for undirected edges
• Confusing directed arrow notation with undirected
• Assuming undirected edges are stored once only

3. Given the directed graph edges: [(1, 2), (2, 3), (3, 1)], what is the result of checking if there is a path from vertex 3 to vertex 2?

medium

A. Only if the graph is undirected

B. Yes, there is a path

C. No, there is no path

D. Cannot determine without weights

Solution

1. Step 1: Analyze edges for path from 3 to 2

   Edges are (1 → 2), (2 → 3), (3 → 1). From 3, you can go to 1 only.

2. Step 2: Check if path leads to 2

   From 3 to 1, then from 1 to 2 is possible, so path exists: 3 → 1 → 2.

3. Final Answer:

   Yes, there is a path -> Option B

4. Quick Check:

   Path 3->1->2 exists [OK]

Hint: Follow edges direction step-by-step [OK]

Common Mistakes:

• Ignoring indirect paths
• Assuming no path if direct edge missing
• Confusing directed with undirected paths

4. Identify the error in this undirected graph edge list representation: edges = [(1, 2), (2, 3), (3, 1)] used as is for an undirected graph.

medium

A. Edges should be duplicated in reverse order

B. Edges must be tuples of length 3

C. Edges cannot connect vertex 3 to 1

D. No error, this is correct

Solution

1. Step 1: Understand undirected edge storage

   Undirected edges require both (u, v) and (v, u) to represent two-way connection.

2. Step 2: Check given edge list

   Edges are only listed one way, missing reverse edges like (2, 1), (3, 2), (1, 3).

3. Final Answer:

   Edges should be duplicated in reverse order -> Option A

4. Quick Check:

   Undirected edges need both directions [OK]

Hint: Undirected edges must appear both ways [OK]

Common Mistakes:

• Assuming one direction is enough
• Thinking tuples need 3 elements
• Believing given list is complete

5. You want to model a social network where friendships are mutual. Which graph type should you use and why?

hard

A. Directed graph, to track who follows whom

B. Directed graph, because friendships have direction

C. Undirected graph, because friendships go both ways

D. Weighted graph, to show friendship strength

Solution

1. Step 1: Understand the nature of friendships

   Mutual friendships mean if A is friend with B, then B is friend with A.

2. Step 2: Choose graph type matching mutual connections

   Undirected graphs represent mutual connections naturally, with edges having no direction.

3. Final Answer:

   Undirected graph, because friendships go both ways -> Option C

4. Quick Check:

   Mutual relations = undirected graph [OK]

Hint: Mutual means undirected edges [OK]

Common Mistakes:

• Choosing directed graph for mutual relations
• Confusing following with friendship
• Ignoring edge direction meaning