Data Structures & AlgorithmsGraphs

What Is a Graph? Definition & Terminology

LevelBeginner

Duration50 mins

TopicGraphs

3 / 4

Endpoints, Adjacency, and Neighbors

The Vocabulary of Relationships

Graphs are fundamentally about relationships. The vertices are entities, but the interesting questions—shortest paths, connectivity, clustering—all arise from how vertices relate to each other through edges.

To reason about these relationships precisely, we need vocabulary. Terms like "adjacent," "neighbor," and "endpoint" may seem simple, but they form the linguistic foundation for describing graph structure, specifying algorithms, and proving theorems. This page builds your fluency in the language of graph relationships.

What You Will Learn

By the end of this page, you will understand what endpoints are, master the concept of adjacency between vertices, distinguish between neighbors and adjacency in directed graphs, and confidently use these terms when analyzing graph structure or implementing graph algorithms.

Endpoints of an Edge

Every edge in a graph connects exactly two vertices (or one vertex to itself in the case of a self-loop). These vertices are called the endpoints of the edge.

Formal Definition:

For an edge e = (u, v) (directed) or e = {u, v} (undirected):

u and v are the endpoints of edge e
Edge e is said to join or connect its endpoints
The endpoints are said to be incident to the edge

Directed Graph Terminology:

For a directed edge e = (u, v):

u is the tail, source, or origin of the edge
v is the head, target, or destination of the edge
We say the edge leaves u and enters v
The edge is outgoing from u and incoming to v

Converting Mermaid diagram...

Endpoint Terminology for Directed Edges
Edge	Tail (Source)	Head (Target)	Description
e₁ = (A, B)	A	B	Edge from A to B
e₂ = (B, C)	B	C	Edge from B to C
e₃ = (A, C)	A	C	Edge from A to C

Undirected Edges Have No Tail/Head

In undirected graphs, both endpoints play symmetric roles. There's no 'from' or 'to'—just 'connected.' We simply call them the two endpoints, without distinguishing source from target.

Adjacency Between Vertices

Adjacency is the fundamental relationship between vertices in a graph. Two vertices are adjacent if they are directly connected by an edge.

Formal Definition (Undirected):

In an undirected graph G = (V, E), vertices u and v are adjacent (or neighbors) if: $${u, v} \in E$$

In other words, there exists an edge with u and v as its endpoints.

Formal Definition (Directed):

In a directed graph G = (V, E):

v is adjacent to u if (u, v) ∈ E (edge from u to v)
u is adjacent from v if (v, u) ∈ E (edge from v to u)

Note the asymmetry: in directed graphs, "u is adjacent to v" and "v is adjacent to u" are different statements.

Undirected Adjacency

•Symmetric: If A is adjacent to B, then B is adjacent to A
•Single relationship: Just 'adjacent' or 'not adjacent'
•Edges: {A, B} = {B, A}
•Example: Friendships, road connections

Directed Adjacency

•Asymmetric: A adjacent to B doesn't imply B adjacent to A
•Two relationships: 'Adjacent to' vs 'adjacent from'
•Edges: (A, B) ≠ (B, A)
•Example: Following, hyperlinks, dependencies

adjacency-example

Adjacency Analysis

Undirected Graph:
  V = {A, B, C, D}
  E = {{A,B}, {B,C}, {B,D}}
 
  Adjacency relationships:
    A is adjacent to: B
    B is adjacent to: A, C, D
    C is adjacent to: B
    D is adjacent to: B
 
  Note: "A adjacent to B" ⟺ "B adjacent to A"
 
---
 
Directed Graph:
  V = {A, B, C, D}
  E = {(A,B), (B,C), (C,B), (B,D)}
 
  Adjacency relationships:
    From A: B is adjacent to A  (A → B exists)
    From B: C, D are adjacent to B  (B → C, B → D exist)
    From C: B is adjacent to C  (C → B exists)
    From D: nothing  (no outgoing edges)
 
  Note: B adjacent to C (B → C) AND C adjacent to B (C → B)
        But A adjacent to B (A → B) does NOT mean B adjacent to A
        (no B → A edge)

Neighbors and Neighborhood

Neighbors of a vertex are all vertices adjacent to it. The set of all neighbors is called the vertex's neighborhood.

Formal Definition (Undirected):

For a vertex v in an undirected graph G = (V, E), the neighborhood of v is: $$N(v) = {u \in V : {u, v} \in E}$$

The closed neighborhood includes v itself: $$N[v] = N(v) \cup {v}$$

Formal Definition (Directed):

For a vertex v in a directed graph:

Out-neighbors (successors): $$N^+(v) = {u \in V : (v, u) \in E}$$

