问答题

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为： MAx{从w到v的最短距离|w属于V(G)} 如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。

答案：正确答案：设C是有向图G的邻接矩阵，求最小偏心度的顶点的步骤如下： (1)利用Floyd算法求出每对顶点之间的最短路径矩...

你可能感兴趣的试题

对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。

答案：正确答案：顶点A到顶点B、C、D、E的最短路径依次是3、18、38、43，按Dijkstra所选顶点过程是B、C、D、E...

(1)对于有向无环图，叙述求拓扑有序序列的步骤。 (2)对于以下的图，写出它的4个不同的拓扑有序序列。

答案：正确答案：(1)对有向图，求拓扑序列步骤为： ①在有向图中选一个没有前驱(即入度为零)的顶点并输出。 ②在图中删除该顶点...

试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点V _i 到顶点V _j 的路径(i≠j)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)

答案：正确答案：算法1： int visited[]=0；／／全局变量，访问数组初始化 int dfs(AdjList g，...

假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注意：图中不存在顶点到自己的弧)

答案：正确答案：用邻接矩阵存储时，可用以下方法实现： void Print(int v，int start){／／输出从顶点s...

已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则打印出该路径上的顶点。

答案：正确答案：void Allpath(AdjList g，vertype u，vertype v){ ／／求有向图g中顶点...

“破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)

答案：正确答案：void SpnTree(AdjList g){ ／／用“破圈法”求解带权连通无向图的一棵最小代价生成树 ty...

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为： MAx{从w到v的最短距离|w属于V(G)} 如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。

答案：正确答案：设C是有向图G的邻接矩阵，求最小偏心度的顶点的步骤如下： (1)利用Floyd算法求出每对顶点之间的最短路径矩...

对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减1，并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2)定义在算法中使用的全局辅助数组。 (3)写出在遍历图的同时进行拓扑排序的算法。

答案：正确答案：(1)邻接表定义 typedef struct ArcNode{ int adjvex； struct Arc...