import networkx as nx
import matplotlib.pyplot as plt

# 创建一个空的无向图
G = nx.Graph()

# 添加节点
G.add_node(1)
G.add_node(2)
G.add_node(3)

# 添加边
G.add_edge(1, 2)
G.add_edge(2, 3)

# 绘制图
nx.draw(G, with_labels=True)
plt.show()

import networkx as nx

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(set(graph[vertex]) - visited)
    return visited

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
G.add_edges_from(edges)

# 执行深度优先搜索
visited_nodes = dfs(G, 1)
print("深度优先搜索访问的节点:", visited_nodes)

import networkx as nx
from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
G.add_edges_from(edges)

# 执行广度优先搜索
visited_nodes = bfs(G, 1)
print("广度优先搜索访问的节点:", visited_nodes)

import networkx as nx
import heapq

def dijkstra(graph, start):
    # 初始化距离字典和优先队列
    distances = {node: float('inf') for node in graph.nodes}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight['weight']
            
            if distance < distances[neighbor]:
                distances[neighbor]

 = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2, 1), (1, 3, 4), (2, 3, 2), (2, 4, 7), (3, 4, 3)]
G.add_weighted_edges_from(edges)

# 执行 Dijkstra 算法
shortest_paths = dijkstra(G, 1)
print("Dijkstra 算法求得的最短路径:", shortest_paths)

import networkx as nx

def bellman_ford(graph, start):
    # 初始化距离字典
    distances = {node: float('inf') for node in graph.nodes}
    distances[start] = 0
    
    # 松弛边
    for _ in range(len(graph.nodes) - 1):
        for u, v, data in graph.edges(data=True):
            if distances[u] + data['weight'] < distances[v]:
                distances[v] = distances[u] + data['weight']
    
    # 检测负权重回路
    for u, v, data in graph.edges(data=True):
        if distances[u] + data['weight'] < distances[v]:
            raise ValueError("图中包含负权重回路")
    
    return distances

# 创建一个示例图
G = nx.DiGraph()
edges = [(1, 2, 1), (1, 3, 4), (2, 3, -3), (2, 4, 2), (3, 4, 3)]
G.add_weighted_edges_from(edges)

# 执行 Bellman-Ford 算法
shortest_paths = bellman_ford(G, 1)
print("Bellman-Ford 算法求得的最短路径:", shortest_paths)

import networkx as nx

def ford_fulkerson(graph, source, sink):
    flow = 0
    residual_graph = graph.copy()
    parent = {}
    
    def bfs(source, sink, parent):
        visited = set()
        queue = [source]
        visited.add(source)
        
        while queue:
            u = queue.pop(0)
            for v, capacity in residual_graph[u].items():
                if v not in visited and capacity > 0:
                    queue.append(v)
                    visited.add(v)
                    parent[v] = u
                    if v == sink:
                        return True
        return False
    
    while bfs(source, sink, parent):
        path_flow = float('inf')
        s = sink
        
        while s != source:
            path_flow = min(path_flow, residual_graph[parent[s]][s])
            s = parent[s]
        
        v = sink
        while v != source:
            u = parent[v]
            residual_graph[u][v] -= path_flow
            residual_graph[v][u] += path_flow
            v = parent[v]
        
        flow += path_flow
    
    return flow

# 创建一个示例图
G = nx.DiGraph()
edges = [(1, 2, 16), (1, 3, 13), (2, 3, 10), (2, 4, 12), (3, 2, 4), (3, 5, 14), (4, 3, 9), (4, 6, 20), (5, 4, 7), (5, 6, 4)]
for u, v, capacity in edges:
    G.add_edge(u, v, capacity=capacity)

# 执行 Ford-Fulkerson 算法
max_flow = ford_fulkerson(G, 1, 6)
print("Ford-Fulkerson 算法求得的最大流:", max_flow)

import networkx as nx

def kruskal(graph):
    mst = []
    edges = list(graph.edges(data=True))
    edges.sort(key=lambda x: x[2]['weight'])
    parent = {node: node for node in graph.nodes}
    
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]
    
    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            parent[root2] = root1
    
    for u, v, data in edges:
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, data['weight']))
    
    return mst

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2, 1), (1, 3, 4), (2, 3, 2), (2, 4, 7), (3, 4, 3)]
G.add_weighted_edges_from(edges)

# 执行 Kruskal 算法
mst = kruskal(G)
print("Kruskal 算法求得的最小生成树:", mst)

import networkx as nx
import heapq

def prim(graph, start):
    mst = []
    visited = set()
    edges = [(weight, start, to) for to, weight in graph[start].items()]
    heapq.heapify(edges)
    
    while edges:
        weight, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, weight))
            for to_next, weight in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (weight, to, to_next))
    
    return mst

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2, 1), (1, 3, 4), (2, 3, 2), (2, 4, 7), (3, 4, 3)]
G.add_weighted_edges_from(edges)

# 执行 Prim 算法
mst = prim(G, 1)
print("Prim 算法求得的最小生成树:", mst)

import networkx as nx
from collections import deque

def topological_sort(graph):
    in_degree = {node: 0 for node in graph.nodes}
    for u in graph.nodes:
        for v in graph.neighbors(u):
            in_degree[v] += 1
    
    queue = deque([node for node in graph.nodes if in_degree[node] == 0])
    top_order = []
    
    while queue:
        u = queue.popleft()
        top_order.append(u)
        
        for v in graph.neighbors(u):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    if len(top_order) == len(graph.nodes):
        return top_order
    else:
        raise ValueError("图中存在环，无法进行拓扑排序")

