图解算法笔记|广度优先算法

1. 图

图由节点和边组成,一个节点可以与众多节点相连,这些节点被称为为邻居

2. 广度优先

广度优先解决的问题:

• 是否有两个节点之间的路线
• 求解两节点之间的最短路径.

广度优先算法的实现:

图中有很多个节点,选取其中给一个作为起点,然后将它和邻居节点放到队列中,然后每次弹出一个节点,查询他是不是已经被查询过了,没有被查询过的话检测他是不是目标节点,如果不是,则将他的邻居节点追加到队列的尾部,如此反复,直至队列清空

这里需要注意的是,图中节点的执行可能存在循环指向的问题,所以需要另外准备一个容器去存放,标记这些已经被检测的节点,

如果从起点开始,所有的方向都是朝着一个方向的,或者说不存在循环指向的话,那就是树

还有一点需要说明一下,就是在确定最短距离时,因为压入队列是有先后顺序的,前面如果找到了,则说明是最短路径,可以当即结束,或者记录下来,当然如果需要记录路径过程,可以在设计结构的时候将打入队列的字符串里包含上含有上级节点的信息

3.实现

python:

graph ={}
graph["a"]=["b","d"]
graph["b"] = ["c"]
graph["d"] = ["e","f"]
graph["e"] = ["f"]
graph["f"] = []
graph["c"] = []

def person_is_seller(name):
    print(name)
    return name=='f'

def bfs(name):
    queue=[]
    searched = []
    queue.append([name])
    print("init queue:",queue)
    while(queue):
        path = queue.pop(0)
        print("path:",path)
        node = path[-1]
        if node not in searched:
            if person_is_seller(node):
                print("找到了:",path)
                return 
            else:
                # 如果不是,则将路径拼装好后放进queue
                # 这里得到的graph[person],这里需要遍历后与之前的path组合成一个新的path
                for element in graph.get(node,[]):
                    new_path = list(path)
                    print("newpath",new_path)
                    new_path.append(element)
                    queue.append(new_path)
                    searched.append(node)

bfs("a")
复制代码

php:

<?php

function person_is_seller($name){
    return $name=="f";
}

function bfs($name,$graph){
    $queue = [];
    $searched = [];
    $path = "";
    $queue[] = [$name];
    while(!empty($queue)){
        $path = array_shift($queue);
        $node = $path[count($path)-1];
        if(!in_array($node,$searched)){
            if(person_is_seller($node)){
                var_dump("最短路径:",$path);
                return true;
            }
            foreach($graph[$node] as $v){
                $new_path = $path;
                array_push($new_path,$v);
                array_push($queue,$new_path);
            }
            array_push($searched,$node);
        }
    }
}

$graph["a"]=["b","d"];
$graph["b"] = ["c"];
$graph["d"] = ["e","f"];
$graph["e"] = ["f"];
$graph["f"] = [];
$graph["c"] = [];
$res = bfs("a",$graph);
复制代码

golang:

package main

import (
	"fmt"
)

var a int

type node map[string][]string
type path []string

func main() {

	var graph = make(node, 6)
	graph["a"] = []string{"b", "d"}
	graph["b"] = []string{"c"}
	graph["d"] = []string{"e", "f"}
	graph["e"] = []string{"f"}
	graph["f"] = []string{}
	graph["c"] = []string{}

	res := bsf("a", graph)
	fmt.Println(res)
}

func check(name string) bool {
	return name == "f"
}

func bsf(name string, graph node) bool {
	//1.首先将节点放进队列
	var queue []path
	start := []string{name}
	var search = make(map[string]string)

	queue = append(queue, start)
	//然后开始循环遍历，
	for len(queue) > 0 {
		path := queue[0]
		node := path[len(path)-1]
		queue = queue[1:]
		//判断遍历的节点是否在search中
		if _, ok := search[node]; !ok {
			if check(node) {
				//找到路径
				fmt.Println("最短路径:", path)
				return true
			}
			//不满足条件,将他里面的联系方式放到队列中

			for _, value := range graph[node] {
				new_path := append(path, value)
				queue = append(queue, new_path)
			}
			search[node] = node
		}
	}
	return false
}

复制代码