如何确定两个节点是否连接? [英] How to determine if two nodes are connected?

问题描述

我担心这可能会解决NP-Complete问题.我希望有人可以给我一个答案，答案是否正确.我正在寻找的答案不仅仅是是"或不是".我想知道为什么.如果您可以说，这基本上是这个问题'x'，它不是NP完全的.(维基百科链接)"

I'm concerned that this might be working on an NP-Complete problem. I'm hoping someone can give me an answer as to whether it is or not. And I'm looking for more of an answer than just yes or no. I'd like to know why. If you can say,"This is basically this problem 'x' which is/is not NP-Complete. (wikipedia link)"

(不，这不是家庭作业)

(No this is not homework)

有没有一种方法可以确定两个点是否连接在任意无向图上.例如以下

Is there a way to determine if two points are connected on an arbitrary non-directed graph. e.g., the following

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

点A到M(没有'I')是可以打开或关闭的控制点(如天然气管道中的阀门). "+"是节点(如管道T一样)，我想井"和房屋"也是节点.

Points A though M (no 'I') are control points (like a valve in a natural gas pipe) that can be either open or closed. The '+'s are nodes (like pipe T's), and I guess the Well and the House are also nodes as well.

我想知道我是否关闭了任意控制点(例如C)，井和房屋是否仍处于连接状态(其他控制点也可能处于关闭状态).例如，如果B，K和D关闭，那么我们仍然有一条通过A-E-J-F-C-G-L-M的路径，而关闭C将断开水井和房屋的连接.当然;如果仅关闭D，则仅关闭C不会断开房屋.

I'd like to know if I shut an arbitrary control point (e.g., C) whether the Well and House are still connected (other control points may also be closed). E.g., if B, K and D are closed, we still have a path through A-E-J-F-C-G-L-M, and closing C will disconnect the Well and the House. Of course; if just D was closed, closing only C does not disconnect the House.

另一种表达方式是C是桥/切边/峡部吗?

Another way of putting this, is C a bridge/cut edge/isthmus?

我可以将每个控制点都视为图表上的权重(打开时为0或关闭时为1)；然后找到Well和House之间的最短路径(结果> = 1表示它们已断开连接.我也可以通过多种方法来短路用于查找最短路径的算法(例如，一旦路径到达1，则丢弃该路径，然后停止一旦我们有了连接井井和房屋等的任何路径，就可以进行搜索.)当然，我还可以对放弃之前要检查的跃点数设置一些人为的限制.

I could treat each control point as a weight on the graph (either 0 for open or 1 for closed); and then find the shortest path between Well and House (a result >= 1 would indicate that they were disconnected. There's various ways I can short circuit the algorithm for finding the shortest path too (e.g., discard a path once it reaches 1, stop searching once we have ANY path that connects the Well and the House, etc.). And of course, I can also put in some artificial limit on how many hops to check before giving up.

有人必须对这种问题进行分类，我只是想念这个名字.

Someone must have classified this kind of problem before, I'm just missing the name.

推荐答案

请参见 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ，这是您解决所有图形相关问题的一站式服务.我相信您的问题实际上可以在二次时间内解决.

See http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , your one stop shop for all graph related problems. I believe your problem is in fact solvable in quadratic time.

这篇关于如何确定两个节点是否连接?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！