应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 急求答案
北京石油化工学院2026年研究生招生接收调剂公告
51/1返回列表
查看: 785  |  回复: 4
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

xinruirui1

金虫 (初入文坛)

[求助] 急求答案

假设图g采用邻接表储存,求不带权无向连通图g中距离顶点v的最远的一个顶点
回复此楼

» 猜你喜欢
出师未捷身先死！！！
1楼 2011-06-18 11:03:51
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

文俊点点

木虫 (著名写手)

【答案】应助回帖

xinruirui1(金币+1): 没有想要的答案 2011-06-19 15:52:22
记录路径的长度，进行比较，选最长的那个···········
赞一下 回复此楼
这是你所拥有的时间·····这是你所能改变的生活·········
3楼2011-06-19 00:24:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 5 个回答

文俊点点

木虫 (著名写手)

【答案】应助回帖

★
jjdg(金币+1): 感谢参与 2011-06-19 13:20:55
xinruirui1(金币+1): 我只要答案，我不是学那专业的 2011-06-19 15:52:51
找数据结构图的那一章，有求最短路径的，你给记录一下，换成最长的就是了·········
赞一下(1人) 回复此楼
这是你所拥有的时间·····这是你所能改变的生活·········
2楼2011-06-19 00:23:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)

【答案】应助回帖

★
jjdg(金币+1): 感谢参与应助 2011-06-19 13:21:11
xinruirui1(金币+1): 没有我要的答案 2011-06-19 15:51:56
广度优先搜索算法是最简单也最直接的做法。
赞一下(1人) 回复此楼
漩涡的中心有一块空地，空空的。
4楼2011-06-19 08:54:06
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

super0077585

金虫 (小有名气)

【答案】应助回帖

★ ★ ★ ★
dubo(金币+1): 欢迎常来程序语言版讨论 2011-06-19 22:07:20
微尘、梦想(金币+3): 辛苦了…… 2011-06-20 19:31:19
微尘、梦想:编辑内容 2011-06-20 19:32
在网上找的程序分别计算顶点到各点的最短和最长距离，没太看懂，希望有所帮助，另外近期也要复习了，可以共同探讨探讨，网上有人说把邻接矩阵中的数值用相反数表示，求得最短距离即是最长距离。。。
CODE:
/*
* test_1.cpp
*
*  Created on: 2011-6-19
*      Author: zxf
*/
#include
#define N 7 /* 顶点数目 */
#define I 999 /* 表示无穷大 */

int graph[N][N] =
{ /* 图的邻接矩阵 */
{ I, 4, 5, 8, I, I, I },
{ I, I, I, 6, 6, I, I },
{ I, I, I, 5, I, 7, I },
{ I, I, I, I, 8, 9, 9 },
{ I, I, I, I, I, I, 5 },
{ I, I, I, I, I, I, 4 },
{ I, I, I, I, I, I, I } };
int List[N]; /* 存放拓扑序列 */
int TopologicalOrder(); /* 拓扑排序函数 */
int main() /* 主 函 数 */
{
        int i, j, k, l;
        int ee[N], el[N]; /* 最长最短距离 */
        int path_e[N][N], path_l[N][N], n_e[N], n_l[N]; /* 记录路径数据 */
        /* 初始化数据 */
        for (i = 0; i < N; i++)
        {
                n_e[i] = 0; /* 到 i 的最短路线的结点数 */
                n_l[i] = 0; /* 到 i 的最长路线的结点数 */
                ee[i] = I;
                el[i] = 0;
        }
        ee[0] = el[0] = 0; /* 初始化头结点 */
        path_e[0][0] = 0;
        path_l[0][0] = 0;
        n_e[0] = 1;
        n_l[0] = 1;
        /* 拓扑排序 */
        if (!TopologicalOrder())
                return 0;
        /* 对于拓扑序列,运用动态规划步步算出最长路线与最短路线 */
        for (i = 0; i < N; i++)
        {
                /* 提取拓扑序列的元素 */
                k = List[i];
                /* 更新它所指向顶点的所有数据 */
                for (j = 0; j < N; j++)
                {
                        /* 寻找指向的顶点 */
                        if (graph[k][j] != I)
                        {
                                /* 如果新路径更短 */
                                if (graph[k][j] + ee[k] < ee[j])
                                {
                                        /* 更新最短路径长度 */
                                        ee[j] = graph[k][j] + ee[k];
                                        /* 更新最短路线 */
                                        for (l = 0; l < n_e[k]; l++)
                                        {
                                                path_e[j][l] = path_e[k][l];
                                        }
                                        path_e[j][l] = j;
                                        n_e[j] = l + 1;
                                }
                                /* 如果新路径更长 */
                                if (graph[k][j] + el[k] > el[j])
                                {
                                        /* 更新最长路径长度 */
                                        el[j] = graph[k][j] + el[k];
                                        /* 更新最长路线 */
                                        for (l = 0; l < n_l[k]; l++)
                                        {
                                                path_l[j][l] = path_l[k][l];
                                        }
                                        path_l[j][l] = j;
                                        n_l[j] = l + 1;
                                }
                        }
                }
        }
        /* 输出结果到屏幕 */
        for (i = 0; i < N; i++)
        {
                printf("shortest(%d): %2d Path: ", i + 1, ee[i]);
                for (j = 0; j < n_e[i]; j++)
                {
                        printf("%d ", path_e[i][j] + 1);
                }
                printf(" ");
                printf("longest (%d): %2d Path: ", i + 1, el[i]);
                for (j = 0; j < n_l[i]; j++)
                {
                        printf("%d ", path_l[i][j] + 1);
                }
                printf(" ");
        }
        return 0;
}

