跳到主要内容 图结构邻接表实现：DFS、BFS 及 Dijkstra 算法详解 | 极客日志
C 算法
图结构邻接表实现：DFS、BFS 及 Dijkstra 算法详解 基于邻接表存储的图数据结构，实现了深度优先搜索（DFS）、广度优先搜索（BFS）及 Dijkstra 最短路径算法。内容涵盖图的构建、遍历逻辑、贪心选择策略证明及完整 C 语言代码示例，并对比了 DFS/BFS 在求解最短路径中的应用差异。
时间旅人 发布于 2026/2/20 更新于 2026/4/18 图（邻接表）- DFS/BFS/Dijkstra 算法
基于一道简单实验，学习用邻接表结构储存图，并且包含 DFS/BFS 两种遍历方式，以及 Dijkstra 算法（朴素版）在本题的使用。
头文件（以及相关内容）
#include <cstdio>
#include <cstdlib>
#define MAX_VERTEX_NUM 20
#define INFINITY 0x3f3f3f3f
typedef char VertexType;
1. 邻接表的构建
包含三个部分：
边节点
所指向边节点的索引（adjvex）
指向下一边节点的指针（nextarc）
顶点节点
储存该节点的信息（data）-----节点名称等
指向边节点的指针（firstarc）
组合成邻接表
顶点数组（vertices）
顶点数（vexnum）
边数（arcnum）
代码如下：
typedef struct ArcNode {int adjvex;
int value;
struct ArcNode * nextarc ;typedef struct VNode {typedef 微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown转HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
struct ALGraph {
int
2. 两种遍历 复用函数（vis — 表示该顶点是否被访问；Visit 函数 — 访问该节点后的行为：打印节点信息）
int vis[MAX_VERTEX_NUM];
void Visit (const ALGraph &G, int v) {
printf ("%c " , G.vertices[v].data);
}
DFS 遍历 void DFS (const ALGraph &G, int v) {
vis[v] = 1 ;
Visit(G, v);
ArcNode* p = G.vertices[v].firstarc;
while (p != NULL ) {
int w = p->adjvex;
if (!vis[w]) {
DFS(G, w);
}
p = p->nextarc;
}
}
void DFSTraverse (const ALGraph &G) {
int n = G.vexnum;
for (int i = 0 ; i < n; i++) {
vis[i] = 0 ;
}
for (int i = 0 ; i < n; i++) {
if (!vis[i]) {
DFS(G, i);
}
}
}
BFS 遍历 （为简化演示，不使用 STL 队列，采用双指针的移动来模拟入队、出队操作）
注 ：front++相当于出队，rear++相当于入队
void BFS (const ALGraph &G, int v) {
int Queue[MAX_VERTEX_NUM];
int front = 0 , rear = 0 ;
vis[v] = 1 ;
Visit(G, v);
Queue[rear++] = v;
while (front < rear) {
int u = Queue[front];
front++;
ArcNode* p = G.vertices[u].firstarc;
while (p != NULL ) {
int w = p->adjvex;
if (!vis[w]) {
vis[w] = 1 ;
Visit(G, w);
Queue[rear++] = w;
}
p = p->nextarc;
}
}
}
void BFSTraverse (const ALGraph &G) {
int n = G.vexnum;
for (int i = 0 ; i < n; i++) {
vis[i] = 0 ;
}
for (int i = 0 ; i < n; i++) {
if (!vis[i]) {
BFS(G, i);
}
}
}
3. Dijkstra 算法 (朴素版）
初始化距离 ：设定源节点到自身的距离为 0，到其他所有节点的距离为 （INFINITY：0x3f3f3f3f）。贪心选择 ：每次从未确定最短路径的节点中，选择当前距离源节点最近的节点 u，将其标记为'已确定最短路径'。（dist[u]）松弛操作 ：对节点 u 的所有邻接节点 v，尝试通过 u 更新 v 的最短距离。松弛条件：若 dist[v] > dist[u] + w(u, v)，则更新 dist[v] = dist[u] + w(u, v)。重复步骤 2-3：直到所有节点都被标记为'已确定最短路径'。
Dijkstra 算法贪心选择正确性证明：
前提
图中所有边权非负；
S：已确定最短路径的节点集合；
dist[u]：当前已知 s 到 u 的最短距离上界。
反证法证明
假设：选 u 时，存在更短的 s→u 路径 P，长度＜dist[u]。拆分路径 P：s→…→x（x∈S，P 上最后一个在 S 中的节点）→y（y∉S，P 上第一个不在 S 中的节点）→…→u。
因 x∈S，其最短路径已确定（dist[x] = 真实最短距离）；又边权非负，所以 s→y 的真实最短距离 ≤ s→x→y 的长度 ≤ 路径 P 的长度（y 到 u 的路径权值≥0，不会缩短）。
结合假设'P 长度＜dist[u]'，可推出：s→y 的真实最短距离 ＜ dist[u]。但 dist[y] 是 s→y 的距离上界（dist[y]≥真实最短距离），因此 dist[y] ＜ dist[u]。
这与「u 是当前未确定节点中 dist 最小的节点」矛盾，故假设不成立。结论
每次选的 u，其当前 dist[u] 就是 s 到 u 的最短路径，后续不会被更新。
int Dijkstra (const ALGraph &G, int start) {
int n = G.vexnum;
int * dist = (int *)malloc (n * sizeof (int ));
int * visited = (int *)malloc (n * sizeof (int ));
for (int i = 0 ; i < n; i++) {
dist[i] = INFINITY;
visited[i] = 0 ;
}
dist[start] = 0 ;
for (int i = 0 ; i < n; i++) {
int u = -1 ;
int min_dist = INFINITY;
for (int j = 0 ; j < n; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
u = j;
}
}
if (u == -1 ) break ;
visited[u] = 1 ;
if (u == n - 1 ) break ;
ArcNode* p = G.vertices[u].firstarc;
while (p != NULL ) {
int v = p->adjvex;
int w = p->value;
if (!visited[v] && dist[u] != INFINITY && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
p = p->nextarc;
}
}
int result = dist[n - 1 ];
free (dist);
free (visited);
return result;
}
4. 综上所述（完整代码如下） #include <cstdio>
#include <cstdlib>
#define MAX_VERTEX_NUM 20
#define INFINITY 0x3f3f3f3f
typedef char VertexType;
typedef struct ArcNode {int adjvex;
int value;
struct ArcNode * nextarc ;typedef struct VNode {typedef struct ALGraph {int vexnum, arcnum;
} ALGraph;
int LocateVex (const ALGraph &G, VertexType V) {
for (int i = 0 ; i < G.vexnum; i++) {
if (G.vertices[i].data == V) return i;
}
return -1 ;
}
int CreateDG (ALGraph &G) {
printf ("请输入顶点数与边数：\n" );
scanf ("%d %d" , &G.vexnum, &G.arcnum);
getchar();
printf ("请输入%d个顶点的信息：\n" , G.vexnum);
for (int i = 0 ; i < G.vexnum; i++) {
scanf ("%c" , &G.vertices[i].data);
getchar();
G.vertices[i].firstarc = NULL ;
}
VertexType V1, V2;
int v;
ArcNode* p;
printf ("请输入%d条边的信息：\n" , G.arcnum);
for (int k = 0 ; k < G.arcnum; k++) {
scanf ("%c %c %d" , &V1, &V2, &v);
getchar();
int i = LocateVex(G, V1);
int j = LocateVex(G, V2);
if (i == -1 || j == -1 ) return 0 ;
p = (ArcNode*)malloc (sizeof (ArcNode));
p->adjvex = j;
p->value = v;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
}
return 1 ;
}
int vis[MAX_VERTEX_NUM];
void Visit (const ALGraph &G, int v) {
printf ("%c " , G.vertices[v].data);
}
void DFS (const ALGraph &G, int v) {
vis[v] = 1 ;
Visit(G, v);
ArcNode* p = G.vertices[v].firstarc;
while (p != NULL ) {
int w = p->adjvex;
if (!vis[w]) {
DFS(G, w);
}
p = p->nextarc;
}
}
void DFSTraverse (const ALGraph &G) {
int n = G.vexnum;
for (int i = 0 ; i < n; i++) {
vis[i] = 0 ;
}
for (int i = 0 ; i < n; i++) {
if (!vis[i]) {
DFS(G, i);
}
}
}
void BFS (const ALGraph &G, int v) {
int Queue[MAX_VERTEX_NUM];
int front = 0 , rear = 0 ;
vis[v] = 1 ;
Visit(G, v);
Queue[rear++] = v;
while (front < rear) {
int u = Queue[front];
front++;
ArcNode* p = G.vertices[u].firstarc;
while (p != NULL ) {
int w = p->adjvex;
if (!vis[w]) {
vis[w] = 1 ;
Visit(G, w);
Queue[rear++] = w;
}
p = p->nextarc;
}
}
}
void BFSTraverse (const ALGraph &G) {
int n = G.vexnum;
for (int i = 0 ; i < n; i++) {
vis[i] = 0 ;
}
for (int i = 0 ; i < n; i++) {
if (!vis[i]) {
BFS(G, i);
}
}
}
int Dijkstra (const ALGraph &G, int start) {
int n = G.vexnum;
int * dist = (int *)malloc (n * sizeof (int ));
int * visited = (int *)malloc (n * sizeof (int ));
for (int i = 0 ; i < n; i++) {
dist[i] = INFINITY;
visited[i] = 0 ;
}
dist[start] = 0 ;
for (int i = 0 ; i < n; i++) {
int u = -1 ;
int min_dist = INFINITY;
for (int j = 0 ; j < n; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
u = j;
}
}
if (u == -1 ) break ;
visited[u] = 1 ;
if (u == n - 1 ) break ;
ArcNode* p = G.vertices[u].firstarc;
while (p != NULL ) {
int v = p->adjvex;
int w = p->value;
if (!visited[v] && dist[u] != INFINITY && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
p = p->nextarc;
}
}
int result = dist[n - 1 ];
free (dist);
free (visited);
return result;
}
int main () {
ALGraph G;
if (CreateDG(G)) {
printf ("成功\n" );
} else printf ("失败\n" );
printf ("DFS 遍历结果：" );
DFSTraverse(G);
printf ("\n" );
printf ("BFS 遍历结果：" );
BFSTraverse(G);
printf ("\n" );
int min = Dijkstra(G, 0 );
printf ("%d" , min);
return 0 ;
}
5. 补充（用 DFS/BFS 解决该题）
DFS #include <cstdio>
#include <cstdlib>
#define MAX_VERTEX_NUM 20
#define INFINITY 0x3f3f3f3f
typedef char VertexType;
typedef struct ArcNode {int adjvex;
int value;
struct ArcNode * nextarc ;typedef struct VNode {typedef struct ALgraph {int vexnum, arcnum;
} ALgraph;
int LocateVex (const ALgraph &G, VertexType e) {
for (int i = 0 ; i < G.vexnum; i++) {
if (G.vertices[i].data == e) {
return i;
}
}
return -1 ;
}
int CreateDG (ALgraph &G) {
printf ("请输入顶点数和边数：\n" );
scanf ("%d %d" , &G.vexnum, &G.arcnum);
getchar();
printf ("请输入顶点的信息：\n" );
for (int i = 0 ; i < G.vexnum; i++) {
scanf ("%c" , &G.vertices[i].data);
getchar();
G.vertices[i].firstarc = NULL ;
}
printf ("请输入边的关系：\n" );
ArcNode* p;
VertexType V1, V2;
int v;
for (int k = 0 ; k < G.arcnum; k++) {
scanf ("%c %c %d" , &V1, &V2, &v);
getchar();
int i = LocateVex(G, V1);
int j = LocateVex(G, V2);
if (i == -1 || j == -1 ) {
return 0 ;
}
p = (ArcNode*)malloc (sizeof (ArcNode));
p->adjvex = j;
p->value = v;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
}
return 1 ;
}
int min_dist = INFINITY;
int cur_dist = 0 ;
int visited[MAX_VERTEX_NUM];
void DFS (const ALgraph &G, int idx) {
int n = G.vexnum;
if (idx == n - 1 ) {
if (cur_dist < min_dist) min_dist = cur_dist;
return ;
}
visited[idx] = 1 ;
ArcNode* p = G.vertices[idx].firstarc;
while (p != NULL ) {
int next_idx = p->adjvex;
int weight = p->value;
if (!visited[next_idx]) {
cur_dist += weight;
DFS(G, next_idx);
cur_dist -= weight;
}
p = p->nextarc;
}
visited[idx] = 0 ;
}
int main () {
ALgraph G;
if (CreateDG(G)) {
printf ("创建成功\n" );
} else printf ("创建失败\n" );
for (int i = 0 ; i < G.vexnum; i++) {
visited[i] = 0 ;
}
DFS(G, 0 );
printf ("%d" , min_dist);
return 0 ;
}
BFS #include <cstdio>
#include <cstdlib>
#define MAX_VERTEX_NUM 20
#define INFINITY 0x3f3f3f3f
typedef char VertexType;
typedef struct ArcNode {int adjvex;
int value;
struct ArcNode * nextarc ;typedef struct VNode {typedef struct ALgraph {int vexnum, arcnum;
} ALgraph;
int LocateVex (const ALgraph &G, VertexType e) {
for (int i = 0 ; i < G.vexnum; i++) {
if (G.vertices[i].data == e) {
return i;
}
}
return -1 ;
}
int CreateDG (ALgraph &G) {
printf ("请输入顶点数和边数：\n" );
scanf ("%d %d" , &G.vexnum, &G.arcnum);
getchar();
printf ("请输入顶点的信息：\n" );
for (int i = 0 ; i < G.vexnum; i++) {
scanf ("%c" , &G.vertices[i].data);
getchar();
G.vertices[i].firstarc = NULL ;
}
printf ("请输入边的关系：\n" );
ArcNode* p;
VertexType V1, V2;
int v;
for (int k = 0 ; k < G.arcnum; k++) {
scanf ("%c %c %d" , &V1, &V2, &v);
getchar();
int i = LocateVex(G, V1);
int j = LocateVex(G, V2);
if (i == -1 || j == -1 ) {
return 0 ;
}
p = (ArcNode*)malloc (sizeof (ArcNode));
p->adjvex = j;
p->value = v;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
}
return 1 ;
}
typedef struct QNode {int idx;
int path_len;
} QNode;
int BFS (const ALgraph &G) {
int n = G.vexnum;
int * dist = (int *)malloc (n * sizeof (int ));
for (int i = 0 ; i < n; i++) {
dist[i] = INFINITY;
}
QNode queue [MAX_VERTEX_NUM * 10 ];
int front = 0 , rear = 0 ;
queue [rear].idx = 0 ;
queue [rear].path_len = 0 ;
rear++;
while (front < rear) {
QNode cur = queue [front];
front++;
int cur_idx = cur.idx;
int cur_len = cur.path_len;
if (cur_len > dist[cur_idx]) continue ;
ArcNode* p = G.vertices[cur_idx].firstarc;
while (p != NULL ) {
int next_idx = p->adjvex;
int weight = p->value;
int new_len = cur_len + weight;
if (new_len < dist[next_idx]) {
dist[next_idx] = new_len;
queue [rear].idx = next_idx;
queue [rear].path_len = new_len;
rear++;
}
p = p->nextarc;
}
}
int result = dist[n - 1 ];
free (dist);
return result;
}
int main () {
ALgraph G;
if (CreateDG(G)) {
printf ("创建成功\n" );
} else printf ("创建失败\n" );
int result = BFS(G);
printf ("%d" , result);
return 0 ;
}
