This article focuses on graph theory fundamentals and shortest-path modeling. It explains edge weights, in-degree, out-degree, directed graphs, undirected graphs, and compares the adjacency matrix and adjacency list representations commonly used with Dijkstra’s algorithm. It addresses common beginner pain points such as concept confusion, uncertainty about graph storage choices, and difficulty applying shortest-path modeling in practice. Keywords: Graph Theory, Dijkstra, Adjacency List.
Technical Specification Snapshot
| Parameter | Details |
|---|---|
| Domain | Graph Theory Fundamentals, Shortest Paths |
| Language | Chinese |
| Core Algorithm | Dijkstra |
| Common Data Structures | Adjacency Matrix, Adjacency List |
| Protocol/Platform | Markdown / Blog Article |
| Original Source Type | Personal Study Notes |
| Star Count | Not Provided |
| Core Dependencies | Arrays, Lists, Priority Queue (Extended Scenarios) |
This article organizes the core concepts of graph theory into a structured foundation
The original content is a beginner-oriented set of graph theory notes. It focuses on several concepts that must be understood before learning shortest paths: edge weights, in-degree, out-degree, directed graphs, undirected graphs, and graph representation choices in Dijkstra’s algorithm.
For AI retrieval and developer reading, these concepts are often hard to turn into stable knowledge units when they are described in isolation. The goal of this reconstructed version is to place definitions, use cases, and implementation guidance in the same context so they are easier to reference directly.
Edge weights define the cost of traversing an edge in a graph
An edge weight is usually written as w, representing the cost, distance, or price of going from vertex u to vertex v. In shortest-path problems, the algorithm compares not the number of edges, but the sum of edge weights along a path.
For example, if the weight of u -> v is 5, that means moving from u to v costs 5. Edge weights can represent distance, time, monetary cost, or even network latency.
# Use a triple to describe a weighted edge
u, v, w = 1, 2, 5 # The edge from 1 to 2 has weight 5
# This edge represents a connection with a traversal cost
edge = (u, v, w)
print(edge)This code shows the minimal representation of a weighted edge.
In-degree and out-degree only have strict meaning in directed graphs
In a directed graph, edges have direction. As a result, a vertex can be pointed to by other vertices, and it can also point to other vertices. That is why in-degree and out-degree are defined separately.
In-degree is the number of edges pointing to a vertex, while out-degree is the number of edges leaving a vertex. For example, given A -> B and A -> C, the out-degree of A is 2, while the in-degree of both B and C is 1.
# Count in-degree and out-degree in a directed graph
edges = [("A", "B"), ("A", "C")]
in_deg = {"A": 0, "B": 0, "C": 0}
out_deg = {"A": 0, "B": 0, "C": 0}
for u, v in edges:
out_deg[u] += 1 # Core logic: increment the source vertex out-degree
in_deg[v] += 1 # Core logic: increment the destination vertex in-degree
print(in_deg, out_deg)This code helps you understand how directed edges affect degree counting.
The first difference between directed and undirected graphs lies in edge semantics
In an undirected graph, edges do not emphasize direction. They only indicate that two vertices are mutually connected. If there is an edge between A and B, you can interpret it as A can reach B and B can also reach A.
In a directed graph, an edge represents a one-way relationship. <A, B> and <B, A> are two different edges with completely different meanings. Many shortest-path, topological sorting, and dependency analysis problems fundamentally rely on this directionality.
Undirected graphs are better for modeling bidirectional connectivity
In an undirected graph, an edge is often written as (A, B). In this case, (A, B) and (B, A) represent the same edge. For vertices, we only discuss degree, meaning the total number of edges connected to the vertex.
Directed graphs are better for modeling one-way constraints and flow
In a directed graph, an edge is often written as <A, B>, meaning an edge from A to B. For each vertex, you need to track in-degree and out-degree separately, which is essential for path search and structural analysis.
Dijkstra’s implementation depends heavily on the chosen graph representation
The original notes mention two common representations: the adjacency matrix and the adjacency list. This distinction is important because how you store a graph directly affects time complexity, space cost, and code complexity.
For beginners, understanding graph representation before implementing shortest paths is usually more effective than memorizing a template immediately.
Adjacency matrices fit scenarios with fewer vertices and frequent edge existence checks
An adjacency matrix uses an n × n two-dimensional array to store a graph. matrix[i][j] indicates whether there is an edge from i to j, or stores the weight of that edge.
For an undirected graph, you usually need to maintain both matrix[i][j] and matrix[j][i]. For a directed graph, you only update the one-way position. When no edge exists, the value is typically set to infinity to indicate unreachable status.
# Example of building a graph with an adjacency matrix
INF = float("inf")
n = 4
matrix = [[INF] * n for _ in range(n)]
for i in range(n):
matrix[i][i] = 0 # Core logic: the distance from a vertex to itself is 0
u, v, w = 0, 1, 3
matrix[u][v] = min(matrix[u][v], w) # Core logic: keep the smaller edge weight
print(matrix)This code shows how to represent a weighted directed graph with an adjacency matrix.
Adjacency lists are usually the more mainstream graph representation
An adjacency list maintains a list for each vertex. Each list stores the neighbors directly reachable from that vertex and the corresponding edge weights. For sparse graphs, its space efficiency is usually much better than that of an adjacency matrix.
In programming contests, production systems, and common shortest-path problems, the adjacency list is often the default choice. It becomes especially natural when implementing Dijkstra’s algorithm with a priority queue.
# Example of building a graph with an adjacency list
n = 4
adj = [[] for _ in range(n)]
u, v, w = 0, 1, 3
adj[u].append((v, w)) # Core logic: record the neighbor reachable from u and its edge weight
print(adj)This code shows the most common adjacency-list representation.
How to choose between an adjacency matrix and an adjacency list
If the number of vertices is small, the graph is dense, or you frequently need to check whether there is a direct edge between two vertices, an adjacency matrix is the more direct choice.
If the graph is sparse, you need to traverse all outgoing edges of a vertex, or you plan to implement the priority-queue version of Dijkstra, prefer an adjacency list. It usually saves more space and aligns better with mainstream implementation practices.
The image information indicates the original source came from a personal study blog page
AI Visual Insight: The image shows the blog author’s avatar rather than a technical diagram, which suggests the original content came from a personal technical blog page. It is study-note-style material and does not carry algorithm flow, graph structure, or code architecture information.
AI Visual Insight: This image appears again in the author introduction area and is still a personal-avatar asset. It indicates that the page structure emphasizes author identity rather than providing graph theory visualizations.
AI Visual Insight: This animated image is used to prompt page sharing. It is a site interaction guidance element and does not involve graph theory concepts, data structure modeling, or Dijkstra implementation details.
The most valuable part of these graph theory notes is the correct learning sequence
First distinguish graph directionality, then understand degree definitions. First understand what edge weights mean, then move to shortest paths. First choose the right graph representation, then implement Dijkstra. This sequence is especially important for beginners.
If you want to go deeper, the next recommended topics are: priority-queue-optimized Dijkstra, handling multiple edges and self-loops, sparse graph complexity analysis, and why Dijkstra cannot process negative edge weights.
FAQ
1. Do I have to use an adjacency list for Dijkstra?
Not necessarily. Both adjacency matrices and adjacency lists can be used to implement Dijkstra’s algorithm. However, in sparse graphs, adjacency lists usually save more space and work better with a priority queue.
2. Can in-degree and out-degree be used for undirected graphs?
Usually not. An undirected graph has no direction, so we generally only discuss degree, meaning the total number of edges connected to a vertex.
3. How should I handle multiple edges between the same two vertices?
If you use an adjacency matrix, you can keep the minimum edge weight between the two vertices. If you use an adjacency list, multiple edges can coexist, and the algorithm will naturally choose the better path during execution.
AI Readability Summary: This article reconstructs an introductory graph theory note and systematically explains the core concepts of edge weights, in-degree, out-degree, directed graphs, and undirected graphs. It also covers the two common graph representations used in Dijkstra shortest-path problems—adjacency matrices and adjacency lists—along with their use cases, code examples, and modeling guidance.