如何检查两个顶点之间的图形连通性
我试图实现一个遗传算法来找到一组边，这些边的移除将会断开图形。 更具体地说，我使用由顶点和边组成的有向无环图。 每条边都有成本或重量。 遗传算法生成大量集合C（即选择两个顶点之间的某些边）。 现在我的问题是检查这组边是否表示剪切集或断开图。 然后，遗传算法正在寻找包含在切割集合中的可能的最小边缘成本总和。
所以，我使用了从图书的算法和优化的Java库中提取的连接图测试这种方法来测试连通性。 这对我不起作用，因为它只扫描顶点的邻居。
public static boolean isConnected(Individual ind)
{
int n= Settings.numOfNodes;
int m= Settings.numOfEdges-ind.cutSet.size();
int nodei[]= new int[m+1];
int nodej[]= new int[m+1];
int tempi[]= new int[m];
int tempj[]= new int[m];
int[] temp= (int[])Settings.nodei.clone();
for(int edg:ind.cutSet)
temp[edg]= -1;
int count=0;
for(int i=0; i<Settings.numOfEdges; i++)
{
if(temp[i]!=-1)
{
tempi[count]=Settings.nodei[i];
tempj[count]=Settings.nodej[i];
count++;
}
}
nodei[0]=0;
nodej[0]=0;
for(int i=0; i<tempi.length;i++)
{
nodei[i+1]=tempi[i];
nodej[i+1]=tempj[i];
}
int i,j,k,r,connect;
int neighbor[] = new int[m + m + 1];
int degree[] = new int[n + 1];
int index[] = new int[n + 2];
int aux1[] = new int[n + 1];
int aux2[] = new int[n + 1];
for (i=1; i<=n; i++)
degree[i] = 0;
for (j=1; j<=m; j++) {
degree[nodei[j]]++;
degree[nodej[j]]++;
}
index[1] = 1;
for (i=1; i<=n; i++) {
index[i+1] = index[i] + degree[i];
degree[i] = 0;
}
for (j=1; j<=m; j++) {
neighbor[index[nodei[j]] + degree[nodei[j]]] = nodej[j];
degree[nodei[j]]++;
neighbor[index[nodej[j]] + degree[nodej[j]]] = nodei[j];
degree[nodej[j]]++;
}
for (i=2; i<=n; i++)
aux1[i] = 1;
aux1[1] = 0;
connect = 1;
aux2[1] = 1;
k = 1;
while (true) {
i = aux2[k];
k--;
for (j=index[i]; j<=index[i+1]-1; j++) {
r = neighbor[j];
if (aux1[r] != 0) {
connect++;
if (connect == n) {
connect /= n;
if (connect == 1) return true;
return false;
}
aux1[r] = 0;
k++;
aux2[k] = r;
}
}
if (k == 0) {
connect /= n;
if (connect == 1) return true;
return false;
}
}
}
给定以下有向无环图：
number of vertices = 4
number of edges = 5
1->2
1->3
1->4
2->4
3->4
如果我们删除以下边缘：
1->2
1->3
2->4
然后，该方法返回该图形断开连接，但仍存在以下路径之一：
1->4
我正在寻找一种算法或方法来检查我们是否删除了一些边，该图仍然连接在开始和目标顶点之间。 换句话说，图形在这两个顶点之间仍然存在一些其他路径。
一个有效集合的例子，当被移除的图表没有连接时：
1->2
1->3
1->4
要么
2->4
1->4
3->4
请给我解答这个问题的任何想法或想法。
谢谢
检查连接性：
您的图形是定向的a-cyclic，因此您可以预处理并查找Paths = { (u,v) | there is a path from u to v } Paths = { (u,v) | there is a path from u to v } 。
删除/添加每个边(u,v)您需要做的就是相应地重置Paths 。 请注意，对于每个v' ， (u,v')在Paths当且仅当存在u' ，使得(u,u')仍然是图中的边，且(u',v')处于Paths 。
不要忘了递归调用Paths递归每个修改u的父母。
虽然这种解决方案在最坏的情况下并不比BFS好，但在平均情况下应该更好 - 因为在每次更改后都不需要浏览整个图。
编辑：例如
例如，在你的图中， Path={(1,2),(1,3),(1,4),(2,4),(3,4)} - 所有顶点到所有路径“前进”顶点除2至3之外。
现在，如果你删除边(1,4)你Path={(1,2),(1,3),(1,4),(2,4),(3,4)}注意(1,4)仍然存在，因为边（1,2）和（2,4）在Path 。
现在删除(2,4) ，它将导致： Path={(1,2),(1,3),(1,4),(3,4)} 。 再次， (1,4)仍然存在，因为(1,3)仍然是边，而(3,4)在Path 。
现在删除(3,4) 。 从3到4没有路径，所以你删除(3,4) 。 现在，递归地修改所有3的父母。 因为1是3的父亲，因此在他身上调用它，并且发现没有更多的边(1,u)使得(u,4)仍然在路径中，因此我们将它从Path移除，导致Path={(1,2),(1,3)} 。
查找要移除的边集：
我将从删除所有边开始 ，添加边而不是删除它们。 您只能添加不会连接图形的边。 通过这种方法，您可以尝试最大化您添加的边的值，而不是最小化您删除的边。
通过这样做 - 您确保您的解决方案可行 ，并且图形确实没有连接。