广度优先搜索

内容简介：广度优先搜索

广度优先搜索回答两类问题：

1.从节点A出发，有前往节点D的路径吗？
    2.从节点A出发，前往节点D的哪条路径最短？

演示：

代码演示

OC实现代码：

//示例：是否存在A到D的路径
#import "ViewController.h"

@interface ViewController ()
@property(nonatomic,strong)NSDictionary *dic;
@end
@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    _dic = [[NSDictionary alloc] init];
    //把每个节点对应的邻居节点存储起来
    _dic = @{@"A":@[@"B",@"F"],@"B":@[@"C"],@"C":@[@"D"],@"D":@[],@"E":@[@"C"],@"F":@[@"E",@"G"],@"G":@[@"C"]};
    BOOL lj = [self search:@"D"];
    if(lj){
        NSLog(@"存在A到D的路径");
    }else{
        NSLog(@"不存在A到D的路径");
    }
}

-(BOOL)search:(NSString*)str{
    //查找队列
    NSMutableArray *array = [[NSMutableArray alloc] initWithCapacity:0];
    [array addObject:@"A"];
    //存储已经检查过的节点
    NSMutableArray *searchedArr = [[NSMutableArray alloc] initWithCapacity:0];
    //当查找队列不为空
    while ([array count] != 0) {
        //取出队列中的一个元素
        NSString *name = array[0];
        [array removeObjectAtIndex:0];
        //检查这个元素是否被检查过
        if(![searchedArr containsObject:name]){
            //检查是不是要找的节点
            if([name isEqualToString:str]){
                return YES;
            }else{
                //将这个节点对应的邻居节点加入查找队列
                [array addObjectsFromArray:[_dic objectForKey:name]];
                //将这个节点标记为已检查过
                [searchedArr addObject:name];
            }
        }
    }
    return NO;
}
@end

java代码实现：

import java.util.*;
public class MyClass {
    private static Map m1 = new HashMap();
    public static void main(String[] args){
        //把每个节点对应的邻居节点存储起来
        m1.put("A", new String[]{"B", "F"});
        m1.put("B", new String[]{"C"});
        m1.put("C", new String[]{"D"});
        m1.put("D", new String[]{});
        m1.put("E", new String[]{"C"});
        m1.put("F", new String[]{"E","G"});
        m1.put("G", new String[]{"C"});

        boolean lj = search("G");
        if(lj){
            System.out.println("cz");
        }else{
            System.out.println("bcz");
        }
    }

    private static boolean search(String str){
        //查找队列
        Queue<String> queue = new LinkedList<String>();
        queue.offer("A");
        //存储已经检查过的节点
        String[] searchedArray = new String[0];
        //当查找队列不为空
        while (queue.size() != 0){
            //取出队列中的一个元素
            String name = queue.poll();
            //检查这个元素是否被检查过
            if(!Arrays.asList(searchedArray).contains(name)){
                //检查是不是要找的节点
                if(name == str){
                    return true;
                }else{
                    //将这个节点对应的邻居节点加入查找队列
                    String[] s = (String[]) m1.get(name);
                    for(int i = 0;i<s.length;i++){
                        queue.offer(s[i]);
                    }
                    //将这个节点标记为已检查过
                    searchedArray = Arrays.copyOf(searchedArray,searchedArray.length+1);
                    searchedArray[searchedArray.length-1] = name;
                }
            }
        }
        return false;
    }
}

python实现代码：

from collections import deque
def search(str):
    queue = deque()
    queue += 'A'
    searched = []
    while queue:
        name = queue.popleft()
        if not name in searched:
            if name == str:
                return True
            else:
                queue += dict[name]
                searched.append(name)
    return False

dict = {'A':['B','F'],'B':['C'],'C':['D'],'D':[],'E':['C'],'F':['E','G'],'G':['C']}
if search('D'):
    print('cz')
else:
    print('bcz')

以上所述就是小编给大家介绍的《广度优先搜索》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

• 深度优先搜索和广度优先搜索
• 图解：深度优先搜索与广度优先搜索
• 算法图解笔记：广度优先搜索
• 算法(三)：图解广度优先搜索算法
• 【你该懂一点Javascript算法系列】之【图类】的定义及深度优先与广度优先搜索算法
• 算法快学笔记（十二）：图的广度优先搜索(BFS-Breadth First Search)

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。