# 创建一个示例图
G = nx.DiGraph()
edges = [(1, 2), (1, 3), (3, 4), (4, 5), (2, 5)]
G.add_edges_from(edges)

# 执行拓扑排序算法
top_order = topological_sort(G)
print("拓扑排序结果:", top_order)

import networkx as nx

def connected_components(graph):
    visited = set()
    components = []
    
    def dfs(node, component):
        stack = [node]
        while stack:
            u = stack.pop()
            if u not in visited:
                visited.add(u)
                component.append(u)
                for v in graph.neighbors(u):
                    if v not in visited:
                        stack.append(v)
    
    for node in graph.nodes:
        if node not in visited:
            component = []
            dfs(node, component)
            components.append(component)
    
    return components

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (2, 3), (4, 5)]
G.add_edges_from(edges)

# 检测连通分量
components = connected_components(G)
print("连通分量:", components)

import networkx as nx

def tarjan(graph):
    index = 0
    stack = []
    indices = {}
    lowlinks = {}
    on_stack = set()
    sccs = []

    def strongconnect(node):
        nonlocal index
        indices[node] = index
        lowlinks[node] = index
        index += 1
        stack.append(node)
        on_stack.add(node)

        for neighbor in graph.neighbors(node):
            if neighbor not in indices:
                strongconnect(neighbor)
                lowlinks[node] = min(lowlinks[node], lowlinks[neighbor])
            elif neighbor in on_stack:
                lowlinks[node] = min(lowlinks[node], indices[neighbor])

        if lowlinks[node] == indices[node]:
            scc = []
            while True:
                w = stack.pop()
                on_stack.remove(w)
                scc.append(w)
                if w == node:
                    break
            sccs.append(scc)

    for node in graph.nodes:
        if node not in indices:
            strongconnect(node)

    return sccs

# 创建一个示例图
G = nx.DiGraph()
edges = [(1, 2), (2, 3), (3, 1), (4, 2), (4, 3), (4, 5), (5, 4), (5, 6)]
G.add_edges_from(edges)

# 执行 Tarjan 算法
sccs = tarjan(G)
print("强连通分量:", sccs)

import networkx as nx

def is_isomorphic(graph1, graph2):
    return nx.is_isomorphic(graph1, graph2)

# 创建两个示例图
G1 = nx.Graph()
edges1 = [(1, 2), (2, 3), (3, 1), (3, 4)]
G1.add_edges_from(edges1)

G2 = nx.Graph()
edges2 = [(5, 6), (6, 7), (7, 5), (7, 8)]
G

2.add_edges_from(edges2)

# 检测图的同构
isomorphic = is_isomorphic(G1, G2)
print("G1 和 G2 是否同构:", isomorphic)

import networkx as nx

def degree_centrality(graph):
    return nx.degree_centrality(graph)

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)]
G.add_edges_from(edges)

# 计算度中心性
centrality = degree_centrality(G)
print("度中心性:", centrality)

import networkx as nx

def betweenness_centrality(graph):
    return nx.betweenness_centrality(graph)

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)]
G.add_edges_from(edges)

# 计算介数中心性
centrality = betweenness_centrality(G)
print("介数中心性:", centrality)

import networkx as nx

def closeness_centrality(graph):
    return nx.closeness_centrality(graph)

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)]
G.add_edges_from(edges)

# 计算接近度中心性
centrality = closeness_centrality(G)
print("接近度中心性:", centrality)

import networkx as nx

def eigenvector_centrality(graph):
    return nx.eigenvector_centrality(graph)

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)]
G.add_edges_from(edges)

# 计算特征向量中心性
centrality = eigenvector_centrality(G)
print("特征向量中心性:", centrality)

import networkx as nx

def maximum_matching(graph):
    return nx.max_weight_matching(graph, maxcardinality=True)

# 创建一个示例二分图
G = nx.Graph()
edges = [(1, 'A'), (2, 'B'), (3, 'C'), (1, 'B'), (2, 'C')]
G.add_edges_from(edges)

# 计算最大匹配
matching = maximum_matching(G)
print("最大匹配:", matching)

import networkx as nx

def minimum_coloring(graph):
    return nx.coloring.greedy_color(graph, strategy='largest_first')

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)]
G.add_edges_from(edges)

# 计算最小染色
coloring = minimum_coloring(G)
print("最小染色:", coloring)

import networkx as nx
import community as community_louvain

def louvain_community_detection(graph):
    return community_louvain.best_partition(graph)

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (1, 3), (2, 4)]
G.add_edges_from(edges)

# 执行 Louvain 算法进行社区检测
communities = louvain_community_detection(G)
print("社区检测结果:", communities)

import networkx as nx
from networkx.algorithms.community import girvan_newman

def girvan_newman_community_detection(graph):
    communities = girvan_newman(graph)
    return next(communities)

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (1, 3), (2, 4)]
G.add_edges_from(edges)

# 执行 GN 算法进行社区检测
communities = girvan_newman_community_detection(G)
print("社区检测结果:", [list(c) for c in communities])

import networkx as nx
from networkx.algorithms.approximation import steiner_tree

def path_decomposition(graph):
    return list(nx.approximation.steiner_tree(graph, graph.nodes))

# 创建一个示例图
G = nx.Graph()
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (1, 3), (2, 4)]
G.add_edges_from(edges)

# 执行路径分解
paths = path_decomposition(G)
print("路径分解结果:", paths)