Python 判断 有向图 是否有环的实例讲解

yipeiwu_com5年前Python基础

实例如下:

import numpy
from numpy import *
def dfs( v ):
 vis[v] = -1
 flag = 0
 for i in range(n):
 # print (a[v][i],'---', vis[i] )
 if a[v][i] != 0 and vis[i] != -1:
  dfs(i)
  vis[i] = 1
 else:
  pass
 if a[v][i] != 0 and vis[i] == -1:
  print ('Yes, there is A loop in this network\n')
  global swi
  swi = True
  exit()
  return
  # break
 else:
  pass
 print ('s = 0')
 return False

global swi
swi = False
'''===装载数据'''
edges = numpy.loadtxt('9_nodes_with_r_edge_8_to_3.txt')

# edges = [ int(i) for i in edges]
bian = int(shape(edges)[0]) - 1
print (bian,'edges in the network \n')
print (shape(edges),'\n')

n = int( edges[0][1] )

c = int( edges[0][0] )
# n, c = input().split()
# n = int(n)
# c = int(c)
a = [([0] * n) for i in range(n)]
vis = [0] * c
for i in range(1, c+1):
 s, t = edges[i][0:2]
 # print (s,' - ', t )
 '''GO_OBO文件则 s, t 不需要 -1 '''
 s = int(s) - 1
 t = int(t) - 1
 # s = int(s)
 # t = int(t)
 a[s][t] = 1
# print (a)
# print (vis)
dfs(0)
# print (swi)
if not swi:
 print('No loop, DAG - DAG - DAG')

用到 numpy 模块,读取的 txt 文件为 有向图的连边,其中第一行 第一个数字 为 边的数量,第二个数字为 节点数 第二行及以后 前两个数字,第一个为 起点, 第二个为 落点。

以上这篇Python 判断 有向图 是否有环的实例讲解就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

Django学习笔记之为Model添加Action

在使用Django自带的admin后台的时候,他提供了一些默认的指令可以对数据进行操作, 比如批量删除,修改等 同样的我们也可以添加自己的指令。 |- Django版本:1.8 |- P...

在Python中表示一个对象的方法

在 Python 中一切都是对象。如果要在 Python 中表示一个对象,除了定义 class 外还有哪些方式呢?我们今天就来盘点一下。 0x00 dict...

python实现数组插入新元素的方法

本文实例讲述了python实现数组插入新元素的方法。分享给大家供大家参考。具体如下: li=['a', 'b'] li.insert(0,"c") 输出为:['c', 'a'...

numpy创建单位矩阵和对角矩阵的实例

在学习linear regression时经常处理的数据一般多是矩阵或者n维向量的数据形式,所以必须对矩阵有一定的认识基础。 numpy中创建单位矩阵借助identity()函数。更为准...

Python实现的拉格朗日插值法示例

本文实例讲述了Python实现的拉格朗日插值法。分享给大家供大家参考,具体如下: 拉格朗日插值简单介绍 拉格朗日插值法是以法国十八世纪数学家约瑟夫·拉格朗日命名的一种多项式插值方法。 许...