设计一个算法计算邻接表表示的图的各个顶点的出度
c
//Analyse:由于邻接表中,表头就是尾节点,几个邻接点就是几个出度.
void out_degree(LGraph lg)
{
int i;
ENode *p;
printf("--- 各节点出度统计 ---\n");
for(i = 0;i < lg.n;i++)
{
int count = 0;
for(p = lg.a[i];p;p = p->nextArc)
count++;
printf("节点 [%d]：%d\n",i,count);
}
}设计一个算法计算邻接表表示的图的各个顶点的入度
c
//Analyse:就是箭头指向各个顶点的数目一共多少个
void in_degree(LGraph lg)
{
int i;
ENode *p;
int *count = (int*)calloc(lg.n,sizeof(int));
if(count == NULL) return;
printf("--- 各节点入度统计 ---\n");
for(i = 0;i < lg.n;i++)
{
for(p = lg.a[i];p;p = p->nextArc)
count[p->adjVex]++;
}
//遍历结束之后 所有情况考虑 运算完成
for(i = 0;i < lg.n;i++)
printf("节点 [%d]：%d\n",i,count[i]);
//结束之后 释放内存
free(count);
}设计算法计算任意节点u的入度:
c
与第五题思路一致
但是直接选中,遍历所有非u节点 即i < lg.n && i != u
然后当 p -> adjVex == u时
入度加1，然后输出，这里无需添加count计数数组，只需要保存数值输出即可设计算法任意顶点u的出度:
c
第四题时计算每个顶点的入度
稍加修改即可输出任意节点u的入度!
比如在printf执行时添加条件：i == u 时打印
这样就返回顶点u的入度G是由邻接矩阵表示的图,设计算法由邻接矩阵转化为邻接表
c
//Analyse:邻接矩阵->邻接表 如果mg.a[i][j] 存在就在lg->a[i]后面加边、点
LGraph* mg2lg(MGraph mg)
{
//转化后的邻接表表示的图存储
LGraph *lg = (LGraph*)malloc(sizeof(LGraph));
if(lg == NULL) return;
lg->a = (ENode**)malloc(sizeof(ENode*) * mg.n);
if(lg->a == NULL)
{
free(lg)
return;
}
//然后开始 加入表 先创建节点 加如当前位置后面 然后置null
for(int i=0;i<mg.n;i++)
{
//初始化为NULL防止出问题
lg->a[i] = NULL;
for(int j=0;j<mg.n;j++)
{
//从i为尾开始 开始创建邻接表
if(mg.a[i][j] != noEdge && i != j)
{
ENode *p = (ENode*)malloc(sizeof(ENode));
if(p == NULL) return;
p->adjVex = j;
p->w = mg.a[i][j];
p->nextArc = lg->a[i];
lg->a[i] = p;
}
}
}
return lg;
}G是由邻接表表示的图,设计算法由邻接表转化为邻接矩阵表示的图
c
//Analyse:lg->a[i] 然后访问nextArc(j) 以及w 对应mg->a[i][j] == w
MGraph* lg2mg(LGraph lg)
{
int n = lg.n;
MGraph *mg = (MGraph*)malloc(sizeof(MGraph));
if (mg == NULL) return NULL;
mg->n = n;
// 2. 分配 NxN 矩阵的空间并初始化
mg->a = (ElemType**)malloc(sizeof(ElemType*) * n);
if (mg->a == NULL) { free(mg); return NULL; }
// 2.1 循环分配每一行空间并进行初始化
for (int i = 0; i < n; i++) {
mg->a[i] = (ElemType*)malloc(sizeof(ElemType) * n);
if (mg->a[i] == NULL) {
// 实际项目中需要清理已分配的内存，这里简化
return NULL;
}
for (int j = 0; j < n; j++) {
if (i == j) {
mg->a[i][j] = 0; // 对角线设为 0
} else {
mg->a[i][j] = noEdge; // 其余设为无穷大/不连通
}
}
}
// 3. 遍历邻接表，填充矩阵 (核心逻辑)
for (int i = 0; i < n; i++) {
ENode *p = lg.a[i]; // 从顶点 i 的链表头开始遍历
// 遍历 i 的所有出边
while (p != NULL) {
int j = p->adjVex; // 终点 j
// 将链表中的权值 p->w 填入矩阵的 mg.a[i][j] 位置
mg->a[i][j] = p->w;
p = p->nextArc; // 移动到下一条边
}
}
return mg;
}根据前面9.23画出顶点为c的宽度优先遍历顶点序列与生成森林(或生成树)
c
答案：CEBFAD
生成森林：如图![[a73ba5fcd96e8b46ad2109d73fe94534.jpg]] G以邻接表表示，设计一个算法实现对图G的深度优先遍历的算法
c
bool *visited;
// DFS 递归核心函数
void DFS_Visit(LGraph lg, int v) {
visited[v] = true;
printf("访问: %d\n", v);
ENode *p = lg.a[v];
while (p != NULL) {
int w = p->adjVex;
// 遇到未访问的邻居，递归进入
if (!visited[w]) {
DFS_Visit(lg, w);
}
p = p->nextArc;
}
}
// 主函数
void DFS(LGraph lg) {
visited = (bool*)calloc(lg.n, sizeof(bool));
if (visited == NULL) return;
// 遍历所有顶点，处理不连通分量
for (int i = 0; i < lg.n; i++) {
if (!visited[i]) {
DFS_Visit(lg, i);
}
}
free(visited);
}G以邻接表表示，设计一个算法实现对图G的广度优先遍历的算法
c
#include <stdbool.h>
#include <stdlib.h>
// 假设队列 Queue 已经实现
// 辅助结构：简化队列实现
typedef struct {
int *data;
int front, rear;
int capacity;
} SimpleQueue;
// [队列基本操作代码省略...]
void BFS(LGraph lg) {
bool *visited = (bool*)calloc(lg.n, sizeof(bool));
SimpleQueue q;
InitQueue(&q, lg.n); // 队列初始化
for (int i = 0; i < lg.n; i++) {
if (!visited[i]) {
visited[i] = true;
printf("访问: %d\n", i);
EnQueue(&q, i); // 起点入队
while (q.front != q.rear) {
int v = DeQueue(&q); // 队首出队
ENode *p = lg.a[v];
// 遍历 v 的所有邻居
while (p != NULL) {
int w = p->adjVex;
if (!visited[w]) {
visited[w] = true;
printf("访问: %d\n", w);
EnQueue(&q, w); // 邻居入队
}
p = p->nextArc;
}
}
}
}
free(q.data);
free(visited);
}在第三题基础上构建的邻接表上执行拓扑排序算法，给出最终拓扑排序的顶点序列
c
拓扑排序顺序：3502416无向图G以邻接矩阵表示，设计算法实现普利姆算法prim
c
void Prim(MGraph mg, int u) { // u 为起始顶点
int n = mg.n;
// lowcost[i] 存储：已选顶点集 U 到 顶点 i 的最短边的权值
int *lowcost = (int*)malloc(sizeof(int) * n);
// closest[i] 存储：lowcost[i] 对应的边在 U 中的哪个顶点
int *closest = (int*)malloc(sizeof(int) * n);
bool *s = (bool*)calloc(n, sizeof(bool)); // 标记顶点是否已加入最小生成树 (集合 S)
// 1. 初始化：以起始点 u 为中心
for (int i = 0; i < n; i++) {
lowcost[i] = mg.a[u][i]; // 顶点 i 到 u 的距离
closest[i] = u; // 顶点 i 都是连接到 u
}
s[u] = true; // 起点 u 加入集合 S
// 2. 循环 n-1 次，每次找到一条新的最小边
for (int i = 1; i < n; i++) {
int min = INFTY;
int k = -1; // 记录找到的下一个顶点
// 步骤 A: 贪心选择：在 (V-S) 中找到 lowcost 最小的顶点 k
for (int j = 0; j < n; j++) {
if (!s[j] && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
if (k == -1) break; // 图不连通，无法继续
// 步骤 B: 打印新边，将 k 加入集合 S
s[k] = true;
printf("选择边 (%d, %d), 权值: %d\n", closest[k], k, min);
// 步骤 C: 松弛更新：用新加入的顶点 k 更新 lowcost 数组
for (int j = 0; j < n; j++) {
// 检查：如果 j 未被选中，且 (k -> j) 边的权值比 lowcost[j] 更小
if (!s[j] && mg.a[k][j] < lowcost[j]) {
lowcost[j] = mg.a[k][j]; // 更新最短连接权值
closest[j] = k; // 更新最短连接的顶点是 k
}
}
}
free(lowcost);
free(closest);
free(s);
}AOE网求各个事件最早发生时间、允许最迟发生时间、 各个活动允许发生的最早时间与最迟时间，关键活动、关键路径、以及关键路径长度 ![[94c1280fafda36ad2b00b2b9ea29ee3a_720.jpg]]