In-neighbors (predecessors): $$N^-(v) = {u \in V : (u, v) \in E}$$

The out-neighbors are vertices you can reach in one step from v; in-neighbors are vertices that can reach v in one step.

Neighborhood Notation Summary
Notation	Name	Definition	Usage
N(v)	Open neighborhood	Vertices adjacent to v	Undirected graphs
N[v]	Closed neighborhood	N(v) ∪ {v}	When v should be included
N⁺(v)	Out-neighborhood	Vertices reachable from v	Directed graphs
N⁻(v)	In-neighborhood	Vertices that reach v	Directed graphs

neighborhood-code
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from typing import Set, Dict, List
 
class UndirectedGraph:
    """Graph with neighborhood operations."""
    
    def __init__(self):
        self.adj: Dict[str, Set[str]] = {}
    
    def add_vertex(self, v: str):
        if v not in self.adj:
            self.adj[v] = set()
    
    def add_edge(self, u: str, v: str):
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u].add(v)
        self.adj[v].add(u)
    
    def neighbors(self, v: str) -> Set[str]:
        """N(v): Open neighborhood - vertices adjacent to v."""
        return self.adj.get(v, set()).copy()
    
    def closed_neighborhood(self, v: str) -> Set[str]:
        """N[v]: Closed neighborhood - N(v) ∪ {v}."""
        result = self.neighbors(v)
        result.add(v)
        return result
    
    def are_adjacent(self, u: str, v: str) -> bool:
        """Check if u and v are neighbors."""
        return v in self.adj.get(u, set())
 
 
class DirectedGraph:
    """Directed graph with in/out neighborhood operations."""
    
    def __init__(self):
        self.out_adj: Dict[str, Set[str]] = {}  # v -> successors
        self.in_adj: Dict[str, Set[str]] = {}   # v -> predecessors
    
    def add_vertex(self, v: str):
        if v not in self.out_adj:
            self.out_adj[v] = set()
            self.in_adj[v] = set()
    
    def add_edge(self, u: str, v: str):
        """Add directed edge u → v."""
        self.add_vertex(u)
        self.add_vertex(v)
        self.out_adj[u].add(v)
        self.in_adj[v].add(u)
    
    def out_neighbors(self, v: str) -> Set[str]:
        """N⁺(v): Vertices reachable from v in one step."""
        return self.out_adj.get(v, set()).copy()
    
    def in_neighbors(self, v: str) -> Set[str]:
        """N⁻(v): Vertices that can reach v in one step."""
        return self.in_adj.get(v, set()).copy()
 
 
# Example usage
g = UndirectedGraph()
for edge in [("A", "B"), ("B", "C"), ("B", "D"), ("C", "D")]:
    g.add_edge(*edge)
 
print(f"N(B) = {g.neighbors('B')}")           # {A, C, D}
print(f"N[B] = {g.closed_neighborhood('B')}") # {A, B, C, D}
print(f"A adjacent to B? {g.are_adjacent('A', 'B')}")  # True
 
dg = DirectedGraph()
for u, v in [("A", "B"), ("B", "C"), ("C", "B"), ("B", "D")]:
    dg.add_edge(u, v)
 
print(f"N⁺(B) = {dg.out_neighbors('B')}")  # {C, D}
print(f"N⁻(B) = {dg.in_neighbors('B')}")   # {A, C}

Neighborhood Size = Degree

The number of neighbors of a vertex equals its degree: |N(v)| = deg(v). For directed graphs: |N⁺(v)| = out-degree(v) and |N⁻(v)| = in-degree(v). This connection makes neighborhood operations central to degree-based algorithms.

In-Degree and Out-Degree

In directed graphs, we distinguish between edges entering and leaving a vertex. This gives rise to two degree measures:

Out-Degree:

The out-degree of vertex v, denoted deg⁺(v) or out-deg(v), is the number of edges leaving v: $$\deg^+(v) = |{(v, u) : (v, u) \in E}| = |N^+(v)|$$

In-Degree:

The in-degree of vertex v, denoted deg⁻(v) or in-deg(v), is the number of edges entering v: $$\deg^-(v) = |{(u, v) : (u, v) \in E}| = |N^-(v)|$$

Total Degree:

Sometimes we care about the total number of edges incident to v: $$\deg(v) = \deg^+(v) + \deg^-(v)$$

Degree Types in Directed Graphs
Vertex Type	In-Degree	Out-Degree	Interpretation
Source	0	0	No incoming edges; starting point
Sink	0	0	No outgoing edges; terminal point
Isolated	0	0	No edges at all
Internal	0	0	Both incoming and outgoing edges

degree-analysis

