提取图中奇数度顶点的边

Question

我有如下图，用邻接矩阵表示 MyCustomVector<MyCustomVector<int>> graph:

0       1       2       3       4       5       6       7       8       9       10      11      12      13      14      15

1       0       1       1       INF     INF     INF     INF     INF     INF     INF     INF     INF     INF     INF     INF
2       1       0       1       1       1       INF     INF     INF     INF     INF     INF     INF     INF     INF     INF
3       1       1       0       INF     INF     1       INF     INF     INF     INF     INF     INF     INF     INF     INF
4       INF     1       INF     0       1       INF     INF     INF     1       INF     INF     INF     INF     INF     INF
5       INF     1       INF     1       0       1       INF     INF     INF     1       1       INF     INF     INF     INF
6       INF     INF     1       INF     1       0       1       INF     1       1       INF     1       INF     INF     INF
7       INF     INF     INF     INF     INF     1       0       1       INF     INF     INF     INF     1       1       1
8       INF     INF     INF     INF     INF     INF     1       0       INF     INF     INF     INF     INF     INF     1
9       INF     INF     INF     1       INF     1       INF     INF     0       INF     INF     INF     INF     INF     INF
10      INF     INF     INF     INF     1       1       INF     INF     INF     0       INF     INF     INF     INF     INF
11      INF     INF     INF     INF     1       INF     INF     INF     INF     INF     0       1       INF     INF     INF
12      INF     INF     INF     INF     INF     1       INF     INF     INF     INF     1       0       INF     INF     INF
13      INF     INF     INF     INF     INF     INF     1       INF     INF     INF     INF     INF     0       1       INF
14      INF     INF     INF     INF     INF     INF     1       INF     INF     INF     INF     INF     1       0       1
15      INF     INF     INF     INF     INF     INF     1       1       INF     INF     INF     INF     INF     1       0

最左边和最上面的列和行只代表#节点。我认为这更容易看到。所有边都是无向的，权重为 1。 INF表示节点A和节点B不共享奇异边。

我可以计算出所有的奇数度顶点，它们是 { 3 4 5 7 14 15 }，它们包含在我拥有的向量中 MyCustomVector<int> oddVertices。我想做的是只用这些顶点和它们的边构建这个图的子图，就像这样。

0       3       4       5       7       14       15   
3       0       INF     INF     INF     INF      INF
4       INF     0       1       INF     INF      INF
5       INF     1       0       INF     INF      INF
7       INF     INF     INF     0       1        1  
14      INF     INF     INF     1       0        1                                             
15      INF     INF     INF     1       1        0

这样我就可以运行 Floyd Warshall 算法在此图上得到

0       3       4       5       7       14       15   
3       0       2       2       2       3        3
4       2       0       1       3       4        4
5       2       1       0       2       1        1
7       2       3       2       0       1        1  
14      3       4       3       1       0        1                                             
15      3       4       3       1       1        0

我在管理邻接矩阵和获取我需要的列时遇到问题。基本上我想做的是

遍历图形
注意我们当前所在的节点包含在oddVertices
添加 oddVertices 中包含的其他节点。

我不能使用除 MyCustomVector 以外的任何其他数据结构，它只有 []、size()、pop_back() 和 push_back() 等基本功能。

Answer 1

简单提取索引子集对应的行和列：

using std::vector;

/*
** input:
**   adjacency list                adj
**   subset of node indices        v
** output:
**   adj list of induced subgraph  subadj
*/
vector<vector<int>> get_subgraph(vector<vector<int>> const &adj, vector<int> const &v)
{
    vector<vector<int>> subadj(v.length(), vector<int>(v.length()));
    for (unsigned int i = 0; i < v.size(); ++i)
        for (unsigned int j = 0; j < v.size(); ++j)
        {
            subadj[i][j] = adj[v[i]][v[j]];
        }
    return subadj;
}

提取图中奇数度顶点的边

Extracting the edges of odd degree vertices in a graph

c++

graph-theory

matrix