企业官网建设流程全解析

图论核心算法与手算例题

一、 代码实现（C语言）

1. 图的邻接矩阵存储与DFS/BFS遍历

#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 #define INFINITY 65535 // 图的邻接矩阵存储结构 typedef struct { int vexs[MAX_VERTEX_NUM]; // 顶点数组 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexNum, arcNum; // 顶点数和边数 } MGraph; // 初始化图 void InitGraph(MGraph *G, int n) { G->vexNum = n; G->arcNum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { G->arcs[i][j] = (i == j) ? 0 : INFINITY; // 对角线为0，其余为无穷大 } } } // 添加边（无向图） void AddEdge(MGraph *G, int v, int w, int weight) { G->arcs[v][w] = weight; G->arcs[w][v] = weight; // 有向图则注释此行 G->arcNum++; } // 深度优先搜索（DFS）递归实现 int visited[MAX_VERTEX_NUM] = {0}; // 访问标记数组 void DFS(MGraph G, int v) { visited[v] = 1; printf("%d ", v); // 访问顶点v for (int w = 0; w < G.vexNum; w++) { if (G.arcs[v][w] != 0 && G.arcs[v][w] != INFINITY && !visited[w]) { DFS(G, w); // 递归访问未访问的邻接点 } } } // 广度优先搜索（BFS）队列实现 #include <stdbool.h> #define QUEUE_SIZE 100 typedef struct { int data[QUEUE_SIZE]; int front, rear; } Queue; void InitQueue(Queue *Q) { Q->front = Q->rear = 0; } bool QueueEmpty(Queue Q) { return Q.front == Q.rear; } bool EnQueue(Queue *Q, int e) { if ((Q->rear + 1) % QUEUE_SIZE == Q->front) return false; Q->data[Q->rear] = e; Q->rear = (Q->rear + 1) % QUEUE_SIZE; return true; } bool DeQueue(Queue *Q, int *e) { if (QueueEmpty(*Q)) return false; *e = Q->data[Q->front]; Q->front = (Q->front + 1) % QUEUE_SIZE; return true; } void BFS(MGraph G, int v) { int visited[MAX_VERTEX_NUM] = {0}; Queue Q; InitQueue(&Q); printf("%d ", v); visited[v] = 1; EnQueue(&Q, v); while (!QueueEmpty(Q)) { DeQueue(&Q, &v); for (int w = 0; w < G.vexNum; w++) { if (G.arcs[v][w] != 0 && G.arcs[v][w] != INFINITY && !visited[w]) { printf("%d ", w); visited[w] = 1; EnQueue(&Q, w); } } } } // 测试DFS和BFS int main() { MGraph G; InitGraph(&G, 5); AddEdge(&G, 0, 1, 1); AddEdge(&G, 0, 2, 1); AddEdge(&G, 1, 3, 1); AddEdge(&G, 2, 4, 1); printf("DFS遍历结果: "); DFS(G, 0); printf(" "); printf("BFS遍历结果: "); BFS(G, 0); printf(" "); return 0; }

2. Prim算法（最小生成树）

// Prim算法求最小生成树（邻接矩阵） void Prim(MGraph G) { int lowcost[MAX_VERTEX_NUM]; // 存储当前生成树到剩余顶点的最小权值 int closest[MAX_VERTEX_NUM]; // 存储最小权值边对应的顶点 int min, k; // 从顶点0开始构造最小生成树 for (int i = 0; i < G.vexNum; i++) { lowcost[i] = G.arcs[0][i]; // 初始化lowcost数组 closest[i] = 0; // 所有顶点初始依附于顶点0 } printf("最小生成树的边: "); for (int i = 1; i < G.vexNum; i++) { min = INFINITY; k = 0; // 寻找当前lowcost中的最小值 for (int j = 1; j < G.vexNum; j++) { if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; k = j; } } printf("(%d, %d) 权值: %d ", closest[k], k, min); lowcost[k] = 0; // 将顶点k加入生成树 // 更新lowcost和closest数组 for (int j = 1; j < G.vexNum; j++) { if (lowcost[j] != 0 && G.arcs[k][j] < lowcost[j]) { lowcost[j] = G.arcs[k][j]; closest[j] = k; } } } }

