算法学习笔记 —— 图

本文最后更新于：2023年12月5日下午

学而时习，本文记录图相关算法练习笔记。

133. 克隆图

给你无向连通图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return None

        q = [node]
        res_set = set()
        max_node_index = -1
        while q:
            temp_q = []
            for node in q:
                if node not in res_set:
                    res_set.add(node)
                    if node.val > max_node_index:
                        max_node_index = node.val
                    for neighbor in node.neighbors:
                        temp_q.append(neighbor)
            q = temp_q

        node_list = [Node(index) for index in range(1, max_node_index + 1)]

        for node in res_set:

            copy_node = node_list[node.val - 1]

            for neighbor in node.neighbors:
                copy_node.neighbors.append(node_list[neighbor.val - 1])
        return node_list[0]

433. 最小基因变化

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        def check_valid(data1, data2):
            if len(data1) != len(data2):
                return False
            num = 0
            for index in range(len(data1)):
                if data1[index] != data2[index]:
                    num += 1
            if num == 1:
                return True
            else:
                return False
        
        visited = set()
        visited.add(startGene)
        q = [startGene]
        step = 0
        while q:
            temp_q = []
            step += 1
            for str_data in q:
                for data in bank:
                    if data not in visited:
                        if check_valid(str_data, data):
                            temp_q.append(data)
                            visited.add(data)
                            if data == endGene:
                                return step
            q = temp_q
        return -1