Types of Graphs: Key Graph Structures Explained

Graphs are data structures made of nodes (vertices) connected by edges. Common types include undirected graphs where edges have no direction, directed graphs where edges point from one node to another, and weighted graphs where edges carry values like distances or costs.

Syntax

A graph is defined by a set of vertices and a set of edges. Each edge connects two vertices.

• Undirected graph: Edges have no direction, represented as pairs (u, v).
• Directed graph (digraph): Edges have direction, represented as ordered pairs (u → v).
• Weighted graph: Edges have weights or costs, represented as (u, v, w) where w is the weight.

python

class Graph:
    def __init__(self):
        self.vertices = set()
        self.edges = dict()  # key: vertex, value: list of connected vertices or (vertex, weight)

    def add_vertex(self, v):
        self.vertices.add(v)
        if v not in self.edges:
            self.edges[v] = []

    def add_edge(self, u, v, weight=None, directed=False):
        self.add_vertex(u)
        self.add_vertex(v)
        if weight is None:
            self.edges[u].append(v)
        else:
            self.edges[u].append((v, weight))
        if not directed:
            if weight is None:
                self.edges[v].append(u)
            else:
                self.edges[v].append((u, weight))

Example

This example creates an undirected weighted graph with three nodes and edges with weights representing distances.

python

class Graph:
    def __init__(self):
        self.vertices = set()
        self.edges = dict()

    def add_vertex(self, v):
        self.vertices.add(v)
        if v not in self.edges:
            self.edges[v] = []

    def add_edge(self, u, v, weight=None, directed=False):
        self.add_vertex(u)
        self.add_vertex(v)
        if weight is None:
            self.edges[u].append(v)
        else:
            self.edges[u].append((v, weight))
        if not directed:
            if weight is None:
                self.edges[v].append(u)
            else:
                self.edges[v].append((u, weight))

    def display(self):
        for v in self.vertices:
            print(f"{v}: {self.edges[v]}")

# Create graph
graph = Graph()
graph.add_edge('A', 'B', weight=5)
graph.add_edge('B', 'C', weight=3)
graph.add_edge('A', 'C', weight=10)

graph.display()

Output

A: [('B', 5), ('C', 10)]
B: [('A', 5), ('C', 3)]
C: [('B', 3), ('A', 10)]

Common Pitfalls

One common mistake is confusing directed and undirected edges, which changes how connections are stored and traversed.

Another is forgetting to add vertices before edges, causing errors or missing nodes.

Also, mixing weighted and unweighted edges without clear handling can cause bugs.

python

# Wrong: Adding edge without adding vertices explicitly
class GraphWrong:
    def __init__(self):
        self.edges = dict()

    def add_edge(self, u, v):
        # This will fail if u or v not in edges
        self.edges[u].append(v)

# Right: Add vertices before edges
class GraphRight:
    def __init__(self):
        self.vertices = set()
        self.edges = dict()

    def add_vertex(self, v):
        self.vertices.add(v)
        if v not in self.edges:
            self.edges[v] = []

    def add_edge(self, u, v):
        self.add_vertex(u)
        self.add_vertex(v)
        self.edges[u].append(v)

Quick Reference

• Undirected graph: Edges connect nodes both ways, no direction.
• Directed graph: Edges have a direction from one node to another.
• Weighted graph: Edges carry a value like cost or distance.
• Simple graph: No loops or multiple edges between same nodes.
• Complete graph: Every node connects to every other node.

Key Takeaways

Graphs consist of vertices (nodes) and edges (connections) that can be directed or undirected.

Weighted graphs assign values to edges to represent costs or distances.

Always add vertices before edges to avoid errors in graph construction.

Understand the difference between directed and undirected graphs for correct traversal.

Common graph types include simple, complete, directed, undirected, and weighted graphs.