鱼C论坛

 找回密码
 立即注册
查看: 2720|回复: 3

弗洛伊德最优路径法

[复制链接]
发表于 2019-5-19 20:50:34 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
给定一个有N个顶点和E条边的无向图,请判断给定的两个顶点之间是否有路径存在。 假设顶点从0到N−1编号。
纯技术需求贴
望广大鱼友鼎力相助
输入格式:
输入第1行给出2个整数N(0<N≤10)和E,分别是图的顶点数和边数。

随后E行,每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

最后一行给出两个顶点编号i,j(0≤i,j<N),i和j之间用空格分隔。

输出格式:
如果i和j之间存在路径,则输出"There is a path between i and j.",

否则输出"There is no path between i and j."。

输入样例1:
7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 3

输出样例1:
There is a path between 0 and 3.
输入样例2:
7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 6

输出样例2:
There is no path between 0 and 6.
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2019-5-19 21:56:24 | 显示全部楼层
从一个顶点开始遍历无向图,看能否遍历到另一个顶点。
看起来这是某种练习题吧,这种题还是自己写的好,毕竟这是基础啊
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-5-19 23:37:39 | 显示全部楼层
Croper 发表于 2019-5-19 21:56
从一个顶点开始遍历无向图,看能否遍历到另一个顶点。
看起来这是某种练习题吧,这种题还是自己写的好,毕 ...

老师说;用弗洛伊德最优解,和并查集,最后还有人用DFS做出来的,感觉无力呵
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-5-20 00:10:57 | 显示全部楼层
用Java写的,唉!!
  1. import java.util.Scanner;

  2. public class Main {

  3.         static int visited[]= {0,0,0,0,0,0,0,0,0,0,0};
  4.         static int lianxi[][]= {
  5.                         {0,0,0,0,0,0,0,0,0,0,0},
  6.                         {0,0,0,0,0,0,0,0,0,0,0},
  7.                         {0,0,0,0,0,0,0,0,0,0,0},
  8.                         {0,0,0,0,0,0,0,0,0,0,0},
  9.                         {0,0,0,0,0,0,0,0,0,0,0},
  10.                         {0,0,0,0,0,0,0,0,0,0,0},
  11.                         {0,0,0,0,0,0,0,0,0,0,0},
  12.                         {0,0,0,0,0,0,0,0,0,0,0},
  13.             {0,0,0,0,0,0,0,0,0,0,0},
  14.                         {0,0,0,0,0,0,0,0,0,0,0},
  15.             {0,0,0,0,0,0,0,0,0,0,0}
  16.         };
  17.         static int p=0;
  18.        
  19.         public static void main(String[] args) {
  20.                
  21.                 //int visited[]= {0,0,0,0,0,0,0,0,0,0};
  22.                
  23.                 int N,E;
  24.                 Scanner scanf=new Scanner(System.in);
  25.                 N=scanf.nextInt();
  26.                 E=scanf.nextInt();
  27.                

  28.                
  29.                 for(int i=0;i<E;i++) {
  30.                         int x=scanf.nextInt();
  31.                         int y=scanf.nextInt();
  32.                         lianxi[x][y]=1;
  33.                         lianxi[y][x]=1;
  34.                        
  35.                 }
  36.                
  37.                
  38.                 int i,j;
  39.                 i=scanf.nextInt();
  40.                 j=scanf.nextInt();
  41.                
  42.                 DFS(i,N,j);
  43.                
  44.                 if(p==1)
  45.                         System.out.printf("There is a path between %d and %d.",i,j);
  46.                 else
  47.                         System.out.printf("There is no path between %d and %d.",i,j);
  48.                
  49.         }

  50.         public static void DFS(int v,int n,int j) {
  51.                 if(v==j) {
  52.                         p=1;
  53.                         return;
  54.                 }
  55.                 visited[v]=1;
  56.                 for(int i=0;i<n;i++) {
  57.                         if(visited[i]==0&&lianxi[v][i]==1) {
  58.                                
  59.                                 DFS(i, n, j);       
  60.                         }
  61.                 }
  62.         }
  63.        
  64. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-1 09:14

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表