3. Dijkstra算法（单源最短路径）

// Dijkstra算法求单源最短路径 void Dijkstra(MGraph G, int v0) { int dist[MAX_VERTEX_NUM]; // 从v0到各顶点的最短路径长度 int path[MAX_VERTEX_NUM]; // 前驱顶点数组 int S[MAX_VERTEX_NUM] = {0}; // 标记是否已找到最短路径 // 初始化 for (int i = 0; i < G.vexNum; i++) { dist[i] = G.arcs[v0][i]; if (dist[i] < INFINITY) path[i] = v0; else path[i] = -1; } S[v0] = 1; // 将v0加入S集 // 循环n-1次，每次确定一个顶点的最短路径 for (int i = 1; i < G.vexNum; i++) { int min = INFINITY; int u = v0; // 选择当前dist中的最小值 for (int j = 0; j < G.vexNum; j++) { if (!S[j] && dist[j] < min) { min = dist[j]; u = j; } } S[u] = 1; // 将顶点u加入S集 // 更新dist和path数组 for (int w = 0; w < G.vexNum; w++) { if (!S[w] && G.arcs[u][w] < INFINITY && dist[u] + G.arcs[u][w] < dist[w]) { dist[w] = dist[u] + G.arcs[u][w]; path[w] = u; } } } // 输出结果 printf("从顶点%d出发的最短路径: ", v0); for (int i = 0; i < G.vexNum; i++) { if (i != v0) { printf("到顶点%d的最短距离: %d ", i, dist[i]); } } }

4. Floyd算法（多源最短路径）

// Floyd算法求所有顶点对之间的最短路径 void Floyd(MGraph G) { int A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 距离矩阵 int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 路径矩阵 // 初始化 for (int i = 0; i < G.vexNum; i++) { for (int j = 0; j < G.vexNum; j++) { A[i][j] = G.arcs[i][j]; if (i != j && A[i][j] < INFINITY) path[i][j] = i; else path[i][j] = -1; } } // 三重循环更新 for (int k = 0; k < G.vexNum; k++) { for (int i = 0; i < G.vexNum; i++) { for (int j = 0; j < G.vexNum; j++) { if (A[i][k] + A[k][j] < A[i][j]) { A[i][j] = A[i][k] + A[k][j]; path[i][j] = path[k][j]; } } } } // 输出结果（示例：输出A矩阵） printf("Floyd算法结果（距离矩阵）: "); for (int i = 0; i < G.vexNum; i++) { for (int j = 0; j < G.vexNum; j++) { if (A[i][j] == INFINITY) printf("INF "); else printf("%3d ", A[i][j]); } printf(" "); } }

5. 拓扑排序（基于邻接表）

// 邻接表存储结构 typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 } ArcNode; typedef struct VNode { int data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; // 拓扑排序（Kahn算法） int TopologicalSort(ALGraph G) { int indegree[MAX_VERTEX_NUM] = {0}; int stack[MAX_VERTEX_NUM], top = -1; int count = 0; // 计数输出的顶点数 // 计算所有顶点的入度 for (int i = 0; i < G.vexnum; i++) { ArcNode *p = G.vertices[i].firstarc; while (p) { indegree[p->adjvex]++; p = p->nextarc; } } // 将所有入度为0的顶点入栈 for (int i = 0; i < G.vexnum; i++) { if (indegree[i] == 0) { stack[++top] = i; } } printf("拓扑排序结果: "); while (top != -1) { int v = stack[top--]; printf("%d ", v); count++; // 删除顶点v的所有出边 ArcNode *p = G.vertices[v].firstarc; while (p) { int k = p->adjvex; indegree[k]--; if (indegree[k] == 0) { stack[++top] = k; } p = p->nextarc; } } if (count < G.vexnum) { printf(" 图中存在环，无法完成拓扑排序 "); return 0; } return 1; }

