数据结构与算法参考答案（第十三周）
2021-03-31 15:25
标签：有向无环图 cell 优先 输出 nat style -- unsigned 返回 一、试编写一个算法，给有向无环图G中每个顶点赋以一个整数序号，并满足以下条件：若从顶点i至顶点j有一条弧，则应使i 答： 分析题目，我们很容易知道本题应当采用拓扑排序的方法。我们先统计所有点的入度，然后把当前剩下的点中入度为0的点编号,把这个点删去,更新与它相邻的点的入度，直到重复所有点处理完。最终得到的结果便是题目要求的答案。 该算法实现的伪代码如下： /* 函数名称：拓扑排序 函数传入参数：图g 函数返回值：成功排序返回OK失败返回ERROR */ bool Topological(GraphAdjList g, int Queue[]){ unsigned int front,rear; front = rear = 0; for (i = 0;i if (i==g.numVertexes) return ERROR; Queue[rear] = i; rear++; for (EdgeNode *j = g.adjList[i].firstEdge;j!=NULL||front!=rear; ){ while (j!=NULL){ front++; if (front==rear) break; j = g.adjList[Queue[front]].firstEdge; } if (j!=NULL&&(--g.adjList[j->adjVex].in)==0){ Queue[rear] = j->adjVex; rear++; } if (j!=NULL) j = j->next; } if (rear == g.numVertexes){ for (unsigned int i = 0;i cout
} return OK; } else{ return ERROR; } } /* 函数名称：process 函数传入参数图G，数组Top 函数返回值：void */ void process(GraphAdjList g, int Top[]) { if(Topological(g, top[])) { //输出的结果即为答案 for(int i = 1; i
printf("%d\n", i, g.vertices[Top[k]].data); } } return; } 算法分析：拓扑排序作为一种将偏序转换为全序的一种算法，可以高效地解决这种排序中看似难解的问题。综上，它是一个解决这种有优先次序问题的较好算法。 二、以邻接表作存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法。 答： 由题意我们可以知道，该题目需要我们用邻接表实现迪杰斯特拉算法。由该算法的相关知识我们可以知道，我们需要定义一个dis数组用于存储从一号顶点到其它各个点的初始路径。然后，通过在不断最近的点，最终得到路径。同时需要对找过的点进行标记。 该算法实现的伪代码如下： /* 函数名称：用邻接表实现Dijkstra 函数传入参数：图G,终点参数 函数返回值类型：void */ int dis[MAXSIZE]; void Dijkstra(Graph G, int destination) { //初始化dis表示1号顶点到其余各个顶点的最短路程 for(int i = 1; i
if(G.edge[i].start == 1) dist[G.edge[i].end] = G.edge[i].value;//初始化dis数组， } //初始化vis for(int i = 1; i
vis[i] = false; } vis[1] = true; dis[1] = false; //算法核心内容 for(int i = 1; i
int minn = inf; for(int j = 1; j
if(vis[j] == false && dis[j]
minn = dis[j]; k = j; //进行最小距离查找 } } vis[k] = true; //使用邻接表的方式继续进行查找 for(int p = G.adjlist[k].firstedge; p != -1; p = p -> next) { if(value[p] 如果权值小于最大范围 if(dis[k] + edge[p].value
dis[edge[i].end] = dis[k] + edge[p].value; } } } //最终得到的dis数组为第一个点到第i各点的最短路径长度 prinf("%d", &dis[destination]); return 0; } } 算法分析：由该算法的相关知识我们可以知道，通过使用邻接表，我们将算法的时间复杂度优化为了O(nlogn)。该算法是求解该问题的较好算法。 数据结构与算法参考答案（第十三周） 标签：有向无环图 cell 优先 输出 nat style -- unsigned 返回 原文地址：https://www.cnblogs.com/lightac/p/13558261.html