Golang 广度优先搜索图

图是由边或者我们可以说节点和顶点组成的数据结构。顶点是节点之间的连接线。为了遍历所有这些节点，我们有不同的遍历算法。在本文中，我们将讨论广度优先搜索或者我们可以说BFS。在广度优先搜索中，我们首先从一个节点开始，然后移动到另一个节点，直到遇到死胡同。

范例

步骤

第一步： 使用import关键字在顶部导入所需的包。

第二步： 然后，主函数将首先运行。

• 首先，我们声明并初始化图。

• 然后，我们使用图和节点作为参数调用BFS()函数。

第三步： 在BFS()函数中，以下步骤将在每个函数调用上运行。

isvisited := make(map[int]bool)

创建一个用于存储节点是否已访问的数据的地图。

var bfsQueue Queue

为队列数据结构创建一个参数。

isvisited[node] = true, bfsQueue.Enqueue(node)

将通过的节点标记为已访问，并将节点添加到队列中。

对所有连接的节点运行一个for循环，并将它们添加到队列中。

示例1

在这个示例中，我们将图表示为一个矩阵，并对矩阵应用广度优先搜索。这种方法的复杂度为O(e*e)，其中e是边的数量，空间复杂度为O(e*e)，即矩阵的大小。

package main

import "fmt"

type Queue struct {
    List []int
}

// function to add element in queue
func (q *Queue) Enqueue(element int) {
    q.List = append(q.List, element)
}

// function to delete element in the queue
func (q *Queue) Dequeue() int {
    if q.isEmpty() {
        fmt.Println("Queue is empty.")
        return 0
    }
    element := q.List[0]
    q.List = q.List[1:]

    return element
}

// function check that queue is empty or not
func (q *Queue) isEmpty() bool {
    return len(q.List) == 0
}

// BFS() is a function with matrix and int value as parameter
func BFS(graph [][]int, node int) {
    // initializing the map that will keep
    // the track is the node is visited or not
    isvisited := make(map[int]bool)

    // creating a Queue variable
    // in which we will add an element at the same level
    // of that node
    var bfsQueue Queue

    // marking current node as visited
    isvisited[node] = true

    // adding a current node in the queue
    bfsQueue.Enqueue(node)

    // running a for loop until the queue becomes empty
    for !bfsQueue.isEmpty() {
        currNode := bfsQueue.List[0]
        fmt.Print(currNode, " ")
        // adding all the connected node in queue if not visted
        for nodes := 0; nodes < len(graph[currNode]); nodes++ {
            if graph[currNode][nodes] == 1 && !isvisited[nodes] {
                bfsQueue.Enqueue(nodes)
                isvisited[nodes] = true
            }
        }
        // removing the current node from queue
        // after visiting
        bfsQueue.Dequeue()
    }
}

func main() {
    // matrix representation of the undirected connected graph
    // where if the value is 1 the node i is connected
    // with node j
    graph := [][]int{{0, 1, 0, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}, {1, 0, 1, 0}}

    fmt.Println("Golang program to do Breath first search of an undirected connected graph represented in the form of a matrix.")

    // calling BFS() function for the breadth-first search
    // traversal of a graph
    BFS(graph, 0)

    fmt.Println()
}

输出

Golang program to do Breath first search of an undirected connected graph represented in the form of a matrix.
0 1 3 2

示例2

在这个示例中，我们将图表示为邻接表的形式，并相应地应用广度优先搜索。这种方法的复杂度为O(e*v)，其中e是边的数量，v是顶点的数量。空间复杂度为O(e*v)，即邻接表的大小。

package main

import "fmt"

type Queue struct {
    List []int
}

// function to add an element in the queue
func (q *Queue) Enqueue(element int) {
    q.List = append(q.List, element)
}

// function to delete elements in the queue
func (q *Queue) Dequeue() int {
    if q.isEmpty() {
        fmt.Println("Queue is empty.")
        return 0
    }
    element := q.List[0]
    q.List = q.List[1:]

    return element
}

// function checks whether the queue is empty or not
func (q *Queue) isEmpty() bool {
    return len(q.List) == 0
}

// BFS() is a function with matrix and int value as parameter
func BFS(graph [4][]int, node int) {
    //Initializing the map that will keep
    // the track is the node is visited or not
    isvisited := make(map[int]bool)

    // creating a Queue variable
    // in which we will add elements at the same level
    // of that node
    var bfsQueue Queue

    // marking current node as visited
    isvisited[node] = true

    // adding the current node in the queue
    bfsQueue.Enqueue(node)

    // running a for loop until the queue becomes empty
    for !bfsQueue.isEmpty() {
        currNode := bfsQueue.List[0]
        fmt.Print(currNode, " ")
        // adding all the connected nodes in the queue if not visited
        for _, nodes := range graph[currNode] {
            if !isvisited[nodes] {
                bfsQueue.Enqueue(nodes)
                isvisited[nodes] = true
            }
        }
        // removing the current node from queue
        // after visiting
        bfsQueue.Dequeue()
    }
}

func main() {
    //adjacency list representation of the undirected connected graph
    // where if the value is 1 the node i is connected
    // with node j
    var graph [4][]int

    // initializing each list of the array
    graph[0] = []int{1, 3}
    graph[1] = []int{0, 2}
    graph[2] = []int{1, 3}
    graph[3] = []int{0, 2}

    fmt.Println("Golang program to do Breath first search of an undirected connected graph represented in the form of an adjacency list.")

    // calling BFS() function for the breadth-first search
    // traversal of a graph
    BFS(graph, 0)

    fmt.Println()
}

输出

Golang program to do Breath first search of an undirected connected graph represented in the form of an adjacency list.
0 1 3 2

结论

这是表示图数据结构和运行广度优先搜索算法的两种不同方式。第二种方法是创建邻接表，从时间和空间的角度来看更高效，因为我们将与节点连接的节点编号添加到数组中。要了解更多关于Golang的知识，可以探索这些教程。