New answers tagged

0

Do a BFS from any node, say r, construct the BFS tree. For each edge ({u, v}) in the graph that isn't a tree edge, check whether u.level + v.level is even or odd. If it's odd then the graph has an even cycle. If it's even, then the graph has an odd cycle. Proof: BFS yields the shortest path between nodes r,u and r,v. The levels of the BFS tree are equal to ...


0

It's not answerable in the abstract, without a lot more specifics. It depends on intimate specifics of the computer architecture, what counts as "one" operation, how the tree is represented, and many other details that are usually considered a distraction for purposes of analysis of algorithms. And it wouldn't really be useful in practice anyway; ...


1

It sounds like you don't need to be talking about this as a "graph" data structure.. you have points in R3 and you want to partition them into clusters based on their distances (or their pairwise weight matrix). This is more a statistical clustering problem than a graph clustering problem. Here are some python functions to accomplish these: https://...


Top 50 recent answers are included