判断图是否为有向无环图的基本思想为：从任意点出发，都不会再回到该点。
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
