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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 急求答案
北京石油化工学院2026年研究生招生接收调剂公告
51/1返回列表
查看: 781  |  回复: 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返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 366求调剂 +6 sbdnd 2026-04-03 6/300 2026-04-03 11:18 by wangjy2002
[考研] 281求调剂 +3 aaawhy 2026-04-03 3/150 2026-04-03 11:02 by ditto77778
[考研] 一志愿a区211，085601-307分求调剂 +13 党嘉豪 2026-03-31 26/1300 2026-04-03 08:33 by 495374996
[考研] 土木304求调剂 +4 兔突突突， 2026-04-02 5/250 2026-04-02 21:16 by 兔突突突，
[考研] 348求调剂 +11 zzzzyk123 2026-04-01 11/550 2026-04-02 16:52 by Wang200018
[考研] 求调剂 +7 Aniyaio 2026-04-02 7/350 2026-04-02 16:42 by zzsw+
[考研] 学硕化学工程与技术，一志愿中国海洋大学320+求调剂 +8 披星河 2026-04-02 8/400 2026-04-02 14:12 by oooqiao
[考研] 材料科学与工程调剂 +18 深V宿舍吧 2026-03-30 19/950 2026-04-02 10:28 by sanrepian
[考研] 329求调剂 +8 miaodesi 2026-04-02 10/500 2026-04-02 10:24 by 不吃魚的貓
[考研] 一志愿厦门大学化学工程（专硕）-数二英二406分-求调剂 +5 厦大化工 2026-04-01 5/250 2026-04-02 10:03 by jp9609
[考研] 332求调剂 +8 Lyy930824@ 2026-03-29 8/400 2026-04-01 18:40 by 千钧澄玉宇啊
[考研] 283求调剂 +9 A child 2026-03-28 9/450 2026-04-01 14:20 by Jaylen.
[考研] 315求调剂 +6 akie... 2026-03-28 7/350 2026-03-31 16:48 by asdfzly
[考研] 材料工程专硕求调剂 +10 hyl3153942 2026-03-29 10/500 2026-03-31 16:31 by hypershenger
[考研] 266求调剂 +3 哇呼哼呼哼 2026-03-29 3/150 2026-03-31 10:06 by cal0306
[考研] 福建理工大学材料学院先进合金团队招收考研调剂学生 +3 大华金商都 2026-03-30 4/200 2026-03-31 01:04 by 方英俊602
[考研] 327求调剂 +5 小卡不卡. 2026-03-29 5/250 2026-03-30 19:30 by Wang200018
[考研] 0703 化学 求调剂，一志愿山东大学 342 分 +7 Shern—- 2026-03-28 7/350 2026-03-30 16:31 by nothing投稿中
[考研] 291求调剂 +5 Y-cap 2026-03-29 6/300 2026-03-29 13:18 by mumin1990
[考研] 305求调剂 +8 RuiFairyrui 2026-03-28 8/400 2026-03-29 08:22 by fmesaito
信息提示
关闭
请填处理意见
关闭