6. 关键路径算法

// 关键路径算法（基于拓扑排序） typedef struct { int ve[MAX_VERTEX_NUM]; // 事件最早发生时间 int vl[MAX_VERTEX_NUM]; // 事件最迟发生时间 } CriticalPath; int CriticalPathMethod(ALGraph G) { int indegree[MAX_VERTEX_NUM] = {0}; int stack1[MAX_VERTEX_NUM], top1 = -1; // 用于拓扑排序的栈 int stack2[MAX_VERTEX_NUM], top2 = -1; // 用于逆拓扑排序的栈 CriticalPath cp; // 初始化ve数组 for (int i = 0; i < G.vexnum; i++) cp.ve[i] = 0; // 计算入度并初始化栈 for (int i = 0; i < G.vexnum; i++) { ArcNode *p = G.vertices[i].firstarc; while (p) { indegree[p->adjvex]++; p = p->nextarc; } } // 拓扑排序求ve for (int i = 0; i < G.vexnum; i++) { if (indegree[i] == 0) stack1[++top1] = i; } int count = 0; while (top1 != -1) { int v = stack1[top1--]; stack2[++top2] = v; // 将顶点压入逆拓扑栈 count++; ArcNode *p = G.vertices[v].firstarc; while (p) { int k = p->adjvex; if (--indegree[k] == 0) stack1[++top1] = k; // 更新ve[k] if (cp.ve[v] + 1 > cp.ve[k]) { // 假设边权为1 cp.ve[k] = cp.ve[v] + 1; } p = p->nextarc; } } if (count < G.vexnum) return 0; // 存在环 // 初始化vl数组 for (int i = 0; i < G.vexnum; i++) cp.vl[i] = cp.ve[stack2[top2]]; // 逆拓扑排序求vl while (top2 != -1) { int v = stack2[top2--]; ArcNode *p = G.vertices[v].firstarc; while (p) { int k = p->adjvex; if (cp.vl[k]1 < cp.vl[v]) { // 假设边权为1 cp.vl[v] = cp.vl[k]1; } p = p->nextarc; } } // 输出关键路径 printf("关键路径: "); for (int i = 0; i < G.vexnum; i++) { if (cp.ve[i] == cp.vl[i]) { printf("%d ", i); } } printf(" "); return 1; }

二、 手算步骤与例题

1. Prim算法手算例题

题目：使用Prim算法构造下图的最小生成树，从顶点A开始。

A /|\ 1 3 4 / | \ B--2--C \ | / 5 6 \| D

边权：AB=1, AC=3, AD=4, BC=2, BD=5, CD=6

手算步骤：

1. 初始化：选择A作为起点，U={A}，V-U={B,C,D}
2. 第一轮：比较边AB(1), AC(3), AD(4)，选择最小权值边AB(1)，将B加入U，U={A,B}
3. 第二轮：比较边AC(3), AD(4), BC(2)，选择最小权值边BC(2)，将C加入U，U={A,B,C}
4. 第三轮：比较边AD(4), CD(6)，选择最小权值边AD(4)，将D加入U，U={A,B,C,D}
5. 结果：最小生成树包含边AB(1), BC(2), AD(4)，总权值=7

2. Dijkstra算法手算例题

题目：使用Dijkstra算法求顶点A到其他各顶点的最短路径。

A /|\2 6 9 / | \ B--1--C \ | / 3 2 \| D

边权：AB=2, AC=6, AD=9, BC=1, BD=3, CD=2

手算步骤（表格形式）：

结果：A到B最短路径=2，A到C最短路径=3，A到D最短路径=5

3. Floyd算法手算例题

