基于矩阵实现的广度优先搜索

àì夳堔傛蜴生んèń 2022-08-18 00:53 2阅读 0赞

# 1.广度优先算法 #

广度优先算法是指，从指定结点，沿着图的宽度遍历所有节点。在Wikipedia上的定义如下：

> *Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.*

# 2.传统算法 #

## 2.1算法思想 ##

广度优先搜索类似于树的层次遍历。其算法思路如下：

1.  从图中的某个顶点V出发，访问之；并将其访问标志置为已被访问，即visited\[i\]=1；
2.  依次访问顶点V的各个未被访问过的邻接 点，将V的全部邻接点都访问到；
3.  分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，并使“先被访问的顶 点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问过的顶 点的邻接点都被访问到。

依此类推，直到图中所有顶点都被访问完为止。

## 2.2算法实现 ##

下面是Java实现的无向图的广度优先搜索：

public class BreadthFirstPaths {
        private static final int INFINITY = Integer.MAX_VALUE;
        private boolean[] marked;  // marked[v] = is there an s-v path
        private int[] edgeTo;      // edgeTo[v] = previous edge on shortest s-v path
        private int[] distTo;      // distTo[v] = number of edges shortest s-v path
    
        /**
         * Computes the shortest path between the source vertex <tt>s</tt>
         * and every other vertex in the graph <tt>G</tt>.
         * @param G the graph
         * @param s the source vertex
         */
        public BreadthFirstPaths(Graph G, int s) {
            marked = new boolean[G.V()];
            distTo = new int[G.V()];
            edgeTo = new int[G.V()];
            bfs(G, s);
    
            assert check(G, s);
        }
    
        /**
         * Computes the shortest path between any one of the source vertices in <tt>sources</tt>
         * and every other vertex in graph <tt>G</tt>.
         * @param G the graph
         * @param sources the source vertices
         */
        public BreadthFirstPaths(Graph G, Iterable<Integer> sources) {
            marked = new boolean[G.V()];
            distTo = new int[G.V()];
            edgeTo = new int[G.V()];
            for (int v = 0; v < G.V(); v++)
                distTo[v] = INFINITY;
            bfs(G, sources);
        }
    
    
        // breadth-first search from a single source
        private void bfs(Graph G, int s) {
            Queue<Integer> q = new Queue<Integer>();
            for (int v = 0; v < G.V(); v++)
                distTo[v] = INFINITY;
            distTo[s] = 0;
            marked[s] = true;
            q.enqueue(s);
    
            while (!q.isEmpty()) {
                int v = q.dequeue();
                for (int w : G.adj(v)) {
                    if (!marked[w]) {
                        edgeTo[w] = v;
                        distTo[w] = distTo[v] + 1;
                        marked[w] = true;
                        q.enqueue(w);
                    }
                }
            }
        }
    
        // breadth-first search from multiple sources
        private void bfs(Graph G, Iterable<Integer> sources) {
            Queue<Integer> q = new Queue<Integer>();
            for (int s : sources) {
                marked[s] = true;
                distTo[s] = 0;
                q.enqueue(s);
            }
            while (!q.isEmpty()) {
                int v = q.dequeue();
                for (int w : G.adj(v)) {
                    if (!marked[w]) {
                        edgeTo[w] = v;
                        distTo[w] = distTo[v] + 1;
                        marked[w] = true;
                        q.enqueue(w);
                    }
                }
            }
        }
    
        /**
         * Is there a path between the source vertex <tt>s</tt> (or sources) and vertex <tt>v</tt>?
         * @param v the vertex
         * @return <tt>true</tt> if there is a path, and <tt>false</tt> otherwise
         */
        public boolean hasPathTo(int v) {
            return marked[v];
        }
    
        /**
         * Returns the number of edges in a shortest path between the source vertex <tt>s</tt>
         * (or sources) and vertex <tt>v</tt>?
         * @param v the vertex
         * @return the number of edges in a shortest path
         */
        public int distTo(int v) {
            return distTo[v];
        }
    
        /**
         * Returns a shortest path between the source vertex <tt>s</tt> (or sources)
         * and <tt>v</tt>, or <tt>null</tt> if no such path.
         * @param v the vertex
         * @return the sequence of vertices on a shortest path, as an Iterable
         */
        public Iterable<Integer> pathTo(int v) {
            if (!hasPathTo(v)) return null;
            Stack<Integer> path = new Stack<Integer>();
            int x;
            for (x = v; distTo[x] != 0; x = edgeTo[x])
                path.push(x);
            path.push(x);
            return path;
        }
    
    
        // check optimality conditions for single source
        private boolean check(Graph G, int s) {
    
            // check that the distance of s = 0
            if (distTo[s] != 0) {
                StdOut.println("distance of source " + s + " to itself = " + distTo[s]);
                return false;
            }
    
            // check that for each edge v-w dist[w] <= dist[v] + 1
            // provided v is reachable from s
            for (int v = 0; v < G.V(); v++) {
                for (int w : G.adj(v)) {
                    if (hasPathTo(v) != hasPathTo(w)) {
                        StdOut.println("edge " + v + "-" + w);
                        StdOut.println("hasPathTo(" + v + ") = " + hasPathTo(v));
                        StdOut.println("hasPathTo(" + w + ") = " + hasPathTo(w));
                        return false;
                    }
                    if (hasPathTo(v) && (distTo[w] > distTo[v] + 1)) {
                        StdOut.println("edge " + v + "-" + w);
                        StdOut.println("distTo[" + v + "] = " + distTo[v]);
                        StdOut.println("distTo[" + w + "] = " + distTo[w]);
                        return false;
                    }
                }
            }
    
            // check that v = edgeTo[w] satisfies distTo[w] + distTo[v] + 1
            // provided v is reachable from s
            for (int w = 0; w < G.V(); w++) {
                if (!hasPathTo(w) || w == s) continue;
                int v = edgeTo[w];
                if (distTo[w] != distTo[v] + 1) {
                    StdOut.println("shortest path edge " + v + "-" + w);
                    StdOut.println("distTo[" + v + "] = " + distTo[v]);
                    StdOut.println("distTo[" + w + "] = " + distTo[w]);
                    return false;
                }
            }
    
            return true;
        }
    
