数据结构第12章 Scipy

TOC\o"1-3"\h\u第12章Scipy【例12.1】举例fromscipy.sparseimportcsr_matriximportnumpyasnprow=np.array([0,1,1,2])col=np.array([1,0,2,1])data=np.array([1,1,1,1])adj_matrix_sparse=csr_matrix((data,(row,col)),shape=(3,3))print(adj_matrix_sparse.toarray())12.2图的遍历12.2.1depth_first_order()importnumpyasnpfromscipy.sparse.csgraphimportdepth_first_orderfromscipy.sparseimportcsr_matrixarr=np.array([[0,1,0,1],[1,1,1,1],[2,1,1,0],[0,1,0,1]])newarr=csr_matrix(arr)print(depth_first_order(newarr,1))12.2.2breadth_first_order()importnumpyasnpfromscipy.sparse.csgraphimportbreadth_first_orderfromscipy.sparseimportcsr_matrixarr=np.array([[0,1,0,1],[1,1,1,1],[2,1,1,0],[0,1,0,1]])newarr=csr_matrix(arr)print(breadth_first_order(newarr,1))12.3最短路径12.3.1迪杰斯特拉算法importnumpyasnpfromscipy.sparse.csgraphimportdijkstrafromscipy.sparseimportcsr_matrixarr=np.array([[0,1,5],[1,0,3],[5,3,0]])print(arr)#输出邻接矩阵newarr=csr_matrix(arr)print("输出以0为起始源点的最短路径")print(dijkstra(newarr,return_predecessors=True,indices=0))print(dijkstra(newarr,return_predecessors=False,indices=0))print("输出以1为起始源点的最短路径")print(dijkstra(newarr,return_predecessors=False,indices=1))print("输出以2为起始源点的最短路径")print(dijkstra(newarr,return_predecessors=False,indices=2))12.3.2佛洛伊德算法importnumpyasnpfromscipy.sparse.csgraphimportfloyd_warshallfromscipy.sparseimportcsr_matrixarr=np.array([[0,1,2],[1,0,0],[2,0,0]])newarr=csr_matrix(arr)print(floyd_warshall(newarr,return_predecessors=False))12.4最小生成树importnumpyasnpfromscipy.sparseimportcsr_matrixfromscipy.sparse.csgraphimportminimum_spanning_tree#创建一个图的邻接矩阵graph=np.array([[0,8,0,3,0],[8,0,2,5,12],[0,2,0,0,10],[3,5,0,0,6],[0,12,10,6,0]])#将邻接矩阵转换为稀疏矩阵sparse_graph=csr_matrix(graph)#计算最小生成树mst=minimum_spanning_tree(sparse_graph)#输出最小生成树的邻接矩阵print(mst.toarray().astype(int))12.5图的连通分量12.5.1无向图的连通分量importnumpyasnpfromscipy.sparseimportcsr_matrixfromscipy.sparse.csgraphimportconnected_components#创建一个无向图的邻接矩阵graph=np.array([[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,0]])#将邻接矩阵转换为稀疏矩阵sparse_graph=csr_matrix(graph)#计算连通分量n_components,labels=connected_components(sparse_graph,directed=False)print("Numberofconnectedcomponents:",n_components)print("Labelsofconnectedcomponents:",labels)12.5.2有向图的连通分量importnumpyasnpfromscipy.sparseimportcsr_matrixfromscipy.sparse.csgraphimportconnected_components#创建一个有向图的邻接矩阵graph=np.array([[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,0,0,0]])#将邻接矩阵转换为稀疏矩阵sparse_graph=csr_matrix(graph)#计算强连通分量n_components_strong,labels_strong=connected_components(sparse_graph,directed=True,connection='strong')print("Numberofstronglyconnectedcomponents:",n_components_strong)print("Labelsofstronglyconnectedcomponents:",labels_strong)#计算弱连通分量n_components_weak,labels_weak=connected_components(sparse_graph,directed=True,connection='weak')print("Numberofweaklyconnectedcomponents:",n_components_weak)print("Labelsofweaklyconnectedcomponents:",labels_weak)12.6实例12.6.1城市交通规划importnumpyasnpfromscipy.sparseimportcsr_matrixfromscipy.sparse.csgraphimportshortest_path#城市道路网络邻接矩阵，权重表示距离road_graph=np.array([[0,5,0,10],[5,0,3,0],[0,3,0,2],[10,0,2,0]])#将邻接矩阵转换为稀疏矩阵sparse_graph=csr_matrix(road_graph)#计算最短路径distances,predecessors=shortest_path(sparse_graph,directed=False,return_predecessors=True)print("Distances:\n",distances)print("Predecessors:\n",predecessors)12.6.2电路网络分析importnumpyasnpfromscipy.sparseimportcsr_matrixfromscipy.sparse.csgraphimportminimum_spanning_tree#构建邻接矩阵data=np.array([2,2,3,3,5,5,6,6,7,7,8,8,9,9])row_indices=np.array([0,1,1,2,1,4,0,3,2,4,1,3,3,4])col_indices=np.array([1,0,2,1,4,1,3,0,4,2,3,1,4,3])adjacency_matrix=csr_matrix((data,(row_indices,col_indices)),shape=(5,5))#计算最小生成树mst=minimum_spanning_tree(adjacency_matrix)print("最小生成树的邻接矩阵：")print(mst.toarray())12.6.3社交网络分析importnumpyasnpfromscipy.sparseimportcsr_matrixfromscipy.sparse.csgraphimportconnected_components#构建社交网络的邻接矩阵data=np.ones(4)row_indices=np.array([0,1,1,3])col_indices=np.array([1,0,2,4])adjacency_ma