c++ - 如何将邻接矩阵转换为关联矩阵，反之亦然？

Question

假设矩阵如下:(N = 4)

邻接:

0110100110010110

发生率:

1100101001010011

如何通过邻接矩阵获得关联矩阵，反之亦然？

P.S: 我从一个 .txt 文件中得到的邻接矩阵，我已经读入一个数组并通过以下算法得到它:

int read(){

    ifstream graf("graf.txt");
    if(graf.is_open()){
        graf >> n;
        for (int i=0; i < n; i++) {
        for(int j = 0; j<2; j++)
                graf >> Graf[i][j];
        }
    }
    graf.close();
    return 0;
}

void adj() {
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        sz[i][j] = 0;
    for (int i=0; i<n; i++)
        for (int j=0; j<2; j++)
        {sz[Graf[i][j]-1][Graf[i][j+1]-1] = 1;}
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        sz[j][i] = sz[i][j];
}

Answer 1

您可以通过查看顶点之间的每个可能连接将邻接矩阵转换为关联矩阵，只要确实存在连接，就向关联矩阵添加一条边。不过，请注意只查看每个顶点组合一次。

反过来，您可以简单地查看每条边。关联矩阵为每条边指定它连接的两个顶点。

您无法重新创建的一种情况是多条边连接相同的两个顶点。

这里有一些源代码来说明上面的解释(See it work):

#include <vector>
#include <cassert>
#include <iostream>

typedef std::vector<bool> matrix_row;
typedef std::vector<matrix_row> matrix; // Saves some typing

// The initially given matrix. Uses C++11 initializer list.
matrix adj = 
{
    { 1, 1, 1, 0 },
    { 1, 0, 0, 1 },
    { 1, 0, 0, 1 },
    { 0, 1, 1, 0 }
};

matrix adjacency_to_incidence(const matrix &adj)
{
    int cols = adj.size();
    assert(cols > 0);

    int rows = adj[0].size();
    assert(rows > 0);

    assert(rows == cols);

    int edge = 0;
    matrix incidence;

    for (int col = 0; col < cols; ++col) {
        // We only look at half the adjacency matrix, so that we only add each
        // edge to the incidence matrix once.
        for (int row = 0; row <= col; ++row) {
            if (adj[col][row]) {
                incidence.push_back(matrix_row(cols, 0));
                incidence[edge][row] = incidence[edge][col] = 1;
                ++edge;
            }
        }
    }

    return incidence;
}

matrix incidence_to_adjacency(const matrix &inc)
{
    int edges = inc.size();
    assert(edges > 0);

    int vertices = inc[0].size();
    assert(vertices > 0);

    matrix adjacency(vertices, matrix_row(vertices, 0));

    for (int edge = 0; edge < edges; ++edge) {
        int a = -1, b = -1, vertex = 0;
        for (; vertex < vertices && a == -1; ++vertex) {
            if (inc[edge][vertex]) a = vertex;
        }
        for (; vertex < vertices && b == -1; ++vertex) {
            if (inc[edge][vertex]) b = vertex;
        }
        if (b == -1) b = a;
        adjacency[a][b] = adjacency[b][a] = 1;
    }

    return adjacency;
}

void print_matrix(const matrix &m)
{
    int cols = m.size();
    if (cols == 0) return;
    int rows = m[0].size();
    if (rows == 0) return;

    for (int c = 0; c < cols; ++c) {
        for (int r = 0; r < rows; ++r) {
            std::cout << m[c][r] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

int main()
{
    matrix incidence = adjacency_to_incidence(adj);
    print_matrix(incidence);

    matrix adjacency = incidence_to_adjacency(incidence);
    print_matrix(adjacency);

    return 0;
}

当您的图表很大时，可能值得考虑在 adjacency_to_incidence 中运行循环两次。第一次计算边的数量，然后用足够的空间初始化矩阵，然后再次遍历邻接矩阵以填充关联矩阵。