题目：使用Floyd算法求所有顶点对之间的最短路径（邻接矩阵如下）。

初始邻接矩阵： A B C A 0 2 6 B ∞0 1 C ∞ ∞ 0

手算步骤：

1. 初始化：A⁽⁰⁾ = 初始矩阵
2. k=0（以A为中间点）：
   B→C：min(∞, 2+6=8) = ∞（无变化）
   C→B：min(∞, ∞+∞) = ∞
3. k=1（以B为中间点）：
   • A→C：min(6, 2+1=3) = 3
     C→A：min(∞, ∞+∞) = ∞
4. k=2（以C为中间点）：
   A→B：min(2, 3+∞) = 2
   B→A：min(∞, 1+∞) = ∞

最终结果矩阵：

A B C A 0 2 3 B ∞ 0 1 C ∞ ∞ 0

4. 拓扑排序手算例题

题目：对下图进行拓扑排序。

A → B → D ↓ ↗ C → E

手算步骤：

1. 计算入度：A(0), B(1), C(1), D(2), E(2)
2. 第一轮：选择入度为0的顶点A，输出A，删除A及其出边，更新入度：B(0), C(0), D(2), E(2)
3. 第二轮：选择入度为0的顶点B（或C），假设选B，输出B，删除B及其出边，更新入度：C(0), D(1), E(2)
4. 第三轮：选择入度为0的顶点C，输出C，删除C及其出边，更新入度：D(0), E(1)
5. 第四轮：选择入度为0的顶点D，输出D，删除D及其出边，更新入度：E(0)
6. 第五轮：选择入度为0的顶点E，输出E

结果：一种可能的拓扑序列为 A → B → C → D → E

5. 关键路径手算例题

题目：求下图AOE网的关键路径。

23 A —→ B —→ D ↘ ↗1↘ /2 C

活动与时间：a1(A→B)=2, a2(A→C)=1, a3(B→D)=3, a4(C→D)=2

手算步骤：

1. 求ve（事件最早发生时间）：

   • ve(A)=0
     ve(B)=max{ve(A)+2}=2 - ve(C)=max{ve(A)+1}=1 - ve(D)=max{ve(B)+3=5, ve(C)+2=3}=5

2. 求vl（事件最迟发生时间）：

   • vl(D)=ve(D)=5 - vl(B)=min{vl(D)-3}=2 - vl(C)=min{vl(D)-2}=3 - vl(A)=min{vl(B)-2=0, vl(C)-1=2}=0

3. 求e（活动最早开始时间）和l（活动最迟开始时间）：
   a1: e=ve(A)=0, l=vl(B)-2=0 a2: e=ve(A)=0, l=vl(C)-1=2 - a3: e=ve(B)=2, l=vl(D)-3=2
   a4: e=ve(C)=1, l=vl(D)-2=3

4. 求关键活动：e=l的活动是关键活动
   a1: e=l=0 ✓ - a2: e=0≠l=2 ✗
   a3: e=l=2 ✓ - a4: e=1≠l=3 ✗

结果：关键路径为 A → B → D，总工期=5

三、 算法对比总结

注：1. Prim算法通常用于稠密图，Kruskal算法（未在用户query中要求）更适合稀疏图。2. Dijkstra算法不能处理带负权边的图。3. 拓扑排序可用于检测有向图中是否存在环。4. 关键路径算法基于拓扑排序，用于确定项目的最短完成时间和关键活动。

参考来源

• C 408—《数据结构》图、查找、排序专题考点（含解析）-云社区-华为云
• 408数据结构常考算法 - CSDN文库
• 《数据结构》代码
• 【数据结构与编译原理】图论算法与文法分类核心知识点：最短路径、最小生成树、拓扑排序、关键路径及编译过程详解资源-CSDN下载
• 图领计算机2026年408考研选择题专项突破1800题常见技术问题有哪些？_编程语言-CSDN问答