DSA Graphs
A graph is a data structure made of vertices and edges that models connections between objects, from social networks to road maps.
What Is a Graph?
A graph is a collection of vertices (also called nodes) together with edges that connect pairs of them. Unlike a list or a tree, a graph places no restriction on how many connections a vertex can have, which makes it the natural way to model networks: people and friendships, cities and roads, web pages and hyperlinks, or computers and network cables.
- Vertex (node): a single unit in the graph, such as a person, city, or web page.
- Edge: a connection between two vertices, such as a friendship, road, or hyperlink.
- Adjacent / neighbor: two vertices that are directly connected by an edge.
- Degree: the number of edges touching a vertex (split into in-degree and out-degree for directed graphs).
- Path: a sequence of edges leading from one vertex to another without repeating a vertex.
- Cycle: a path that starts and ends at the same vertex.
Example 1: An Undirected Graph as an Adjacency List
class Graph:
def __init__(self):
self.adjacency_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacency_list:
self.adjacency_list[vertex] = []
def add_edge(self, v1, v2):
self.add_vertex(v1)
self.add_vertex(v2)
self.adjacency_list[v1].append(v2)
self.adjacency_list[v2].append(v1) # undirected: add both directions
# Build a small social network graph
graph = Graph()
graph.add_edge("Alice", "Bob")
graph.add_edge("Alice", "Cara")
graph.add_edge("Bob", "Cara")
print(graph.adjacency_list)
# {'Alice': ['Bob', 'Cara'], 'Bob': ['Alice', 'Cara'], 'Cara': ['Alice', 'Bob']}
Directed vs. Undirected Graphs
In an undirected graph, an edge represents a two-way connection: if Bob is a friend of Alice, Alice is a friend of Bob. In a directed graph, an edge points only one way, so a connection from A to B does not imply a connection from B to A. Directed graphs are used for one-way relationships such as 'follows' on a social network, prerequisite chains between courses, or one-way streets. Each vertex in a directed graph has an in-degree (edges pointing to it) and an out-degree (edges pointing away from it).
Example 2: A Directed Graph and In-Degree
class DirectedGraph:
def __init__(self):
self.adjacency_list = {}
def add_vertex(self, vertex):
self.adjacency_list.setdefault(vertex, [])
def add_edge(self, source, destination):
self.add_vertex(source)
self.add_vertex(destination)
self.adjacency_list[source].append(destination) # one-way only
def in_degree(self, vertex):
return sum(1 for neighbors in self.adjacency_list.values() if vertex in neighbors)
# Model a "follows" network like Twitter
follows = DirectedGraph()
follows.add_edge("amy", "ben")
follows.add_edge("cleo", "ben")
follows.add_edge("ben", "amy")
print(follows.adjacency_list)
# {'amy': ['ben'], 'ben': ['amy'], 'cleo': ['ben']} - ben never lists cleo back
print("in-degree of ben:", follows.in_degree("ben")) # 2
Weighted Graphs
An edge can also carry a weight: a number representing cost, distance, time, or capacity. A road network is naturally weighted by distance in kilometers; a computer network might be weighted by latency in milliseconds. A graph with no explicit weight is usually treated as if every edge has weight 1, which is why algorithms like BFS can find 'shortest paths' purely by counting edges.
Example 3: A Weighted Graph
class WeightedGraph:
def __init__(self):
self.adjacency_list = {}
def add_vertex(self, vertex):
self.adjacency_list.setdefault(vertex, [])
def add_edge(self, v1, v2, weight):
self.add_vertex(v1)
self.add_vertex(v2)
self.adjacency_list[v1].append((v2, weight))
self.adjacency_list[v2].append((v1, weight))
# Roads between towns, weight = distance in km
roads = WeightedGraph()
roads.add_edge("Springfield", "Riverside", 12)
roads.add_edge("Riverside", "Fairview", 7)
roads.add_edge("Springfield", "Fairview", 20)
total_weight = sum(w for edges in roads.adjacency_list.values() for _, w in edges) // 2
print("Total road distance:", total_weight, "km") # 39 km
Exercise: DSA Graphs
What are the two primary components used to define a graph?