        /**
         * Unit tests the <tt>BreadthFirstPaths</tt> data type.
         */
        public static void main(String[] args) {
            In in = new In(args[0]);
            Graph G = new Graph(in);
            // StdOut.println(G);
    
            int s = Integer.parseInt(args[1]);
            BreadthFirstPaths bfs = new BreadthFirstPaths(G, s);
    
            for (int v = 0; v < G.V(); v++) {
                if (bfs.hasPathTo(v)) {
                    StdOut.printf("%d to %d (%d):  ", s, v, bfs.distTo(v));
                    for (int x : bfs.pathTo(v)) {
                        if (x == s) StdOut.print(x);
                        else        StdOut.print("-" + x);
                    }
                    StdOut.println();
                }
                else {
                    StdOut.printf("%d to %d (-):  not connected\n", s, v);
                }
            }
        }
    }

# 3.基于矩阵的算法 #

## 3.1算法推导 ##

邻接矩阵的定义形式：结点i和结点j邻接，则邻接矩阵A(i，j) =1；邻接矩阵对角线元素值为1，即A(i，i)=1；结点i和结点j不邻接，则邻接矩阵A(i，j)=0，可表示为：

![Center][]

起始向量定义形式为：

![Center 1][]

此时，由 ![Center 2][]表示y的第i行，包含结点i的邻结点，即y的第i行中非零值，是结点i经过一条路径连接的顶点。以此类推，经过若干次相乘，即经过若干次搜索，可以得到BFS搜索结果。用公式可以表示为：

![Center 3][]

亦可参考下图演示过程：

![Center 4][]

其中BFS向量每经过一次乘运算后，新添加的非零值即为搜索结点。  
另外，不难发现如果用![Center 5][]与对角矩阵X进行若干次相乘后，即可得到以图中每个结点为起点，进行BFS搜索后构成的结果矩阵。

## 3.2算法实现 ##

用Python实现的代码：

import numpy as np
    from numpy.random import rand
    
    def init(dimension, startVertex = 0):
        mat = np.ones((dimension, dimension), dtype = np.int32)
        mat[(rand(dimension ** 2 / 2) * dimension).astype(int), (rand(dimension ** 2 / 2) * dimension).astype(int)] = 0
        for i in range(dimension):
            mat[i, i] = 1
        return mat
    
    def bfsSingal(adjacencyMat, startVertex):
        def nonZeroNum(vector):
            return len(np.nonzero(vector)[0])
        adjacencyMat = adjacencyMat.T
        n = np.shape(adjacencyMat)[0]
        current = np.zeros((n, 1), dtype = np.int32)
        current[startVertex, 0] = 1
        i = 0
        stop = False
        print("The %sth search: %s" % (i, current.T))
        while(not stop):
            i += 1
            next = np.dot(adjacencyMat, current)
            stop = nonZeroNum(current) == nonZeroNum(next)
            if(not stop):
                current = next
                print("The %sth search: %s" % (i, current.T))
            
    if __name__ == "__main__":
        adjacencyMat = init(7, 3)
        adjacencyMat1 = np.array([[1, 1, 0, 1, 0, 0, 0],
                          [0, 1, 0, 0, 1, 0, 1],
                          [0, 0, 1, 0, 0, 1, 0],
                          [1, 0, 1, 1, 0, 0, 0],
                          [0, 0, 0, 0, 1, 1, 0],
                          [0, 0, 1, 0, 0, 1, 0],
                          [0, 0, 1, 1, 1, 0, 1]])
        adjacencyMat2 = np.array([[1, 1, 0, 1, 0, 0, 0],
                          [0, 1, 0, 0, 1, 0, 1],
                          [0, 0, 1, 0, 0, 1, 0],
                          [1, 0, 1, 1, 0, 0, 0],
                          [0, 0, 0, 0, 1, 1, 0],
                          [0, 0, 1, 0, 0, 1, 1],
                          [0, 0, 1, 1, 1, 0, 1]])
        bfsSingal(adjacencyMat1, 3)

[Center]: /images/20220731/ea2fb8ad89f947118b2050e05eac8f80.png
[Center 1]: /images/20220731/065623b0e7e14a5b94055d3e85df6c70.png
[Center 2]: /images/20220731/9295d8d7d1d045c59fc79d5162da0cb9.png
[Center 3]: /images/20220731/6ef942e0b48c49d6bb59f856e6dd1d24.png
[Center 4]: /images/20220731/f513ee3c624b4e86a89321d6ac3f81b8.png
[Center 5]: /images/20220731/069337e09d0d4c4bb1a5692a546ef564.png