算法 leetCode 岛屿问题
''' 岛屿数量 问题描述 给定一个有’1‘（陆地）和’0‘组成的二维网格 计算到预计的数量。 一个岛被水包围而成，并且它是通过水平方向相邻的陆地链接而成的 输入： 11110 11010 11000 00000 输出：1 输入 11000 11000 00100 00011 输出 3 ''' # 算法一 深度搜索 lands = 0 def dfs(lst, r, c): nr = len(lst) nc = len(lst[0]) lst[r][c] = 0 if r-1 >= 0 and lst[r-1][c]==1: dfs(lst, r-1,c) if r+1 < nr and lst[r+1][c]==1: dfs(lst, r+1,c) if c-1 >= 0 and lst[r][c-1]==1: dfs(lst, r,c-1) if c+1 < nc and lst[r][c+1]==1: dfs(lst, r,c+1) lst = [[1,1,1,1,0],[1,1,1,1,0],[1,1,0,0,0],[0,0,1,0,1,]] nr = len(lst) nc = len(lst[0]) num_islands = 0 for r in range(nr): for c in range(nc): if lst[r][c] == 1: num_islands +=1 dfs(lst, r, c) print(num_islands) # 算法二 广度优先搜索 lst = [[1,1,1,1,0],[1,1,1,1,0],[1,1,0,0,0],[0,0,1,0,1,]] nr = len(lst) nc = len(lst[0]) num_islands = 0 for r in range(nr): for c in range(nc): if lst[r][c] == 1: num_islands +=1 lst[r][c] = 0 from collections import deque from django.db.migrations import graph 2 def search(name):#广度优先搜索(BFS) # deque()函数创建一个双端队列（先进先出） # 注意deque是python标准库cillections中的一个模块 search_quene = deque() search_quene += graph[name] # 创建空列表的目的：为了防止后边添加到队列里的元素与之前的重复出现 # 所以我加入一个空列表，将判断完成的数据添加的这个列表，将准备进入列表的数据与这个列表元素对比，确保没有重复元素再次进入队列，防止无限循环产生 searched = [] while search_quene: # 队列中，pop()默认抛出右边元素，但是我们希望，append()从右边入队，popleft()从左边出队 person = search_quene.popleft() if person not in searched: #person_is_not()是一个判断函数，我们需要判断我们查找的内容是否满足我们的需求 if person_is_not(person): print (person+" is this") return True else: search_quene += graph[person] searched.append(person) return False
def myDijkstra(statr:int , lst:list): """ :param statr: 开始的地点 :param lst: 各个城市之间的距离， 二维数组，就是用行列坐标表示图形上两点之间的距离。 :return: 到各个城市的最短距离 """ # city 未被当作中间节点的城市列表 city = [x for x in range(len(lst)) if x != statr] # 城市顺序 cityorder = [statr] citylength = lst[statr] # len1 是一一维列表，里面包含着 成市 n 到各个城市的初始距离 # 用循环判断，城市n 到其他城市中最短的距离 while len(city): idenx1 =city[0] for i in city: if citylength[i] < citylength[idenx1]: idenx1 = i # 将做过中间节点的移出city city.remove(idenx1) # 添加到城市最近列表 cityorder.append(idenx1) # 更新成市 n 到各个城市之间的最短距离 for i in city: # 当新的路线距离更进时，会更新 个城市直接的距离 if citylength[idenx1]+lst[idenx1][i] < citylength[i]: citylength[i] = citylength[idenx1]+lst[idenx1][i] return citylength if __name__ == '__main__': max = 999999 # max即表示为无法直达 graph = [ [5, max, 10, max, 30, 100], [max, max, 5, max, max, max], [max, 15, max, 50, max, max], [max, max, max, max, max, 10], [max, max, max, 20, max, 60], [max, 15, max, max, max, max], ] inf = 999999 mgraph = [[0, 1, 12, inf, inf, inf], [inf, 0, 9, 3, inf, inf], [inf, inf, 0, inf, 5, inf], [inf, inf, 4, 0, 13, 15], [inf, inf, inf, inf, 0, 4], [inf, inf, inf, inf, inf, 0]] len1 = myDijkstra(0,graph) print(len1) len2 = myDijkstra(0, mgraph) print(len2) def startwith(start: int, mgraph: list) -> list: passed = [start] # 初始化数组，一共有多少个城市 并为城市编号 nopass = [x for x in range(len(mgraph)) if x != start] print('nopass',nopass) # 到直接各个点之间的最短距离，不能直接到达的距离就是 10086 dis = mgraph[start] print(dis) # 执行循环，找出初始位置到各个点的最短路径 while len(nopass): idx = nopass[0] for i in nopass: if dis[i] < dis[idx]: idx = i nopass.remove(idx) # 还有那个的点未被访问 print("111111",nopass) passed.append(idx) # 最短路径的走法 print("22222",passed) for i in nopass: if dis[idx] + mgraph[idx][i] < dis[i]: dis[i] = dis[idx] + mgraph[idx][i] return dis def dijkstra(graph, start_Node, path, cost, max): """ graph：二维数组，就是用行列坐标表示图形上两点之间的距离。 start_Node：起始点 path[i] 表示vi节点的前一个节点，即中转点。 cost[i] 表示V0到Vi的已知最短路径长度 mid_Node:中转点，以已求得V0到Vi的最短路径的Vi作为中转点。 NEXT_Node:尝试优化的点，以中转点为中心，检测NEXT_Node直达V0方案，和经过mid_Node中转到V0的方案哪个更优 check_Node:索引，搜索cost数组里最短路径的点，最短的点会赋值给mid_Node,作为中转点。 """ lenth = len(graph) v = [0] * lenth # V数组初始化为0，用于标记该点是否已取得最短路径 # 初始化 path，cost，V for i in range(lenth): if i == start_Node: v[start_Node] = 1 else: cost[i] = graph[start_Node][i] # cost获取起点至其他点的直达权重 path[i] = (start_Node if (cost[i] < max) else -1) # 前置点为起点或-1（无法直达起点） # print v, cost, path for i in range(1, lenth): # 遍历的数等于除去起点的点的数量 minCost = max # 初始值取最大 mid_Node = -1 for check_Node in range(lenth): # 搜索一个到起点V0最近的点，作为中转点mid_Node if v[check_Node] == 0 and cost[check_Node] < minCost: # mid_Node点未取得最短路径，且路径权重小于最小值，则获取w，也就是先取得 minCost = cost[check_Node] mid_Node = check_Node if mid_Node == -1: break # 找不到权重小于max的点 # 剩下都是不可通行的节点，跳出循环 v[mid_Node] = 1 # check_Node已取得最短路径 for NEXT_Node in range(lenth): if v[NEXT_Node] == 0 and (graph[mid_Node][NEXT_Node] + cost[mid_Node] < cost[ NEXT_Node]): # 检查所有未遍历的点NEXT_Node，检测前面获取的mid_Node对NEXT_Node的影响 cost[NEXT_Node] = graph[mid_Node][NEXT_Node] + cost[mid_Node] # 更新权值 path[NEXT_Node] = mid_Node # 更新路径 # for 更新其他节点的权值（距离）和路径 return path