int TopologicalOrder()
{
        int i, j, top, count;
        int indegree[N], Stack[N];
        top = 0; /* 栈顶标志 */
        for (i = 0; i < N; i++)
        {
                indegree[i] = 0; /* 初始化入度 */
                for (j = 0; j < N; j++)
                {
                        if (graph[j][i] != I)
                        { /* 如连通 */
                                indegree[i]++; /* 入度自增1 */
                        }
                }
                if (!indegree[i])
                { /* 如入度为零 */
                        Stack[top++] = i; /* 入栈 */
                }
        }
        count = 0; /* 输出顶点数 */
        while (top != 0)
        {
                i = Stack[--top];
                List[count++] = i;
                for (j = 0; j < N; j++)
                {
                        if (graph[i][j] != I)
                        { /* 如连通 */
                                if (!(--indegree[j]))
                                { /* 而且入度为零 */
                                        Stack[top++] = j; /* 入栈 */
                                }
                        }
                }/* for */
        }/* while */
        return (count < N) ? 0 : 1;
}

[ Last edited by 微尘、梦想 on 2011-6-20 at 19:32 ]
赞一下(2人) 回复此楼
沉重的飞。。。
5楼2011-06-19 20:49:41
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 5 个回答
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 英一数一408，总分284，二战真诚求调剂 +13 12.27 2026-03-30 15/750 2026-04-03 14:41 by 氮气气气
[考研] 266求调剂 +15 阳阳哇塞 2026-04-01 15/750 2026-04-03 13:44 by melodiousnow
[考研] 262求调剂 +6 励志一定发文章 2026-04-02 7/350 2026-04-03 09:54 by linyelide
[考研] 326求调剂 +10 崽崽仔 2026-04-02 10/500 2026-04-03 09:08 by 帕尔马拉特
[考研] 413求调剂 +3 柯某某 2026-03-31 3/150 2026-04-02 16:59 by zzsw+
[考研] 一志愿北京科技大学085601材料工程英一数二初试总分335求调剂 +9 双马尾痞老板2 2026-04-01 9/450 2026-04-02 12:14 by oooqiao
[考研] 求调剂推荐 +3 南山南@ 2026-04-01 3/150 2026-04-02 12:09 by xiaoranmu
[考研] 266求调剂 +4 学员97LZgn 2026-04-02 4/200 2026-04-02 09:52 by yulian1987
[考研] 350求调剂 +7 阿佳～ 2026-03-31 7/350 2026-04-01 16:12 by yanflower7133
[考研] 0703一志愿南师大334求调剂 +4 seven7yu 2026-03-30 4/200 2026-04-01 16:10 by oooqiao
[考研] 309求调剂 +19 谁不是少年 2026-03-29 19/950 2026-04-01 15:47 by jp9609
[考研] 283求调剂 +9 A child 2026-03-28 9/450 2026-04-01 14:20 by Jaylen.
[考研] 358求调剂 +3 王向阳花 2026-03-31 3/150 2026-04-01 09:56 by zzchen2000
[考研] 085601 329分调剂 +6 yzsa12 2026-03-31 6/300 2026-03-31 15:23 by yanflower7133
[考研] 286求调剂 +5 丢掉懒惰 2026-03-27 8/400 2026-03-31 11:27 by Delta2012
[考研] 11408总分309，一志愿东南大学求调剂，不挑专业 +5 天赋带到THU 2026-03-29 6/300 2026-03-30 20:49 by dick_runner
[考研] 一志愿华中师范化学332分求调剂 +3 Lyy930824@ 2026-03-29 3/150 2026-03-30 20:15 by DHUSHUAI
[考研] 求调剂 +10 家佳佳佳佳佳 2026-03-29 10/500 2026-03-30 18:34 by 544594351
[考研] 求调剂 +7 争取九点睡 2026-03-28 8/400 2026-03-28 21:07 by 争取九点睡
[考研] 复试调剂 +3 raojunqi0129 2026-03-28 3/150 2026-03-28 15:27 by 落睿可思
信息提示
关闭
请填处理意见
关闭