Degree Example

Directed Graph:
  V = {A, B, C, D, E}
  E = {(A,B), (A,C), (B,C), (B,D), (C,D), (D,E)}
 
Degree Analysis:
  Vertex A:  in-deg = 0,  out-deg = 2  → Source
  Vertex B:  in-deg = 1,  out-deg = 2  → Internal
  Vertex C:  in-deg = 2,  out-deg = 1  → Internal
  Vertex D:  in-deg = 2,  out-deg = 1  → Internal
  Vertex E:  in-deg = 1,  out-deg = 0  → Sink
 
Verification (Directed Handshaking Lemma):
  Sum of in-degrees:  0 + 1 + 2 + 2 + 1 = 6
  Sum of out-degrees: 2 + 2 + 1 + 1 + 0 = 6
  Number of edges: 6 ✓
  
  Both sums equal |E| because each edge contributes 1 to one vertex's
  out-degree and 1 to another's in-degree.

Directed Handshaking Lemma

In a directed graph: Σ deg⁺(v) = Σ deg⁻(v) = |E|. Every edge has exactly one tail (contributing to out-degree) and one head (contributing to in-degree). This is the directed version of the handshaking lemma.

Adjacency in Real Applications

Understanding adjacency helps solve real-world problems by mapping domain concepts to graph operations:

Social Network Analysis:

Neighbors of a user = their friends/followers
High out-degree = follows many accounts
High in-degree = has many followers (influencer)
Users with shared neighbors = potential friend recommendations

Web Crawling:

Out-neighbors of a page = pages it links to
In-neighbors of a page = pages linking to it (backlinks)
Pages with high in-degree = authoritative sources

Dependency Management:

Out-neighbors of a package = packages it depends on
In-neighbors = packages that depend on it (dependents)
Updating a package requires notifying all in-neighbors

Neighbor Operations in Different Domains
Domain	N⁺(v) Meaning	N⁻(v) Meaning	Example Query
Twitter	Accounts v follows	v's followers	Who does Elon follow?
Web Graph	Pages v links to	Pages linking to v	Find all backlinks to a URL
Package Manager	Dependencies of v	Dependents of v	What breaks if we remove v?
Course Prerequisites	Courses v enables	Courses needed for v	What can I take after Calc?
City Traffic	Roads leaving v	Roads entering v	Which streets lead downtown?

Algorithm Design Insight

Many graph algorithms boil down to: 'For each vertex, examine its neighbors.' BFS explores neighbors level-by-level. DFS explores neighbors depth-first. PageRank propagates scores through neighbors. Understanding neighborhood operations is key to understanding graph algorithms.

Common Vertex Classifications

Based on their neighbor relationships, vertices are often classified into categories that reveal structural properties:

By Degree:

Isolated vertex: deg(v) = 0 — no neighbors at all
Leaf/Pendant vertex: deg(v) = 1 — exactly one neighbor
Hub vertex: Very high degree — connected to many others

By Direction (Directed Graphs):

Source: in-deg(v) = 0, out-deg(v) > 0 — starting point
Sink: in-deg(v) > 0, out-deg(v) = 0 — terminal point
Internal: Both in-deg and out-deg > 0

By Connectivity:

Cut vertex/Articulation point: Removal disconnects the graph
Bridge endpoint: Incident to an edge whose removal disconnects the graph

vertex-classification
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
from typing import List, Dict, Set, Tuple
from collections import defaultdict
 
def classify_vertices(edges: List[Tuple[str, str]], 
                      directed: bool = False) -> Dict[str, str]:
    """
    Classify vertices based on their degree properties.
    
    Returns a dictionary mapping vertex to its classification.
    """
    if directed:
        in_degree: Dict[str, int] = defaultdict(int)
        out_degree: Dict[str, int] = defaultdict(int)
        vertices: Set[str] = set()
        
        for u, v in edges:
            out_degree[u] += 1
            in_degree[v] += 1
            vertices.add(u)
            vertices.add(v)
        
        classification = {}
        for v in vertices:
            in_d = in_degree[v]
            out_d = out_degree[v]
            
            if in_d == 0 and out_d == 0:
                classification[v] = "isolated"
            elif in_d == 0:
                classification[v] = "source"
            elif out_d == 0:
                classification[v] = "sink"
            else:
                classification[v] = "internal"
        
        return classification
    
    else:  # Undirected
        degree: Dict[str, int] = defaultdict(int)
        
        for u, v in edges:
            degree[u] += 1
            degree[v] += 1
        
        classification = {}
        for v, d in degree.items():
            if d == 0:
                classification[v] = "isolated"
            elif d == 1:
                classification[v] = "leaf"
            elif d >= 5:  # Arbitrary threshold for "hub"
                classification[v] = "hub"
            else:
                classification[v] = "internal"
        
        return classification
 
