基于BDD的图表示及其算法

Representation of Graph and Its Algorithms Based on BDD

给出基于二元判决图BDD的无权图和有权图的符号化表示,同时给出该表示下的算法设计及实现,并以连通度算法和最短路径算法作为例子。

A symbolic representation of graph based on ordered binary decision diagram （BDD） is given. The way of how to design algorithms for it is shown. As examples, two symbolic algorithms for connectivity and shortest path problems are given respectively. It is found that the algorithm has obvious advantages especially when the graph becomes larger. When the graph is too huge to be contained in the memory by the routine method, the algorithm here still works due to the compact representation of BDD, which is proved experimentally in this paper.