Graphic algorithm notes | breadth-first algorithm

1. The figure

A graph consists of nodes and edges. A node can be connected to many nodes, which are called neighbors

2. Breadth first

Breadth-first issues addressed:

• Whether there is a route between two nodes
• Solve the shortest path between two nodes.

Implementation of breadth-first algorithm:

There are a lot of a node in the graph, select one to give as a starting point, and then put it and neighbor nodes in the queue, and then pop up every time a node, whether or not he has been a query, query whether or not he hadn’t been query detection target node, if not, will be his neighbor node appended to the end of the queue, so repeatedly, until the queue is empty

It should be noted here that there may be a problem of circular pointing in the execution of nodes in the figure, so it is necessary to prepare another container to store and mark these detected nodes.

If all directions are pointing in one direction from the starting point, or if there is no loop pointing, it’s a tree

Also need to explain, is to determine the shortest distance, because of the pressure into the queue is sequenced, if found, in front of the show is the shortest path, can end immediately, or, of course, if need to record the path process, can be in design structure changes into the queue on the string contains contains information on the superior nodes

3. The implementation

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("Found it :",path)
                return 
            else:
                If not, assemble the path and put it in queue
                Graph [person], which needs to be traversed together with the previous path to create a new 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")
Copy the code

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("Shortest path :".$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);
Copy the code

golang:

package main

import (
	"fmt"
)

var a int

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

func main(a) {

	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. First put the node into the queue
	var queue []path
	start := []string{name}
	var search = make(map[string]string)

	queue = append(queue, start)
	// Then start the loop,
	for len(queue) > 0 {
		path := queue[0]
		node := path[len(path)- 1]
		queue = queue[1:]
		// Check whether the traversal node is in search
		if_, ok := search[node]; ! ok {if check(node) {
				// Find the path
				fmt.Println("Shortest path :", path)
				return true
			}
			// If the condition is not met, the contact information inside the queue is put into the queue

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

Copy the code