# Example: Directed graph
directed_edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]
print("Directed graph classification:")
for v, cls in classify_vertices(directed_edges, directed=True).items():
    print(f"  {v}: {cls}")
# A: source, B: internal, C: internal, D: sink
 
# Example: Undirected graph (tree structure)
undirected_edges = [("A", "B"), ("B", "C"), ("B", "D"), ("B", "E"), 
                    ("B", "F"), ("B", "G")]
print("
Undirected graph classification:")
for v, cls in classify_vertices(undirected_edges, directed=False).items():
    print(f"  {v}: {cls}")
# A: leaf, B: hub, C-G: leaves

Sources and Sinks in DAGs

In Directed Acyclic Graphs (DAGs), sources and sinks are especially important. Every DAG has at least one source (vertex with no predecessors) and at least one sink (vertex with no successors). Topological sort algorithms often start from sources or end at sinks.

Second-Order Neighbors and Beyond

Sometimes we care about vertices that are farther than one hop away. This leads to the concept of k-hop neighborhoods:

Second-Order Neighbors (2-hop):

The 2-hop neighborhood of v includes all vertices reachable in exactly 2 steps: $$N_2(v) = {u : \exists w \in N(v) \text{ such that } u \in N(w)} \setminus (N(v) \cup {v})$$

In plain language: neighbors of neighbors, excluding direct neighbors and v itself.

k-hop Neighborhood:

More generally, Nₖ(v) contains vertices reachable in exactly k steps but not fewer.

Applications:

Social networks: "Friends of friends" for recommendations
Influence propagation: How far does information spread?
Privacy: What's visible within 2 hops of a user?

k-hop-neighbors
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from typing import Set, Dict
from collections import deque
 
def k_hop_neighborhood(adj: Dict[str, Set[str]], 
                       start: str, 
                       k: int) -> Dict[int, Set[str]]:
    """
    Compute vertices at each distance from start, up to k hops.
    
    Returns: {distance: set of vertices at that distance}
    """
    result: Dict[int, Set[str]] = {i: set() for i in range(k + 1)}
    result[0].add(start)
    
    visited = {start}
    queue = deque([(start, 0)])
    
    while queue:
        vertex, dist = queue.popleft()
        
        if dist < k:
            for neighbor in adj.get(vertex, set()):
                if neighbor not in visited:
                    visited.add(neighbor)
                    result[dist + 1].add(neighbor)
                    queue.append((neighbor, dist + 1))
    
    return result
 
 
def friends_of_friends(adj: Dict[str, Set[str]], 
                       person: str) -> Set[str]:
    """
    Find 'friends of friends' - vertices at distance exactly 2.
    Useful for friend recommendations.
    """
    direct_friends = adj.get(person, set())
    fof = set()
    
    for friend in direct_friends:
        for friend_of_friend in adj.get(friend, set()):
            # Exclude self and direct friends
            if friend_of_friend != person and friend_of_friend not in direct_friends:
                fof.add(friend_of_friend)
    
    return fof
 
 
# Example: Social network
social_network = {
    "Alice": {"Bob", "Carol"},
    "Bob": {"Alice", "Carol", "Dave"},
    "Carol": {"Alice", "Bob", "Eve"},
    "Dave": {"Bob", "Frank"},
    "Eve": {"Carol"},
    "Frank": {"Dave"},
}
 
print("Alice's direct friends:", social_network["Alice"])
# {'Bob', 'Carol'}
 
print("Alice's friends-of-friends:", friends_of_friends(social_network, "Alice"))
# {'Dave', 'Eve'} - reachable in 2 hops but not 1
 
print("
Neighborhoods at each distance from Alice:")
neighborhoods = k_hop_neighborhood(social_network, "Alice", 3)
for dist, vertices in neighborhoods.items():
    print(f"  Distance {dist}: {vertices}")
# Distance 0: {'Alice'}
# Distance 1: {'Bob', 'Carol'}
# Distance 2: {'Dave', 'Eve'}
# Distance 3: {'Frank'}

BFS Computes All k-hop Neighborhoods

Breadth-First Search naturally computes k-hop neighborhoods as it explores. The BFS level equals the distance from the start vertex. This is why BFS is foundational for social network analysis and influence modeling.

Summary: The Language of Relationships

We've built fluency in the vocabulary of graph relationships. Let's consolidate:

Key Takeaways

•Endpoints are the two vertices connected by an edge; in directed graphs, we distinguish tail (source) and head (target).
•Adjacent vertices share an edge; adjacency is symmetric in undirected graphs but asymmetric in directed graphs.
•Neighbors N(v) are all vertices adjacent to v; the closed neighborhood N[v] includes v itself.
•In directed graphs, out-neighbors N⁺(v) and in-neighbors N⁻(v) capture different directions.
•In-degree counts incoming edges; out-degree counts outgoing edges.
•Sources have no in-neighbors; sinks have no out-neighbors; these are key in DAGs.
•k-hop neighborhoods extend adjacency to vertices reachable in k steps, enabling social network and influence analysis.

What's Next:

Most definitions assume "well-behaved" edges—each edge connects two distinct vertices exactly once. But what about edges from a vertex to itself? Or multiple edges between the same pair? The next page explores self-loops and multi-edges—the special cases that simple graph definitions exclude.

Page Complete

You now command the vocabulary of graph relationships. Terms like 'adjacent,' 'neighbor,' 'in-degree,' and 'k-hop neighborhood' are no longer mysterious—they're precise tools for describing and analyzing graph structure. This vocabulary underlies every graph algorithm.

3 / 4

Loading learning content...

Data Structures & AlgorithmsGraphs

What Is a Graph? Definition & Terminology

LevelBeginner

Duration50 mins

TopicGraphs

3 / 4

Endpoints, Adjacency, and Neighbors

The Vocabulary of Relationships

What You Will Learn

Endpoints of an Edge

Every edge in a graph connects exactly two vertices (or one vertex to itself in the case of a self-loop). These vertices are called the endpoints of the edge.

Formal Definition:

For an edge e = (u, v) (directed) or e = {u, v} (undirected):

u and v are the endpoints of edge e
Edge e is said to join or connect its endpoints
The endpoints are said to be incident to the edge

Directed Graph Terminology:

For a directed edge e = (u, v):

u is the tail, source, or origin of the edge
v is the head, target, or destination of the edge
We say the edge leaves u and enters v
The edge is outgoing from u and incoming to v

Converting Mermaid diagram...

Endpoint Terminology for Directed Edges
Edge	Tail (Source)	Head (Target)	Description
e₁ = (A, B)	A	B	Edge from A to B
e₂ = (B, C)	B	C	Edge from B to C
e₃ = (A, C)	A	C	Edge from A to C

Undirected Edges Have No Tail/Head

In undirected graphs, both endpoints play symmetric roles. There's no 'from' or 'to'—just 'connected.' We simply call them the two endpoints, without distinguishing source from target.

Adjacency Between Vertices

Adjacency is the fundamental relationship between vertices in a graph. Two vertices are adjacent if they are directly connected by an edge.

Formal Definition (Undirected):

In an undirected graph G = (V, E), vertices u and v are adjacent (or neighbors) if: $${u, v} \in E$$

In other words, there exists an edge with u and v as its endpoints.

Formal Definition (Directed):

In a directed graph G = (V, E):

v is adjacent to u if (u, v) ∈ E (edge from u to v)
u is adjacent from v if (v, u) ∈ E (edge from v to u)

Note the asymmetry: in directed graphs, "u is adjacent to v" and "v is adjacent to u" are different statements.

Undirected Adjacency

•Symmetric: If A is adjacent to B, then B is adjacent to A
•Single relationship: Just 'adjacent' or 'not adjacent'
•Edges: {A, B} = {B, A}
•Example: Friendships, road connections

Directed Adjacency

•Asymmetric: A adjacent to B doesn't imply B adjacent to A
•Two relationships: 'Adjacent to' vs 'adjacent from'
•Edges: (A, B) ≠ (B, A)
•Example: Following, hyperlinks, dependencies

adjacency-example

Adjacency Analysis

Undirected Graph:
  V = {A, B, C, D}
  E = {{A,B}, {B,C}, {B,D}}
 
  Adjacency relationships:
    A is adjacent to: B
    B is adjacent to: A, C, D
    C is adjacent to: B
    D is adjacent to: B
 
  Note: "A adjacent to B" ⟺ "B adjacent to A"
 
---
 
Directed Graph:
  V = {A, B, C, D}
  E = {(A,B), (B,C), (C,B), (B,D)}
 
  Adjacency relationships:
    From A: B is adjacent to A  (A → B exists)
    From B: C, D are adjacent to B  (B → C, B → D exist)
    From C: B is adjacent to C  (C → B exists)
    From D: nothing  (no outgoing edges)
 
  Note: B adjacent to C (B → C) AND C adjacent to B (C → B)
        But A adjacent to B (A → B) does NOT mean B adjacent to A
        (no B → A edge)

Neighbors and Neighborhood

Neighbors of a vertex are all vertices adjacent to it. The set of all neighbors is called the vertex's neighborhood.

Formal Definition (Undirected):

For a vertex v in an undirected graph G = (V, E), the neighborhood of v is: $$N(v) = {u \in V : {u, v} \in E}$$

The closed neighborhood includes v itself: $$N[v] = N(v) \cup {v}$$

Formal Definition (Directed):

For a vertex v in a directed graph:

Out-neighbors (successors): $$N^+(v) = {u \in V : (v, u) \in E}$$

In-neighbors (predecessors): $$N^-(v) = {u \in V : (u, v) \in E}$$

The out-neighbors are vertices you can reach in one step from v; in-neighbors are vertices that can reach v in one step.

Neighborhood Notation Summary
Notation	Name	Definition	Usage
N(v)	Open neighborhood	Vertices adjacent to v	Undirected graphs
N[v]	Closed neighborhood	N(v) ∪ {v}	When v should be included
N⁺(v)	Out-neighborhood	Vertices reachable from v	Directed graphs
N⁻(v)	In-neighborhood	Vertices that reach v	Directed graphs

neighborhood-code
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from typing import Set, Dict, List
 
class UndirectedGraph:
    """Graph with neighborhood operations."""
    
    def __init__(self):
        self.adj: Dict[str, Set[str]] = {}
    
    def add_vertex(self, v: str):
        if v not in self.adj:
            self.adj[v] = set()
    
    def add_edge(self, u: str, v: str):
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u].add(v)
        self.adj[v].add(u)
    
    def neighbors(self, v: str) -> Set[str]:
        """N(v): Open neighborhood - vertices adjacent to v."""
        return self.adj.get(v, set()).copy()
    
    def closed_neighborhood(self, v: str) -> Set[str]:
        """N[v]: Closed neighborhood - N(v) ∪ {v}."""
        result = self.neighbors(v)
        result.add(v)
        return result
    
    def are_adjacent(self, u: str, v: str) -> bool:
        """Check if u and v are neighbors."""
        return v in self.adj.get(u, set())
 
 
class DirectedGraph:
    """Directed graph with in/out neighborhood operations."""
    
    def __init__(self):
        self.out_adj: Dict[str, Set[str]] = {}  # v -> successors
        self.in_adj: Dict[str, Set[str]] = {}   # v -> predecessors
    
    def add_vertex(self, v: str):
        if v not in self.out_adj:
            self.out_adj[v] = set()
            self.in_adj[v] = set()
    
    def add_edge(self, u: str, v: str):
        """Add directed edge u → v."""
        self.add_vertex(u)
        self.add_vertex(v)
        self.out_adj[u].add(v)
        self.in_adj[v].add(u)
    
    def out_neighbors(self, v: str) -> Set[str]:
        """N⁺(v): Vertices reachable from v in one step."""
        return self.out_adj.get(v, set()).copy()
    
    def in_neighbors(self, v: str) -> Set[str]:
        """N⁻(v): Vertices that can reach v in one step."""
        return self.in_adj.get(v, set()).copy()
 
 
# Example usage
g = UndirectedGraph()
for edge in [("A", "B"), ("B", "C"), ("B", "D"), ("C", "D")]:
    g.add_edge(*edge)
 
print(f"N(B) = {g.neighbors('B')}")           # {A, C, D}
print(f"N[B] = {g.closed_neighborhood('B')}") # {A, B, C, D}
print(f"A adjacent to B? {g.are_adjacent('A', 'B')}")  # True
 
dg = DirectedGraph()
for u, v in [("A", "B"), ("B", "C"), ("C", "B"), ("B", "D")]:
    dg.add_edge(u, v)
 
print(f"N⁺(B) = {dg.out_neighbors('B')}")  # {C, D}
print(f"N⁻(B) = {dg.in_neighbors('B')}")   # {A, C}

Neighborhood Size = Degree

In-Degree and Out-Degree

In directed graphs, we distinguish between edges entering and leaving a vertex. This gives rise to two degree measures:

Out-Degree:

The out-degree of vertex v, denoted deg⁺(v) or out-deg(v), is the number of edges leaving v: $$\deg^+(v) = |{(v, u) : (v, u) \in E}| = |N^+(v)|$$

In-Degree:

The in-degree of vertex v, denoted deg⁻(v) or in-deg(v), is the number of edges entering v: $$\deg^-(v) = |{(u, v) : (u, v) \in E}| = |N^-(v)|$$

Total Degree:

Sometimes we care about the total number of edges incident to v: $$\deg(v) = \deg^+(v) + \deg^-(v)$$

Degree Types in Directed Graphs
Vertex Type	In-Degree	Out-Degree	Interpretation
Source	0	0	No incoming edges; starting point
Sink	0	0	No outgoing edges; terminal point
Isolated	0	0	No edges at all
Internal	0	0	Both incoming and outgoing edges

degree-analysis

Degree Example

Directed Graph:
  V = {A, B, C, D, E}
  E = {(A,B), (A,C), (B,C), (B,D), (C,D), (D,E)}
 
Degree Analysis:
  Vertex A:  in-deg = 0,  out-deg = 2  → Source
  Vertex B:  in-deg = 1,  out-deg = 2  → Internal
  Vertex C:  in-deg = 2,  out-deg = 1  → Internal
  Vertex D:  in-deg = 2,  out-deg = 1  → Internal
  Vertex E:  in-deg = 1,  out-deg = 0  → Sink
 
Verification (Directed Handshaking Lemma):
  Sum of in-degrees:  0 + 1 + 2 + 2 + 1 = 6
  Sum of out-degrees: 2 + 2 + 1 + 1 + 0 = 6
  Number of edges: 6 ✓
  
  Both sums equal |E| because each edge contributes 1 to one vertex's
  out-degree and 1 to another's in-degree.

Directed Handshaking Lemma

Adjacency in Real Applications

Understanding adjacency helps solve real-world problems by mapping domain concepts to graph operations:

Social Network Analysis:

Neighbors of a user = their friends/followers
High out-degree = follows many accounts
High in-degree = has many followers (influencer)
Users with shared neighbors = potential friend recommendations

Web Crawling:

Out-neighbors of a page = pages it links to
In-neighbors of a page = pages linking to it (backlinks)
Pages with high in-degree = authoritative sources

Dependency Management:

Out-neighbors of a package = packages it depends on
In-neighbors = packages that depend on it (dependents)
Updating a package requires notifying all in-neighbors

Neighbor Operations in Different Domains
Domain	N⁺(v) Meaning	N⁻(v) Meaning	Example Query
Twitter	Accounts v follows	v's followers	Who does Elon follow?
Web Graph	Pages v links to	Pages linking to v	Find all backlinks to a URL
Package Manager	Dependencies of v	Dependents of v	What breaks if we remove v?
Course Prerequisites	Courses v enables	Courses needed for v	What can I take after Calc?
City Traffic	Roads leaving v	Roads entering v	Which streets lead downtown?

Algorithm Design Insight

Common Vertex Classifications

Based on their neighbor relationships, vertices are often classified into categories that reveal structural properties:

By Degree:

Isolated vertex: deg(v) = 0 — no neighbors at all
Leaf/Pendant vertex: deg(v) = 1 — exactly one neighbor
Hub vertex: Very high degree — connected to many others

By Direction (Directed Graphs):

Source: in-deg(v) = 0, out-deg(v) > 0 — starting point
Sink: in-deg(v) > 0, out-deg(v) = 0 — terminal point
Internal: Both in-deg and out-deg > 0

By Connectivity:

Cut vertex/Articulation point: Removal disconnects the graph
Bridge endpoint: Incident to an edge whose removal disconnects the graph

vertex-classification
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
from typing import List, Dict, Set, Tuple
from collections import defaultdict
 
def classify_vertices(edges: List[Tuple[str, str]], 
                      directed: bool = False) -> Dict[str, str]:
    """
    Classify vertices based on their degree properties.
    
    Returns a dictionary mapping vertex to its classification.
    """
    if directed:
        in_degree: Dict[str, int] = defaultdict(int)
        out_degree: Dict[str, int] = defaultdict(int)
        vertices: Set[str] = set()
        
        for u, v in edges:
            out_degree[u] += 1
            in_degree[v] += 1
            vertices.add(u)
            vertices.add(v)
        
        classification = {}
        for v in vertices:
            in_d = in_degree[v]
            out_d = out_degree[v]
            
            if in_d == 0 and out_d == 0:
                classification[v] = "isolated"
            elif in_d == 0:
                classification[v] = "source"
            elif out_d == 0:
                classification[v] = "sink"
            else:
                classification[v] = "internal"
        
        return classification
    
    else:  # Undirected
        degree: Dict[str, int] = defaultdict(int)
        
        for u, v in edges:
            degree[u] += 1
            degree[v] += 1
        
        classification = {}
        for v, d in degree.items():
            if d == 0:
                classification[v] = "isolated"
            elif d == 1:
                classification[v] = "leaf"
            elif d >= 5:  # Arbitrary threshold for "hub"
                classification[v] = "hub"
            else:
                classification[v] = "internal"
        
        return classification
 
# Example: Directed graph
directed_edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]
print("Directed graph classification:")
for v, cls in classify_vertices(directed_edges, directed=True).items():
    print(f"  {v}: {cls}")
