Reseaech On BFS Based Spanning Tree Updating Strategy For Dynamic Graph

As a basic algorithm in graph theory,breadth first search(BFS)has a high utilization rate.Breadth first traversal of data graph corresponds to a BFS spanning tree,which can be used to solve many problems,such as searching the shortest path,finding the k-step reachability and finding the minimum spanning tree.Given the dynamic graph,the BFS spanning tree update strategy is used to solve the problem of how to maintain the BFS spanning tree efficiently when the data graph is updated frequently.In the existing methods,either the BFS spanning tree is reconstructed by global re traversal or the BFS spanning tree is reconstructed locally based on tags,neither of which supports efficient updating.Aiming at the problems of existing methods,this paper proposes a path coding based BFS spanning tree updating and its optimization strategy.The specific research contents are as followsFirstly,aiming at the problems of existing methods,a path coding based BFS spanning tree updating strategy is proposed.Its main idea is to replace the whole reconstruction with partial reconstruction.Firstly,the location of each node in the graph is marked based on path coding,and the whole BFS spanning tree is recorded by recording the absolute location.By marking the path index,when the structure of the graph changes,the whole BFS spanning tree reconstruction is replaced by updating some vertices.The basic BFS tree update algorithm reduces the huge cost of the overall reconstruction through local reconstruction,which makes the BFS spanning tree update more efficient.Secondly,the compressed storage strategy of path coding is proposed to reduce the time and space complexity of path coding.At the same time,a coding update strategy based on incremental update method is proposed to reduce the number of nodes that need to update the coding,thus reducing the time cost of maintaining the path coding and further improving the overall efficiency.Finally,based on 25 real datasets for testing,the experimental results from the index space size,construction time,maintenance time and BFS spanning tree update efficiency and other aspects of comparative analysis,verify that the proposed method has the advantages of small index scale,short construction time and fast maintenance speed.