Graph

A Graph is a data structure consisting of vertices (nodes) and edges (connections between nodes). It is used to represent relationships between objects.

Terminology

• Vertex (Node): An entity in the graph.
• Edge: A connection between vertices.
• Directed: Edges have a direction (one-way).
• Undirected: Edges have no direction (two-way).
• Weighted: Edges have values/weights.
• Unweighted: Edges have no weights.
• Dense: Many edges, approaching V².
• Sparse: Few edges, approaching V.

Real-World Examples

Basic Representation

# Simple graph using a dictionary
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

Key Terminology

• Degree: The number of edges connected to a vertex.
• Path: A route from one vertex to another.
• Cycle: A path that returns to its starting vertex.
• Connected: All vertices can reach one another.
• Subgraph: A part of a graph.

# Weighted graph
weighted_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 3)],
    'C': [('A', 2), ('D', 5)],
    'D': [('B', 3), ('C', 5)]
}

Types of Graph

When to Use a Graph

• Solving navigation/routing problems
• Social network analysis
• Dependency resolution (build systems)
• Flow analysis (network flow)
• State machines

# Dependency graph (DAG)
dependencies = {
    'main.py': ['config.py', 'database.py'],
    'config.py': [],
    'database.py': ['config.py'],
    'models.py': ['database.py']
}

Graphs have many variations and algorithms. Let's study how to represent them in detail.