matrix - 如何构造 DAG 的邻接矩阵？

Question

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

二部图的邻接矩阵 A 的部分具有 r 和 s 个顶点，其形式为

    A = 产科
         B T O

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

现在，DAG 是一个二分图，例如，您可以对其进行拓扑排序，并让集合 U 和 V 分别作为奇数或偶数拓扑级别的节点。

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

Answer 1

我相信你不能为 DAG 构造一个双邻接矩阵，因为不是每个 DAG 都是二分图。

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

结论是有图是 DAG 但不是二分的，所以不是每个 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 & 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。