里面用到的主要函数有什么

在实现上述算法时，涉及到一些常用的函数，下面我列出一些常用的函数及其作用：

1. 创建无向网

在使用邻接矩阵存储无向网时，需要创建一个二维数组来存储图的边和权重。可以使用以下函数创建一个二维数组：

def create_graph(n: int, edges: List[Tuple[int, int, int]]) -> List[List[int]]:
    graph = [[float('inf')] * n for _ in range(n)]
    for u, v, w in edges:
        graph[u][v] = graph[v][u] = w
    return graph

其中，n表示图中顶点的个数，edges表示边的列表。

在使用邻接表存储无向网时，需要创建一个列表，其中每个元素指向一个链表，链表中存储了与该顶点相邻的顶点和边的权重。可以使用以下函数创建一个链表：

class Node:
    def __init__(self, v: int, w: int):
        self.v = v
        self.w = w
        self.next = None


def create_graph(n: int, edges: List[Tuple[int, int, int]]) -> List[Node]:
    graph = [None] * n
    for u, v, w in edges:
        node = Node(v, w)
        node.next = graph[u]
        graph[u] = node
        node = Node(u, w)
        node.next = graph[v]
        graph[v] = node
    return graph

其中，n表示图中顶点的个数，edges表示边的列表。

2. 判断连通性

在使用DFS或BFS算法判断无向网的连通性时，需要遍历整个图，可以使用以下函数实现：

def dfs(graph: List[List[int]], visited: List[bool], u: int):
    visited[u] = True
    for v in range(len(graph)):
        if graph[u][v] != float('inf') and not visited[v]:
            dfs(graph, visited, v)


def is_connected(graph: List[List[int]]) -> bool:
    visited = [False] * len(graph)
    dfs(graph, visited, 0)
    return all(visited)

其中，graph表示邻接矩阵，visited表示顶点的访问状态，u表示当前遍历到的顶点。

3. 求最小生成树

在使用Prim或Kruskal算法求无向网的最小生成树时，需要维护一个已访问的集合和一个未访问的集合，以及一个记录最小生成树的列表。可以使用以下函数实现：

def prim(graph: List[List[int]]) -> List[Tuple[int, int]]:
    n = len(graph)
    visited = [False] * n
    dist = [float('inf')] * n
    parent = [-1] * n
    dist[0] = 0
    for _ in range(n):
        u = min((dist[i], i) for i in range(n) if not visited[i])[1]
        visited[u] = True
        for v in range(n):
            if graph[u][v] != float('inf') and not visited[v] and graph[u][v] < dist[v]:
                dist[v] = graph[u][v]
                parent[v] = u
    return [(parent[i], i) for i in range(1, n)]


def kruskal(graph: List[Tuple[int, int, int]]) -> List[Tuple[int, int]]:
    n = len(set([u for u, v, w in graph] + [v for u, v, w in graph]))
    graph.sort(key=lambda x: x[2])
    parent = list(range(n))
    rank = [0] * n
    mst = []
    for u, v, w in graph:
        pu, pv = find(parent, u), find(parent, v)
        if pu != pv:
            mst.append((u, v))
            union(parent, rank, pu, pv)
    return mst


def find(parent: List[int], i: int) -> int:
    if parent[i] != i:
        parent[i] = find(parent, parent[i])
    return parent[i]


def union(parent: List[int], rank: List[int], x: int, y: int):
    if rank[x] > rank[y]:
        parent[y] = x
    elif rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[x] = y
        rank[y] += 1

其中，graph表示边的列表。

4. 求最短路径

在使用Dijkstra或Bellman-Ford算法求源点到其他顶点的最短路径时，需要维护一个最短路径的列表和一个已访问的集合。可以使用以下函数实现：

def dijkstra(graph: List[List[int]], src: int) -> List[int]:
    n = len(graph)
    dist = [float('inf')] * n
    visited = [False] * n
    dist[src] = 0
    for _ in range(n):
        u = min((dist[i], i) for i in range(n) if not visited[i])[1]
        visited[u] = True
        for v in range(n):
            if graph[u][v] != float('inf') and not visited[v] and dist[u] + graph[u][v] < dist[v]:
                dist[v] = dist[u] + graph[u][v]
    return dist


def bellman_ford(graph: List[Tuple[int, int, int]], src: int) -> List[int]:
    n = len(set([u for u, v, w in graph] + [v for u, v, w in graph]))
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in graph:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

其中，graph表示邻接矩阵，src表示源点。