# A: source, B: internal, C: internal, D: sink
 
# Example: Undirected graph (tree structure)
undirected_edges = [("A", "B"), ("B", "C"), ("B", "D"), ("B", "E"), 
                    ("B", "F"), ("B", "G")]
print("
Undirected graph classification:")
for v, cls in classify_vertices(undirected_edges, directed=False).items():
    print(f"  {v}: {cls}")
# A: leaf, B: hub, C-G: leaves

Sources and Sinks in DAGs

Second-Order Neighbors and Beyond

Sometimes we care about vertices that are farther than one hop away. This leads to the concept of k-hop neighborhoods:

Second-Order Neighbors (2-hop):

The 2-hop neighborhood of v includes all vertices reachable in exactly 2 steps: $$N_2(v) = {u : \exists w \in N(v) \text{ such that } u \in N(w)} \setminus (N(v) \cup {v})$$

In plain language: neighbors of neighbors, excluding direct neighbors and v itself.

k-hop Neighborhood:

More generally, Nₖ(v) contains vertices reachable in exactly k steps but not fewer.

Applications:

Social networks: "Friends of friends" for recommendations
Influence propagation: How far does information spread?
Privacy: What's visible within 2 hops of a user?

k-hop-neighbors
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from typing import Set, Dict
from collections import deque
 
def k_hop_neighborhood(adj: Dict[str, Set[str]], 
                       start: str, 
                       k: int) -> Dict[int, Set[str]]:
    """
    Compute vertices at each distance from start, up to k hops.
    
    Returns: {distance: set of vertices at that distance}
    """
    result: Dict[int, Set[str]] = {i: set() for i in range(k + 1)}
    result[0].add(start)
    
    visited = {start}
    queue = deque([(start, 0)])
    
    while queue:
        vertex, dist = queue.popleft()
        
        if dist < k:
            for neighbor in adj.get(vertex, set()):
                if neighbor not in visited:
                    visited.add(neighbor)
                    result[dist + 1].add(neighbor)
                    queue.append((neighbor, dist + 1))
    
    return result
 
 
def friends_of_friends(adj: Dict[str, Set[str]], 
                       person: str) -> Set[str]:
    """
    Find 'friends of friends' - vertices at distance exactly 2.
    Useful for friend recommendations.
    """
    direct_friends = adj.get(person, set())
    fof = set()
    
    for friend in direct_friends:
        for friend_of_friend in adj.get(friend, set()):
            # Exclude self and direct friends
            if friend_of_friend != person and friend_of_friend not in direct_friends:
                fof.add(friend_of_friend)
    
    return fof
 
 
# Example: Social network
social_network = {
    "Alice": {"Bob", "Carol"},
    "Bob": {"Alice", "Carol", "Dave"},
    "Carol": {"Alice", "Bob", "Eve"},
    "Dave": {"Bob", "Frank"},
    "Eve": {"Carol"},
    "Frank": {"Dave"},
}
 
print("Alice's direct friends:", social_network["Alice"])
# {'Bob', 'Carol'}
 
print("Alice's friends-of-friends:", friends_of_friends(social_network, "Alice"))
# {'Dave', 'Eve'} - reachable in 2 hops but not 1
 
print("
Neighborhoods at each distance from Alice:")
neighborhoods = k_hop_neighborhood(social_network, "Alice", 3)
for dist, vertices in neighborhoods.items():
    print(f"  Distance {dist}: {vertices}")
# Distance 0: {'Alice'}
# Distance 1: {'Bob', 'Carol'}
# Distance 2: {'Dave', 'Eve'}
# Distance 3: {'Frank'}

BFS Computes All k-hop Neighborhoods

Summary: The Language of Relationships

We've built fluency in the vocabulary of graph relationships. Let's consolidate:

Key Takeaways

•Endpoints are the two vertices connected by an edge; in directed graphs, we distinguish tail (source) and head (target).
•Adjacent vertices share an edge; adjacency is symmetric in undirected graphs but asymmetric in directed graphs.
•Neighbors N(v) are all vertices adjacent to v; the closed neighborhood N[v] includes v itself.
•In directed graphs, out-neighbors N⁺(v) and in-neighbors N⁻(v) capture different directions.
•In-degree counts incoming edges; out-degree counts outgoing edges.
•Sources have no in-neighbors; sinks have no out-neighbors; these are key in DAGs.
•k-hop neighborhoods extend adjacency to vertices reachable in k steps, enabling social network and influence analysis.

What's Next:

Page Complete

3 / 4