数据结构第14章 networkX

第14章NetworkX【例14.1】无向图importnetworkxasnximportmatplotlib.pyplotaspltG=nx.Graph()#创建一个空的无向图G.add_edge(1,2,weight=4.2)#添加一个从节点1到节点2的边，权重为4.2G.add_nodes_from([3,4])#添加多个节点nx.draw(G,with_labels=True)plt.show()【例14.2】有向图importnetworkxasnximportmatplotlib.pyplotaspltDG=nx.DiGraph()#创建一个空的有向图DG.add_edge(1,2)#添加一个从节点1到节点2的边DG.add_edge(3,4)#添加一个从节点3到节点4的边nx.draw(DG,with_labels=True)plt.show()【例14.3】多重图importnetworkxasnximportmatplotlib.pyplotasplt#创建一个空的多重图G=nx.MultiGraph()#添加节点G.add_nodes_from([1,2,3])#添加边G.add_edge(1,2,key='a',weight=7)G.add_edge(1,2,key='b',weight=10)G.add_edge(1,3)G.add_edge(2,3)#访问特定的边print(G[1][2]['a'])#访问键为'a'的边的属性#获取所有边的键print(G.get_edge_data(1,2).keys())#删除特定的边G.remove_edge(1,2,key='a')#绘制多重图nx.draw(G,with_labels=True,node_color='lightblue',edge_color='gray')plt.show()【例14.4】节点属性importnetworkxasnx#创建一个无向图G=nx.Graph()#添加节点G.add_node('A')G.add_node('B')G.add_node('C')#添加边G.add_edge('A','B')G.add_edge('A','C')#使用add_node方法添加属性G.add_node('A',color='red',size=10)G.add_node('B',color='blue',size=20)#使用nodes[node]['attr']方式添加属性G.nodes['C']['color']='green'G.nodes['C']['size']=15#获取节点'A'的属性node_A_attrs=G.nodes['A']print(f"Node'A'attributes:{node_A_attrs}")#获取节点'B'的颜色属性color_B=G.nodes['B']['color']print(f"Node'B'color:{color_B}")#获取节点'C'的大小属性size_C=G.nodes['C']['size']print(f"Node'C'size:{size_C}")【例14.5】节点操作importnetworkxasnximportmatplotlib.pyplotaspltG=nx.Graph()#建立一个空的无向图GG.add_node('a')#添加一个节点G.add_nodes_from(['b','c','d','e'])#加点集合nx.add_cycle(G,['f','g','h','j'])#加环H=nx.path_graph(10)#返回由10个节点挨个连接的无向图，所以有9条边G.add_nodes_from(H)#创建一个子图H加入GG.add_node(H)#直接将图作为节点nx.draw(G,with_labels=True)plt.show()print('图中所有的节点',G.nodes())print('图中节点的个数',G.number_of_nodes())G.remove_node(1)#删除指定节点G.remove_nodes_from(['b','c','d','e'])#删除集合中的节点nx.draw(G,with_labels=True)plt.show()print('图中所有的节点',G.nodes())print('图中节点的个数',G.number_of_nodes())【例14.6】边属性importnetworkxasnxG=nx.Graph(day='monday')G.add_edge(1,2,weight=10)#在添加边时分配属性print(G.edges(data=True))G.add_edges_from([(1,3),(4,5)],len=22)#从集合中添加边时分配属性print(G.edges(data='len'))G.add_edges_from([(3,4,{'hight':10}),(1,4,{'high':'unknow'})])print(G.edges(data=True))G[1][2]['weight']=100000#添加或修改属性print(G.edges(data=True))【例14.7】边操作importnetworkxasnximportmatplotlib.pyplotaspltF=nx.Graph()#创建无向图F.add_edge(11,12)#一次添加一条边e=(14,14)#e是一个元组F.add_edge(*e)F.add_edges_from([(1,2),(1,3)])#通过添加list来添加多条边F.add_edges_from(H.edges())nx.draw(F,with_labels=True)plt.show()print('图中所有的边',F.edges())print('图中边的个数',F.number_of_edges())

