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

24小时热门版块排行榜    

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

xinruirui1

金虫 (初入文坛)

[求助] 急求答案

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

» 猜你喜欢
出师未捷身先死！！！
1楼 2011-06-18 11:03:51
已阅   回复此楼   关注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 个回答

文俊点点

木虫 (著名写手)

【答案】应助回帖

★
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的回帖
查看全部 5 个回答
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 334求调剂 +6 曾仰之 2026-04-03 6/300 2026-04-03 12:07 by wxiongid
[考研] 303求调剂 +3 一色清羽 2026-04-02 4/200 2026-04-03 10:22 by 蓝云思雨
[考研] 282求调剂 +3 aaa车辆 2026-04-02 3/150 2026-04-02 21:55 by zllcz
[考研] 。 +4 雾与海 2026-04-02 5/250 2026-04-02 19:16 by 土木硕士招生
[考研] 081200-11408-276学硕求调剂 +3 崔wj 2026-04-02 3/150 2026-04-02 15:06 by cal0306
[考研] 一志愿北京科技大学085601材料工程英一数二初试总分335求调剂 +8 双马尾痞老板2 2026-04-02 9/450 2026-04-02 14:45 by 5896
[考研] 377求调剂 +3 RASKIN 2026-04-02 3/150 2026-04-02 09:45 by zzchen2000
[考研] 08生物与医药专硕初试346找调剂 +6 dianeeee 2026-04-01 7/350 2026-04-02 08:23 by guoweigw
[考研] 一志愿安徽大学计算机科学与技术学硕，331分求调剂 +5 蒋昌鹏qtj 2026-04-01 5/250 2026-04-02 08:10 by fxue1114
[考研] 材料调剂 +12 一样YWY 2026-04-01 12/600 2026-04-02 00:21 by 百秒光年
[考研] 085410 一志愿211 22408分数359求调剂 +3 123456789qw 2026-03-31 4/200 2026-04-02 00:06 by 义文wang
[考研] 339求调剂，想调回江苏 +7 烤麦芽 2026-03-27 10/500 2026-04-01 21:35 by 495374996
[考研] 0817化工学硕调剂 +11 努力上岸中！ 2026-03-31 11/550 2026-04-01 20:30 by 赖春艳
[考研] 284求调剂 +12 小熊～～ 2026-03-31 12/600 2026-04-01 20:23 by 花??
[考研] 材料调剂 +11 一样YWY 2026-03-31 11/550 2026-04-01 11:35 by wangjy2002
[硕博家园] 博一被送出联培感觉不适应怎么办 +3 全村的狗 2026-03-31 3/150 2026-04-01 10:44 by 328838485
[考研] 070300化学专业279调剂 +10 哈哈哈^_^ 2026-03-31 10/500 2026-03-31 23:13 by liu823948201
[考研] 0856 335分 +9 cccchenso 2026-03-29 9/450 2026-03-31 16:37 by lishahe
[考研] 274求调剂 +6 xiao爱同学 2026-03-30 6/300 2026-03-31 10:04 by cal0306
[考研] 370求调剂 +3 080700调剂 2026-03-30 3/150 2026-03-31 01:09 by A_Zhe
信息提示
关闭
请填处理意见
关闭