图论入门编程

卡码网刷题链接：98. 所有可达路径

一、题目简述

二、编程demo

方法①邻接矩阵

from collections import defaultdict
#简历邻接矩阵
def build_graph(): n, m = map(int,input().split()) graph = [[0 for _ in range(n+1)] for _ in range(n+1)]for _ in range(m): i,j = map(int,input().split()) graph[i][j] = 1return graph,n
#深度优先搜索
def dfs(g,r,i,end,path):if i == end:r.append(path.copy())return for k in range(1,end+1):if g[i][k]:path.append(k)dfs(g,r,k,end,path)path.pop()return 
#主函数
def main():graph,n = build_graph()result = []path = [1]dfs(graph,result,1,n,path)#按格式打印输出if not result:print(-1)for p in result:print(" ".join(map(str,p)))return 
if __name__ == "__main__":main()

方法②邻接表

from collections import defaultdict
def build_graph(): n, m = map(int,input().split()) graph = defaultdict(list) for _ in range(m): i,j = map(int,input().split()) graph[i].append(j)return graph,ndef dfs(g,r,i,end,path):if i == end:r.append(path.copy())return for k in g[i]:path.append(k)dfs(g,r,k,end,path)path.pop()return def main():graph,n = build_graph()result = []path = [1]dfs(graph,result,1,n,path)if not result:print(-1)for p in result:print(" ".join(map(str,p)))return 
if __name__ == "__main__":main()