首页 / 算法 / 数据结构与算法参考答案（第十三周）
数据结构与算法参考答案（第十三周）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法参考答案（第十三周），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3128字，纯文字阅读大概需要5分钟。
内容图文
一、试编写一个算法，给有向无环图G中每个顶点赋以一个整数序号，并满足以下条件：若从顶点i至顶点j有一条弧，则应使i<j。
答：
分析题目，我们很容易知道本题应当采用拓扑排序的方法。我们先统计所有点的入度，然后把当前剩下的点中入度为0的点编号,把这个点删去,更新与它相邻的点的入度，直到重复所有点处理完。最终得到的结果便是题目要求的答案。
该算法实现的伪代码如下：
|
/* 函数名称：拓扑排序 函数传入参数：图g 函数返回值：成功排序返回OK失败返回ERROR */ bool Topological(GraphAdjList g, int Queue[]){ unsigned int front,rear; front = rear = 0; for (i = 0;i<g.numVertexes&&g.adjList[i].in!= 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<g.numVertexes;i++){ cout <<Queue[i]<<" "<<endl; } return OK; } else{ return ERROR; } } /* 函数名称：process 函数传入参数图G，数组Top 函数返回值：void */ void process(GraphAdjList g, int Top[]) { if(Topological(g, top[])) { //输出的结果即为答案 for(int i = 1; i <= g.vexNum; ++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 <= number; i++){ if(G.edge[i].start == 1) dist[G.edge[i].end] = G.edge[i].value;//初始化dis数组， }
//初始化vis for(int i = 1; i <= n; ++i) { vis[i] = false; } vis[1] = true; dis[1] = false; //算法核心内容 for(int i = 1; i <= n - 1; ++i) { int minn = inf; for(int j = 1; j <= n; ++j) { if(vis[j] == false && dis[j] < minn) { minn = dis[j]; k = j; //进行最小距离查找 } } vis[k] = true; //使用邻接表的方式继续进行查找 for(int p = G.adjlist[k].firstedge; p != -1; p = p -> next) { if(value[p] < inf) { //如果权值小于最大范围 if(dis[k] + edge[p].value < dis[edge[p].end]) { dis[edge[i].end] = dis[k] + edge[p].value; } } } //最终得到的dis数组为第一个点到第i各点的最短路径长度 prinf("%d", &dis[destination]); return 0; } } |
算法分析：由该算法的相关知识我们可以知道，通过使用邻接表，我们将算法的时间复杂度优化为了O(nlogn)。该算法是求解该问题的较好算法。
内容总结
以上是互联网集市为您收集整理的数据结构与算法参考答案（第十三周）全部内容，希望文章能够帮你解决数据结构与算法参考答案（第十三周）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。