如何构建 DAG 的双邻接矩阵？

Question

对于二分图，您可以替换邻接矩阵 及其所谓的 邻接矩阵：

部分具有 r 和 s 顶点的二部图的邻接矩阵 A 具有以下形式

    A =  O  B
         BT O

其中 B 是 r × s 矩阵，O 是全零矩阵。 显然，矩阵B唯一地表示了二部图，通常称为二部邻接矩阵。

现在，DAG 是一个二分图，例如，您可以拓扑排序它并得到将 U 和 V 分别设置为奇数或偶数拓扑级别上的节点。

这意味着，对于具有 n 个节点的 DAG，我只需要 (n/2)² 矩阵（平均）而不是 n² 矩阵。 问题是，我不知道如何构建它。 有什么提示吗？

Answer 1

我相信你不能为 DAG 构建双邻接矩阵，因为并非每个 DAG 都是二部图。

这是一个简单的例子：考虑一个有 3 个顶点的有向图，并将它们表示为 A、B 和 C。边将 A 连接到 B、B 连接到 C、A 连接到 C。该图显然是一个 DAG，因为它是有向的并且不存在循环（A->B->C<-A 不是循环）。 然而，该图不是二分图：无法将 A、B 和 C 分为两个不相交的集合，其中同一集合中的顶点之间没有边。

结论是存在有向无环图，但不是二分图，因此并非每个 DAG 都是二分图。

请注意，您可以对 DAG 进行拓扑排序并将顶点划分为两个不相交的集合，但这并不意味着同一集合的顶点之间没有边。

Answer 2

看来只有当图无向时才能构造 A 矩阵的双邻接矩阵 B。

基于维基百科的示例：

此 DAG 的邻接矩阵应为：

Blue -> Red
B = 1 1 0 0
    0 0 1 0
    0 0 0 0
    0 0 0 0
    0 0 0 1

Red -> Blue
C = 0 1 0 0 0
    0 1 0 0 0
    0 0 1 1 1
    0 0 0 0 0

如您所见，C 不是 B 的转置。按照描述创建 A 矩阵似乎是不可能的。 但是，您可以创建这样的 A 矩阵：

A = 0 B
    C 0

这将需要 2 * (n/2)^2 空间，这仍然比 n^2 更好。

要构造 B 和 C 矩阵，您只需（分别）循环 U 和 V 中的每个节点即可确定出站边。

Answer 3

如果给定的邻接矩阵是二分图，以下代码将创建二分邻接矩阵（只有二分图才有二分邻接矩阵。）如果给定的图不是二分图，则 GetBiadjacencyMatrix() 方法返回 null。

所提供样本的图表，包括其邻接矩阵 http://www.freeimagehosting.net/image .php?10e9b6a746.jpg

看不到图像？ 点击此处

public class Matrix
{
    private void Usage()
    {
        int[,] AdjacencyMatrix = new int[,] { 
                                        {0, 1, 1, 0, 0, 0, 0, 0, 0},
                                        {1, 0, 0, 1, 0, 0, 0, 0, 0},
                                        {1, 0, 0, 1, 0, 0, 0, 0, 0},
                                        {0, 1, 1, 0, 1, 0, 0, 0, 0},
                                        {0, 0, 0, 1, 0, 1, 1, 1, 0},
                                        {0, 0, 0, 0, 1, 0, 0, 0, 0},
                                        {0, 0, 0, 0, 1, 0, 0, 0, 0},
                                        {0, 0, 0, 0, 1, 0, 0, 0, 1},
                                        {0, 0, 0, 0, 0, 0, 0, 1, 0}
                                       };

        int[,] BiadjacencyMatrix = GetBiadjacencyMatrix(AdjacencyMatrix);
    }