【例14.8】快速遍历每一条边，可以使用邻接迭代器实现importnetworkxasnximportmatplotlib.pyplotaspltFG=nx.Graph()FG.add_weighted_edges_from([(1,2,0.125),(1,3,0.75),(2,4,1.2),(3,4,0.275)])forn,nbrsinFG.adjacency():fornbr,eattrinnbrs.items():data=eattr['weight']print('(%d,%d,%0.3f)'%(n,nbr,data))nx.draw(FG,with_labels=True)plt.show()【例14.9】筛选weight小于0.5的边importnetworkxasnximportmatplotlib.pyplotaspltFG=nx.Graph()FG.add_weighted_edges_from([(1,2,0.125),(1,3,0.75),(2,4,1.2),(3,4,0.275)])forn,nbrsinFG.adjacency():fornbr,eattrinnbrs.items():data=eattr['weight']ifdata<0.5:print('(%d,%d,%0.3f)'%(n,nbr,data))nx.draw(FG,with_labels=True)plt.show()【例14.10】删除边importnetworkxasnximportmatplotlib.pyplotaspltF=nx.Graph()F.add_weighted_edges_from([(1,2,0.125),(1,3,0.75),(2,4,1.2),(3,4,0.275)])F.remove_edge(1,2)nx.draw(F,with_labels=True)plt.show()14.5.1无向图深度优先搜索【例14.11】举例importnetworkxasnx#创建一个无向图G=nx.Graph()#添加节点G.add_node('A')G.add_node('B')G.add_node('C')G.add_node('D')G.add_node('E')#添加边G.add_edge('A','B')G.add_edge('A','C')G.add_edge('B','D')G.add_edge('C','E')#从节点'A'开始进行深度优先搜索dfs_edges=list(nx.dfs_edges(G,source='A'))#打印搜索过程中访问的边print("DFSedges:",dfs_edges)14.5.2有向图深度优先搜索【例14.12】举例importnetworkxasnx#创建一个简单的有向图DG=nx.DiGraph()DG.add_edges_from([(1,2),(1,3),(2,4),(4,3)])#进行深度优先搜索并获取边edges=list(nx.dfs_edges(DG,source=1))print(edges)【例14.13】举例importnetworkxasnx#创建一个简单的无向图G=nx.Graph()G.add_edges_from([(1,2),(1,3),(1,4),(2,4),(3,4)])#进行广度优先搜索并获取边edges=list(nx.bfs_edges(G,source=1))print(edges)14.6.2有向图广度优先搜索importnetworkxasnx#创建一个简单的有向图DG=nx.DiGraph()DG.add_edges_from([(1,2),(1,3),(2,4),(4,3)])#进行广度优先搜索并获取边edges=list(nx.bfs_edges(DG,source=1))print(edges)【例14.15】举例importpandasaspdimportnetworkxasnx#创建一个包含边信息的DataFrameedges_df=pd.DataFrame({'source':['A','B','C','D','E'],'target':['B','C','D','E','F']})#将DataFrame转换为NetworkX图对象G=nx.from_pandas_edgelist(edges_df,source='source',target='target')is_connected=nx.is_connected(G)print(f"Thegraphisconnected:{is_connected}")【例14.16】举例importnetworkxasnx#创建一个无向图G=nx.Graph()#添加边edges=[(1,2),(2,3),(3,4),(4,1),(5,6)]G.add_edges_from(edges)num_components=nx.number_connected_components(G)print(f"Numberofconnectedcomponents:{num_components}")components=list(nx.connected_components(G))forcomponentincomponents:print(f"Connectedcomponent:{component}")【程序运行结果】Numberofconnectedcomponents:2Connectedcomponent:{1,2,3,4}Connectedcomponent:{5,6}【例14.17】无权图示例importnetworkxasnx#创建一个简单的无权图G=nx.Graph()G.add_edges_from([(1,2),(1,3),(1,4),(2,4),(3,4)])#计算从节点1到节点4的最短路径path=nx.shortest_path(G,source=1,target=4)print(path)14.8.2加权图最短路径【例14.18】加权图示例importnetworkxasnx#创建一个简单的加权图G=nx.Graph()G.add_edge(1,2,weight=3)G.add_edge(1,3,weight=5)G.add_edge(2,4,weight=1)G.add_edge(3,4,weight=2)#计算从节点1到节点4的最短路径（按权重）path=nx.shortest_path(G,source=1,target=4,weight='weight')print(path)14.9.1分析恋情关系importnetworkxasnximportmatplotlib.pyplotasplt#创建一个空的有向图G=nx.DiGraph()#添加节点和边，表示恋情关系G.add_edge('Alice','Bob',relationship='love')G.add_edge('Charlie','Alice',relationship='love')G.add_edge('Bob','Diana',relationship='love')G.add_edge('Diana','Eve',relationship='love')#计算节点的度中心性degree_centrality=nx.degree_centrality(G)print("节点的度中心性:",degree_centrality)#可视化网络pos=nx.spring_layout(G)nx.draw(G,pos,with_labels=True,node_color='lightblue',edge_color='gray',arrows=True)plt.show()14.9.2网页链接关系importnetworkxasnx#创建一个有向图DG=nx.DiGraph()#添加节点DG.add_nodes_from(["Page1","Page2","Page3"])#添加有向边，表示链接关系DG.add_edges_from([("Page1","Page2"),("Page2","Page3"),("Page3","Page1")])#计算节点的入度in_degrees=DG.in_degree()print("入度:",in_degrees)#计算节点的出度out_degrees=DG.out_degree()print("出度:",out_degrees)14.9.3交通网络分析importnetworkxasnximportmatplotlib.pyplotasplt#创建一个交通网络图G=nx.Graph()#添加节点和边，表示交通路线G.add_edge('A','B',weight=5)G.add_edge('B','C',weight=3)G.add_edge('A','C',weight=10)G.add_edge('C','D',weight=2)G.add_edge('B','D',weight=8)#计算从A到D的最短路径shortest_path=nx.shortest_path(G