核心思想就是对图进行遍历,至于选择DFS(深度优先搜索)还是BFS(广度优先搜索)要根据情况考虑,如果不光需要知道能否有路径到达,还要知道有多少条路径,可以考虑采用DFS。如果只是判断是否存在路径,则只需广度优先搜索即可。从一个点,向外扩展到其它的点,再从这些点又开始向开扩展,直到没有节点可以被扩展即可判断是否存在路径。再打个比方,好比在一个点倒水,这些水会通过有向边流到其它的点,再在这些上一步流到的点继续倒水,它又会继续向周边通过有向边流到其他的点,一直重复,直到没有新的点有水流到。
PS:在不统计路径数量的前提下,选择BFS时间复杂度远低于DFS,速度更快。
string[] s={"january", "february", "march", "april", "may", "june", "july", "august", "september", "october", "november", "december"};
system.out.print("请输入数字(1-12):");
bufferedreader br=new bufferedreader(new inputstreamreader(system.in));
string str=br.readline();
int m=integer.parseint(str);
if (m<=0||m>=13)
{=0||m>
用户登录
还没有账号?立即注册
用户注册
投稿取消
文章分类: |
|
还能输入300字
上传中....