    public static int[,] GetBiadjacencyMatrix(int[,] adjacencyMatrix)
    {
        int NodeCount = adjacencyMatrix.GetLength(0);

        NodeInfo[] Nodes = new NodeInfo[NodeCount];
        for (int c = NodeCount - 1; c >= 0; c--)
            Nodes[c] = new NodeInfo(c);

        if (ColorNode(adjacencyMatrix, Nodes, 0, 1, -1) != NodeCount)
            return null; // Given graph is not bipatite.

        int Part1Count = 0, Part2Count = 0;
        foreach (NodeInfo Node in Nodes)
            Node.IndexInPart = Node.PartID == 1 ? Part1Count++ : Part2Count++;

        int[,] ToReturn = new int[Part1Count, Part2Count];
        foreach (NodeInfo NodeInPart1 in Nodes)
            if (NodeInPart1.PartID == 1)
                foreach (NodeInfo NodeInPart2 in Nodes)
                    if (NodeInPart2.PartID == 2)
                        ToReturn[NodeInPart1.IndexInPart, NodeInPart2.IndexInPart]
                            = adjacencyMatrix[NodeInPart1.IndexInGraph, NodeInPart2.IndexInGraph];

        return ToReturn;
    }

    private static int ColorNode(int[,] adjacencyMatrix, NodeInfo[] nodes, int currentNode, int currentPart, int parentNode)
    {
        if (nodes[currentNode].PartID != -1) 
            return nodes[currentNode].PartID != currentPart ? -1 : 0;
        int ToReturn = 1;
        nodes[currentNode].PartID = currentPart;
        for (int c = nodes.Length - 1; c >= 0; c--)
            if (adjacencyMatrix[currentNode, c] != 0 && c != parentNode)
            {
                int More = ColorNode(adjacencyMatrix, nodes, c, currentPart == 1 ? 2 : 1, currentNode);
                if (More == -1) return -1;
                ToReturn += More;
            }
        return ToReturn;
    }
}


public class NodeInfo
{
    private int _IndexInGraph;
    private int _PartID;
    private int _IndexInPart;
    private bool _IsVisited;

    public NodeInfo(int indexInGraph)
    {
        _IndexInGraph = indexInGraph;
        _PartID = -1;
        _IndexInPart = -1;
        _IsVisited = false;
    }

    public int IndexInGraph
    {
        get { return _IndexInGraph; }
        set { _IndexInGraph = value; }
    }

    public int PartID
    {
        get { return _PartID; }
        set { _PartID = value; }
    }

    public int IndexInPart
    {
        get { return _IndexInPart; }
        set { _IndexInPart = value; }
    }

    public bool IsVisited
    {
        get { return _IsVisited; }
        set { _IsVisited = value; }
    }
}

Answer 4

双邻接矩阵 A 的对称性，和您使用拓扑排序来隔离图中二分结构的意图 - 指出您实际上指的是间接，无环图，即树。
（对称性明确表示，如果有从 x 到 y 的边，则必须有从 y 到 x 的边 - 因此，有向性变得毫无意义）。

假设这确实是您的意图：

(1) 对于任何间接图，您可以立即满足大约 0.5*(n^2) （确切地说：n(n-1)/2），通过仅存储邻接矩阵的上三角形。

(2) 假设您必须仅存储 B。

您必须首先识别不相交的子集，例如 R 和 B。 S，每个都没有内部边缘。 拓扑排序是一个看似合理的选项 - 在树中，它相当于选择一个根并通过位于根之上的偶数/奇数级别来标记顶点（与 常见可视化，我更喜欢将树视为实际上生长在其根部之上..）。 我从你的问题中了解到你对此感到满意，所以我什至不会给出伪代码。

接下来，您需要重新标记顶点，以便所有 R 的顶点首先出现，所有 S 的顶点紧随其后：（

Allocate NewLabels(r + s);
CurRSize = 0;
CurSSize = 0;
for each (TreeLevel)
    if #CurLevel is even  // append to R vertices
       NewLabels(CurRSize : CurRsize + CurLevelSize - 1) = CurLevelVertexNums;
       CurRSize += CurLevelSize;
    else // append to S vertices
       NewLabels(r+s - (CurSSize+CurLevelSize) : r+s - (CurSSize + 1) = CurLevelVertexNums;
       CurSSize += CurLevelSize;

一些优化立即浮现在脑海中，但它们在这里并不重要）。

然后，您可以连续扫描图边，并将它们作为条目存储到 rxs 矩阵 B 中，由新顶点标签

Allocate B(r,s);
Zero(B);
for each (edge = x<-->y)
   i = NewLabels(x);
   j = NewLabels(y) - r; // must adjust, to index just B
   B(i,j) = 1;

HTH 进行索引。