## 引子


rules = [
('userLoanLimit', 'platformLoanLimit'),
('platformLoanLimit', 'PreRepayment'),
('platformLoanLimit', 'userAge'),
('userLoanLimit', 'userAge'),
('userAge', 'userEducation'),
('userAge', 'baiqishi'),
('userEducation', 'PreRepayment'),
('PreRepayment', 'RepaymentTimes'),
('RepaymentTimes', 'baiqishi'),
('PreRepayment', 'baiqishi'),
('baiqishi', 'tianji')
]


import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
%matplotlib notebook

rules = [
('userLoanLimit', 'platformLoanLimit'),
('platformLoanLimit', 'PreRepayment'),
('platformLoanLimit', 'userAge'),
('userLoanLimit', 'userAge'),
('userAge', 'userEducation'),
('userAge', 'baiqishi'),
('userEducation', 'PreRepayment'),
('PreRepayment', 'RepaymentTimes'),
('RepaymentTimes', 'baiqishi'),
('PreRepayment', 'baiqishi'),
('baiqishi', 'tianji')
]
G = nx.DiGraph()

pos = nx.shell_layout(G)
nx.draw_networkx(G, pos, node_size=500, alpha=0.6, arrowsize=10, arrowstyle='->')

<IPython.core.display.Javascript object>


## 拓扑排序的实现

### Kanh算法

Kanh算法的思想大概是这样子的:

• 维护一个队列，将所有入度为0的节点依次排队
• 对于队列中的每个节点，输出，然后删掉它与其他节点的边，即它指向的节点入度都要减1，这个时候如果有入度为0的节点，也放进队列
• 不断循环上面一个步骤，直到所有节点都处理完

from collections import deque

class Graph:
def __init__(self, rules):
# 邻接表
# 入度
self.in_degree = {}

for rule in rules:

# 计算各个节点的入度
if rule[0] not in self.in_degree:
self.in_degree[rule[0]] = 0
if rule[1] not in self.in_degree:
self.in_degree[rule[1]] = 0
self.in_degree[rule[1]] += 1

def topological_sort_kanh(self):
result = []
queue = deque([node for node in self.in_degree if self.in_degree[node] == 0])
while len(queue) > 0:
node = queue.popleft()
result.append(node)
continue
self.in_degree[neighbor] -= 1
if self.in_degree[neighbor] == 0:
queue.append(neighbor)
return result

graph = Graph(rules)
result = graph.topological_sort_kanh()
print(result)

['userLoanLimit', 'platformLoanLimit', 'userAge', 'userName', 'userEducation', 'PreRepayment', 'RepaymentTimes', 'baiqishi', 'tianji']


### 深度优先搜索实现

from collections import deque

class DiGraph:
def __init__(self, rules):
# 邻接表
# 是否访问过
self.marked = {}

for rule in rules:
self.marked[rule[0]] = False
self.marked[rule[1]] = False
def topological_sort_dfs(self):
result = deque([])
if not self.marked[node]:
self.dfs(node, result)
return result

def dfs(self, node, result):
self.marked[node] = True
if not self.marked[neighbor]:
self.dfs(neighbor, result)
result.appendleft(node)

graph = DiGraph(rules)
result = graph.topological_sort_dfs()
print(result)

deque(['userLoanLimit', 'platformLoanLimit', 'userAge', 'userEducation', 'userName', 'PreRepayment', 'RepaymentTimes', 'baiqishi', 'tianji'])