We study the problem of learning Bayesian network structures from data.\nKoivisto and Sood (2004) and Koivisto (2006) presented algorithms that can\ncompute the exact marginal posterior probability of a subnetwork, e.g., a\nsingle edge, in O(n2n) time and the posterior probabilities for all n(n-1)\npotential edges in O(n2n) total time, assuming that the number of parents per\nnode or the indegree is bounded by a constant. One main drawback of their\nalgorithms is the requirement of a special structure prior that is non uniform\nand does not respect Markov equivalence. In this paper, we develop an algorithm\nthat can compute the exact posterior probability of a subnetwork in O(3n) time\nand the posterior probabilities for all n(n-1) potential edges in O(n3n) total\ntime. Our algorithm also assumes a bounded indegree but allows general\nstructure priors. We demonstrate the applicability of the algorithm on several\ndata sets with up to 20 variables.\n