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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 急求答案
51/1返回列表
查看: 862  |  回复: 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 Isak0320 2026-10-12 10/500 2026-10-12 22:38 by 大飞鱼鱼鱼
[基金申请] 入职后第一次管课题组的专利缴费，对账才发现官费比别人多掏了一倍 +6 13108017953 2026-10-08 6/300 2026-10-12 20:07 by w3w3y3
[有机交流] OpenAI又攻克数学难题了，离AI做有机合成还有多远？ +4 wangyl_123 2026-10-10 8/400 2026-10-12 18:09 by wangyl_123
[教师之家] 课题组会帮你通过考核么？ +3 好运来～9527 2026-10-10 6/300 2026-10-12 14:55 by 简单化xn
[公派出国] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 9/450 2026-10-11 22:34 by XQNyDCa1Tk5n
[公派出国] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +5 qR2AdCWTVtkw 2026-10-09 10/500 2026-10-11 22:26 by XQNyDCa1Tk5n
[找工作] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 8/400 2026-10-11 22:26 by XQNyDCa1Tk5n
[考博] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 9/450 2026-10-11 22:15 by XQNyDCa1Tk5n
[考博] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 22:11 by XQNyDCa1Tk5n
[教师之家] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 (EPI+-1)(金币-50) +5 qR2AdCWTVtkw 2026-10-09 10/500 2026-10-11 22:06 by XQNyDCa1Tk5n
[教师之家] 售SCI一区T0P文章，我:8.O.55.1.O.5.4,科目全,可+急 (EPI+-1)(金币-50) +5 qR2AdCWTVtkw 2026-10-09 10/500 2026-10-11 14:25 by VOMexwnDzOFZ
[教师之家] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 (EPI+-1)(金币-50) +4 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 14:05 by VOMexwnDzOFZ
[考研] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 8/400 2026-10-11 13:51 by VOMexwnDzOFZ
[硕博家园] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +5 qR2AdCWTVtkw 2026-10-09 8/400 2026-10-11 13:45 by VOMexwnDzOFZ
[找工作] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +3 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 10:54 by VOMexwnDzOFZ
[找工作] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +4 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 10:34 by VOMexwnDzOFZ
[考博] 招收博士生一名 +3 mandolin 2026-10-10 3/150 2026-10-11 10:21 by 不是山谷！
[公派出国] 售SCI一区T0P文章，我:8O.55.1.O.54,科目全,可伽急 +4 qR2AdCWTVtkw 2026-10-09 4/200 2026-10-11 03:14 by M0zrYVSAnxpE
[有机交流] 各位大佬，路线设计求助 +6 zapen 2026-10-08 8/400 2026-10-10 15:59 by zapen
[有机交流] 我应该选哪条合成路线让实验成功率高一些？ +5 jing816y 2026-10-08 9/450 2026-10-10 09:05 by zapen
信息提示
关闭
请填处理意见
关闭