求图中由一个顶点分开的顶点
求图中由一个顶点分开的顶点
提问于 2012-11-10 12:11:51
你知道有什么算法(比蛮力更好)可以在图中找出由一个顶点分开、互不相连的顶点。示例：
在这个图中，找到的路径是：
- 1-4
- 2-4
- 3-5
最好的是c++代码，它使用stl列表数组作为图形表示，但是使用任何其他过程语言或伪代码的代码也可以。
回答 3
Stack Overflow用户
发布于 2012-11-10 13:44:32
一种方法是基于宽度第一风格的搜索，其中对于图中的每个顶点i，我们扫描与i相邻的顶点(即两层邻接！)。
mark = array[0..n-1] of 0
flag = 1
for i = nodes in graph do
// mark pattern of nodes adjacent to i
mark[i] = flag
for j = nodes adjacent to i do
mark[j] = flag
endfor
// scan nodes adjacent to those adjacent to i
// (separated by one vertex!)
for j = nodes adjacent to i do
for k = nodes adjacent to j do
if mark[k] != flag and k > i then
// i,k are separated by another vertex
// and there is no edge i,k
// prevent duplicates
mark[k] = flag
endif
endfor
endfor
// implicit unmarking of current pattern
flag += 1
endfor如果图的每个顶点都有m边，这将是一个需要O(n)额外空间的O(n * m^2)算法。
Stack Overflow用户
发布于 2012-11-10 14:04:49
解决这个问题的一个简单而直观的方法就是邻接矩阵。如我们所知，邻接矩阵的n次方的(i，j) th元素列出了i和j之间长度正好为n的所有路径。
所以我只读取A，邻接矩阵，然后计算A^2。最后，我列出了它们之间有一条长度为2的路径的所有对。
//sg
#include<stdio.h>
#define MAX_NODE 10
int main()
{
int a[MAX_NODE][MAX_NODE],c[MAX_NODE][MAX_NODE];
int i,j,k,n;
printf("Enter the number of nodes : ");
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
{
printf("Edge from %d to %d (1 yes/0 no) ? : ",i+1,j+1);
scanf("%d",&a[i][j]);
a[j][i]=a[i][j]; //undirected graph
}
//dump the graph
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
c[i][j]=0;
printf("%d",a[i][j]);
}
printf("\n");
}
printf("\n");
//multiply
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
{
c[i][j]+=a[i][k]*a[k][j];
}
//result of the multiplication
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d",c[i][j]);
}
printf("\n");
}
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
{
if(c[i][j]==1&&(!a[i][j])&&(i!=j)) //list the paths
{
printf("\n%d - %d",i+1, j+1 );
}
}
return 0;
}示例运行图
[aman@aman c]$ ./Adjacency2
Enter the number of nodes : 5
Edge from 1 to 1 (1 yes/0 no) ? : 0
Edge from 2 to 1 (1 yes/0 no) ? : 1
Edge from 2 to 2 (1 yes/0 no) ? : 0
Edge from 3 to 1 (1 yes/0 no) ? : 1
Edge from 3 to 2 (1 yes/0 no) ? : 1
Edge from 3 to 3 (1 yes/0 no) ? : 0
Edge from 4 to 1 (1 yes/0 no) ? : 0
Edge from 4 to 2 (1 yes/0 no) ? : 0
Edge from 4 to 3 (1 yes/0 no) ? : 1
Edge from 4 to 4 (1 yes/0 no) ? : 0
Edge from 5 to 1 (1 yes/0 no) ? : 0
Edge from 5 to 2 (1 yes/0 no) ? : 0
Edge from 5 to 3 (1 yes/0 no) ? : 0
Edge from 5 to 4 (1 yes/0 no) ? : 1
Edge from 5 to 5 (1 yes/0 no) ? : 0
01100
10100
11010
00101
00010
21110
12110
11301
11020
00101
4 - 1
4 - 2
5 - 3分析
对于n个顶点：
- 时间: O(n^3)。可以还原为O(n^2.32)，这是非常好的。
- 空间: O(n^2)。
Stack Overflow用户
发布于 2013-06-24 21:51:51
您可以使用经过调整的沃尔算法版本来完成这一任务。下面的代码示例中的算法使用图的邻接矩阵，如果有从i到k的边，从k到j的边，但是没有从i到j的直接方式，则打印i。
#include <iostream>
int main() {
// Adjacency Matrix of your graph
const int n = 5;
bool d[n][n] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0 },
};
// Modified Warshall Algorithm
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
if (d[i][k])
for (int j = 0; j < n; j++)
if (d[k][j] && !d[i][j])
std::cout << i + 1 << " " j + 1 << std::endl;
}您可以查看结果在线。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13321932
复制相关文章
相似问题
腾讯云开发者
