SYJ.png

廣度優(yōu)先搜索回答兩類問題：

    1.從節(jié)點A出發(fā)，有前往節(jié)點D的路徑嗎？
    2.從節(jié)點A出發(fā)，前往節(jié)點D的哪條路徑最短？

演示：

SYJ.png

代碼演示

OC實現(xiàn)代碼：

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

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

- (void)viewDidLoad {
    [super viewDidLoad];
    _dic = [[NSDictionary alloc] init];
    //把每個節(jié)點對應的鄰居節(jié)點存儲起來
    _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"];
    //存儲已經(jīng)檢查過的節(jié)點
    NSMutableArray *searchedArr = [[NSMutableArray alloc] initWithCapacity:0];
    //當查找隊列不為空
    while ([array count] != 0) {
        //取出隊列中的一個元素
        NSString *name = array[0];
        [array removeObjectAtIndex:0];
        //檢查這個元素是否被檢查過
        if(![searchedArr containsObject:name]){
            //檢查是不是要找的節(jié)點
            if([name isEqualToString:str]){
                return YES;
            }else{
                //將這個節(jié)點對應的鄰居節(jié)點加入查找隊列
                [array addObjectsFromArray:[_dic objectForKey:name]];
                //將這個節(jié)點標記為已檢查過
                [searchedArr addObject:name];
            }
        }
    }
    return NO;
}
@end

java代碼實現(xiàn)：

import java.util.*;
public class MyClass {
    private static Map m1 = new HashMap();
    public static void main(String[] args){
        //把每個節(jié)點對應的鄰居節(jié)點存儲起來
        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");
        //存儲已經(jīng)檢查過的節(jié)點
        String[] searchedArray = new String[0];
        //當查找隊列不為空
        while (queue.size() != 0){
            //取出隊列中的一個元素
            String name = queue.poll();
            //檢查這個元素是否被檢查過
            if(!Arrays.asList(searchedArray).contains(name)){
                //檢查是不是要找的節(jié)點
                if(name == str){
                    return true;
                }else{
                    //將這個節(jié)點對應的鄰居節(jié)點加入查找隊列
                    String[] s = (String[]) m1.get(name);
                    for(int i = 0;i<s.length;i++){
                        queue.offer(s[i]);
                    }
                    //將這個節(jié)點標記為已檢查過
                    searchedArray = Arrays.copyOf(searchedArray,searchedArray.length+1);
                    searchedArray[searchedArray.length-1] = name;
                }
            }
        }
        return false;
    }
}

python實現(xiàn)代碼：

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')