如何构造DAG的双向矩阵?

我相信你不能为DAG构造一个双向矩阵,因为不是每个DAG都是二部图。

下面是一个简单的例子:考虑一个有3个顶点的有向图,并将它们表示为a、b和c。边缘连接a到b、b到c和a到c。该图显然是一个DAG,因为它是有向的,没有循环(a->b->c<-a不是循环)。然而,该图不是二部图:没有办法将A、B和C划分为两个不相交集,在同一集合中顶点之间没有边。

结论是,有图形是DAG而不是二分体,所以不是每个DAG都是二分体。

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

似乎只有在图是无向的情况下,才能构造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 = 0 B
    C 0

这将需要2个*(n/2)^2空间,该空间仍优于n^2。

要构造B矩阵和C矩阵,只需在U和V中的每个节点上循环(分别),以确定出站边缘。

下面的代码将创建给定邻接矩阵的双邻接矩阵,如果它是双邻接矩阵(只有双邻接图具有双邻接矩阵)。如果给定图不是双邻接,getBiadjacencyMatrix()方法返回空值。

Graph of the provided sample including its biadjacency matrix http://www.freeimagehosting.net/image.php?10e9b6a746.jpg

看不到图像? Click here

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; }
    }
}

你的双相邻矩阵A的规定对称性, 和 您打算使用拓扑排序来隔离图中的二部分结构-指出实际上您指的是 间接的 ,非循环的,图形-即树。 (对称明确地说,如果你有一条从x到y的边,你必须有一条从y到x的边——因此,方向性变得毫无意义)。

假设这确实是你的意图:

(1)对于任何间接图,您可以 立即 通过只存储邻接矩阵的上三角形,确定约0.5*(n^2)(精确地:n(n-1)/2)。

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

您必须首先识别不相交的子集,例如R&S,每个子集都没有内部边缘。拓扑排序是一个合理的选择-在树中,它相当于选择一个根,并通过在根上的偶数/奇数级别标记顶点(与 common visualizations 我更喜欢把一棵树想象成真正的生长 在上面 它的根…我从你的问题中了解到你对此很满意,所以我甚至不会给出伪代码。

接下来,您需要重新标记顶点,以便所有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;

(一些优化立刻浮现在脑海中,但在这里并不重要)。

然后,您可以连续扫描图形边缘,并将其作为条目存储到r x s矩阵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.