如何判断一个图是否为有向无环图（DAG）

判断图是否为有向无环图的基本思想为：从任意点出发，都不会再回到该点。
Description：
Input:邻接矩阵
color:用来记录节点被访问的情况。‘0’代表未被访问过，‘1代表正在访问’，‘-1’代表该点的后裔节点都已经被访问过。在一次搜索中，若某点的状态为1，则该点之前被访问过，存在环。若某点的状态为‘-1’，则该点的后裔点均被访问过，跳过该次搜索。若某点的状态为‘0’，则该点之前没有被访问过，DFS该点。

class Graph(object):
    def __init__(self,G):
      self.G = G
      self.color = [0] * len(G)
      self.isDAG = True
        
    def DFS(self,i):
        self.color[i] = 1
        for j in range(len(self.G)):
            if self.G[i][j] != 0:
                if self.color[j] == 1:
                    self.isDAG = False
                elif self.color[j] == -1:
                    continue
                else:
                    print('We are visiting node' + str(j + 1))
                    self.DFS(j)
        self.color[i] = -1

    def DAG(self):
        for i in range(len(self.G)):
            if self.color[i] == 0:
                self.DFS(i)
     

本文分别用一个有向无圈图和一个有向有圈图做测试：

acyclic_directed_graph.png

G = [[0,0,1,0,0,0],
     [0,0,1,0,0,0],
     [0,0,0,1,0,0],
     [0,0,0,0,1,1],
     [0,0,0,0,0,0],
     [0,0,0,0,0,0]]

G1 = Graph(G)
G1.DAG()
G1.isDAG

acyclic.png

cyclic_directed_graph.png

G = [[0,0,1,0,0,0,0],
     [0,0,1,0,0,0,0],
     [0,0,0,1,0,0,0],
     [0,0,0,0,1,1,0],
     [0,0,0,0,0,0,0],
     [0,0,0,0,0,0,1],
     [0,0,0,1,0,0,0]]

G2 = Graph(G)
G2.DAG()
G2.isDAG

cyclic.png