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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 急求答案
51/1返回列表
查看: 823  |  回复: 4
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

xinruirui1

金虫 (初入文坛)

[求助] 急求答案

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

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

文俊点点

木虫 (著名写手)

【答案】应助回帖

★
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的回帖

文俊点点

木虫 (著名写手)

【答案】应助回帖

xinruirui1(金币+1): 没有想要的答案 2011-06-19 15:52:22
记录路径的长度，进行比较，选最长的那个···········
赞一下 回复此楼
这是你所拥有的时间·····这是你所能改变的生活·········
3楼2011-06-19 00:24:27
已阅   回复此楼   关注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的回帖
相关版块跳转 我要订阅楼主 xinruirui1 的主题更新
51/1返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 各位道友，我要去昆明玩几天，回来见。 +7 Tide man 2026-08-14 8/400 2026-08-15 01:11 by arzu_hma
[教师之家] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +4 7lpolszZVXgi 2026-08-14 4/200 2026-08-15 01:08 by 4wMiSEwB6436
[考研] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +3 HFw0lei2R37i 2026-08-14 7/350 2026-08-15 00:40 by 4wMiSEwB6436
[基金申请] 咱们一起用铁证分析2026国家社科基金中标与否 +7 启萌科技 2026-08-12 22/1100 2026-08-14 23:45 by Noways
[基金申请] 是这周出结果还是下周出结果？ +4 yuleib84 2026-08-11 4/200 2026-08-14 23:05 by lfy8008
[教师之家] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 HFw0lei2R37i 2026-08-14 5/250 2026-08-14 22:32 by 4wMiSEwB6436
[基金申请] filecode +6 cratir 2026-08-14 10/500 2026-08-14 18:29 by 笑叹辞穷
[基金申请] 奇怪，两个人的filecode固定段从头到尾一模一样 +8 布布和一二 2026-08-10 11/550 2026-08-14 14:58 by Equinoxhua
[基金申请] 有时候，自然基金真的不能太认真 （我的申报经验） +6 majunge000 2026-08-11 8/400 2026-08-14 14:44 by 医学老男孩
[硕博家园] 读博的好处 +4 lnee 2026-08-11 4/200 2026-08-14 10:20 by ahsoarli
[基金申请] filecode +15 documentary 2026-08-10 17/850 2026-08-14 10:08 by kissu88
[文学芳草园] 阿姨 +4 汪汪锅 2026-08-09 4/200 2026-08-13 19:43 by arzu_hma
[硕博家园] 一作与独作在应聘高校教师时区别大吗 +3 mbygzh 2026-08-08 4/200 2026-08-13 19:31 by 龙-樱
[基金申请] 不应该看fileCode +7 且听虎啸 2026-08-12 9/450 2026-08-13 14:27 by flydreamws
[基金申请] Filecode 又变了，巨变 +3 WH3796 2026-08-12 4/200 2026-08-13 14:13 by 小木虫6752397
[基金申请] 2019年青年基金涵评意见，大家看看几个A，几个B? +11 Tide man 2026-08-11 11/550 2026-08-13 07:35 by 撸猫猫
[基金申请] 为什么网上很多人说本周 12号出结果 +6 瞬息宇宙 2026-08-10 7/350 2026-08-11 19:25 by Tide man
[基金申请] 国自然结果 +4 Vierhys 2026-08-10 8/400 2026-08-10 15:06 by Vierhys
[基金申请] 这样的filecode谁见过 +11 布布和一二 2026-08-08 22/1100 2026-08-10 11:10 by wmfsnow
[基金申请] fileCode有新解读？ +10 Tide man 2026-08-08 18/900 2026-08-09 12:55 by 仁砚薪传
信息提示
关闭
请填处理意见
关闭