Skip to main content

​
What is a Graph?

A graph is a data structure consisting of vertices (nodes) and edges (connections between nodes). Graphs are fundamental for representing relationships and networks in computer science, from social networks to road maps to dependency systems.
UCX DSA provides comprehensive graph implementations supporting both adjacency matrix and adjacency list representations, with support for directed/undirected and weighted/unweighted graphs.

​
Graph Components

Vertices

Nodes in the graph that represent entities. In UCX DSA, vertices are identified by string labels.

Edges

Connections between vertices. Edges can be directed (one-way) or undirected (two-way).

Weights

Optional numeric values assigned to edges representing cost, distance, or other metrics.

Neighbors

Vertices directly connected to a given vertex through an edge.

​
Graph Types

​
Directed vs Undirected

In a directed graph, edges have a direction. An edge from vertex A to vertex B does not imply an edge from B to A.Use Cases:
  • Web page links
  • Social media followers (following relationship)
  • Task dependencies
  • One-way streets in a road network
from dsa.graph import Graph

# Create a directed graph
g = Graph.create('adjacency_list', directed=True)
g.add_edge('A', 'B')  # A → B
g.add_edge('B', 'C')  # B → C

# A can reach B, but B cannot reach A (unless explicitly added)
print(g.has_edge('A', 'B'))  # True
print(g.has_edge('B', 'A'))  # False

​
Weighted vs Unweighted

In a weighted graph, each edge has an associated numeric value (weight) representing cost, distance, capacity, or other metrics.Use Cases:
  • Road networks with distances
  • Flight routes with costs
  • Network flow problems
  • Shortest path algorithms
from dsa.graph import Graph

# Create a weighted graph
g = Graph.create('adjacency_list', weighted=True)
g.add_edge('A', 'B', 5)   # Edge with weight 5
g.add_edge('B', 'C', 10)  # Edge with weight 10
g.add_edge('A', 'C', 3)   # Edge with weight 3

# Get edge weight
weight = g.get_weight('A', 'B')  # Returns 5

​
Graph Representations

UCX DSA supports two primary graph representations:

Adjacency Matrix

A 2D matrix where cell (i, j) indicates if there’s an edge from vertex i to vertex j.Pros:
  • O(1) edge lookup
  • Good for dense graphs
  • Simple to implement
Cons:
  • O(V²) space complexity
  • Inefficient for sparse graphs

Adjacency List

Each vertex stores a list of its adjacent vertices.Pros:
  • O(V + E) space complexity
  • Efficient for sparse graphs
  • Fast neighbor iteration
Cons:
  • O(degree) edge lookup
  • More complex structure

​
Graph Terminology

TermDefinition
OrderThe number of vertices in the graph
SizeThe number of edges in the graph
DegreeThe number of edges connected to a vertex
PathA sequence of vertices where each consecutive pair is connected by an edge
CycleA path that starts and ends at the same vertex
ConnectedA graph where there’s a path between every pair of vertices
AdjacencyTwo vertices are adjacent if they’re connected by an edge

​
Common Graph Operations

All graph implementations in UCX DSA support these core operations: 
from dsa.graph import Graph

# Create a graph (example with adjacency list)
g = Graph.create('adjacency_list', directed=False)

# Add vertices
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')

# Add edges
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('A', 'C')

# Query the graph
print(f"Vertices: {g.vertices()}")  # ['A', 'B', 'C']
print(f"Edges: {g.edges()}")        # [('A', 'B'), ('B', 'C'), ...]
print(f"Order: {g.order()}")        # 3 vertices
print(f"Size: {g.size()}")          # 3 edges

# Check existence
print(g.has_vertex('A'))      # True
print(g.has_edge('A', 'B'))   # True

# Get neighbors
print(g.adjacents('A'))       # ['B', 'C']
print(g['A'])                 # ['B', 'C'] (using indexing)

# Delete operations
g.delete_edge('A', 'C')
g.delete_vertex('B')

​
Choosing a Graph Type

Use this guide to choose the right graph implementation:
Choose adjacency matrix when:
  • The graph is dense (many edges)
  • You need O(1) edge existence checks
  • You have a fixed number of vertices
  • Memory is not a primary concern
  • You need to frequently check if edges exist
Choose adjacency list when:
  • The graph is sparse (few edges)
  • You need to iterate over neighbors frequently
  • The number of vertices may change
  • Memory efficiency is important
  • You’re implementing graph traversal algorithms
Choose weighted graphs when:
  • Edges have associated costs or distances
  • You’re implementing shortest path algorithms (Dijkstra, Bellman-Ford)
  • You need to optimize routes or flows
  • You’re working with network capacity problems
Choose directed graphs when:
  • Relationships are one-way
  • You’re modeling dependencies or hierarchies
  • You need to represent asymmetric relationships
  • You’re implementing topological sorting

​
Graph Traversal

UCX DSA provides two fundamental graph traversal algorithms:

Breadth-First Search (BFS)

Explores neighbors level by level. Useful for finding shortest paths in unweighted graphs.

Depth-First Search (DFS)

Explores as far as possible along each branch before backtracking. Useful for cycle detection and topological sorting.

​
Quick Start Example

from dsa.graph import Graph
from dsa.graph_traversal import bfs, dfs

# Create a social network graph
social = Graph.create('adjacency_list', directed=False)

# Add friendships
friendships = [
    ('Alice', 'Bob'),
    ('Alice', 'Charlie'),
    ('Bob', 'David'),
    ('Charlie', 'David'),
    ('David', 'Eve')
]

for person1, person2 in friendships:
    social.add_edge(person1, person2)

# Find Alice's friends
print(f"Alice's friends: {social['Alice']}")

# Check if two people are friends
if social.has_edge('Alice', 'Bob'):
    print("Alice and Bob are friends")

# Find all people reachable from Alice using BFS
reachable = bfs(social, 'Alice')
print(f"Alice can reach: {reachable}")

# Find network size
print(f"Network has {social.order()} people")
print(f"Network has {social.size()} friendships")

​
Next Steps

Graph Factory

Learn how to create different types of graphs using the Graph factory class

Adjacency Matrix

Explore matrix-based graph implementations

Adjacency List

Explore list-based graph implementations

Graph Traversal

Learn BFS and DFS algorithms for graph traversal

Build docs developers (and LLMs) love

Get started for freeTalk to us