Python實現(xiàn)經(jīng)典算法拓?fù)渑判?、字符串匹配算法和最小生成樹實?/h1>
更新時間：2023年08月03日 08:32:38 作者：老王學(xué)長
這篇文章主要介紹了Python實現(xiàn)經(jīng)典算法拓?fù)渑判?、字符串匹配算法和最小生成樹實?拓?fù)渑判?、字符串匹配算法和最小生成樹是計算機科學(xué)中常用的數(shù)據(jù)結(jié)構(gòu)和算法，它們在解決各種實際問題中具有重要的應(yīng)用價值,需要的朋友可以參考下
一、拓?fù)渑判?/h2>
拓?fù)渑判蚴且环N對有向無環(huán)圖（DAG）進(jìn)行排序的算法。它可以解決依賴關(guān)系的排序問題，常用于構(gòu)建任務(wù)調(diào)度、編譯器優(yōu)化等領(lǐng)域。
拓?fù)渑判蛩惴ǖ幕舅枷胧峭ㄟ^不斷刪除入度為0的節(jié)點，并更新相關(guān)節(jié)點的入度，直到所有節(jié)點都被訪問。
示例問題：課程安排問題 給定一些課程和它們的先修課程關(guān)系，要求安排課程的學(xué)習(xí)順序，使得先修課程在后修課程之前學(xué)習(xí)。
示例代碼：
from collections import defaultdict, deque
def topological_sort(num_courses, prerequisites):
# 構(gòu)建鄰接表和入度數(shù)組
graph = defaultdict(list)
indegree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
# 使用隊列進(jìn)行拓?fù)渑判?
queue = deque()
for course in range(num_courses):
if indegree[course] == 0:
queue.append(course)
result = []
while queue:
course = queue.popleft()
result.append(course)
for neighbor in graph[course]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
if len(result) != num_courses:
return []
return result
# 示例用法
num_courses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
result = topological_sort(num_courses, prerequisites)
print("課程學(xué)習(xí)順序:", result)
二、字符串匹配算法
字符串匹配算法用于在文本串中查找給定模式串的出現(xiàn)位置。常見的字符串匹配算法包括暴力匹配算法、KMP算法、Boyer-Moore算法等。這些算法根據(jù)不同的思想和技巧，實現(xiàn)了高效的字符串匹配過程。
示例問題：在文本串中查找模式串 給定一個文本串和一個模式串，要求在文本串中查找模式串的出現(xiàn)位置。
示例代碼：
def string_match(text, pattern):
m, n = len(text), len(pattern)
for i in range(m - n + 1):
j = 0
while j < n:
if text[i + j] != pattern[j]:
break
j += 1
if j
== n:
return i
return -1
# 示例用法
text = "Hello, World!"
pattern = "World"
result = string_match(text, pattern)
if result != -1:
print("模式串在文本串中的位置:", result)
else:
print("模式串不存在于文本串中")
三、最小生成樹
最小生成樹是一種在無向帶權(quán)圖中找到一棵包含所有頂點的生成樹，并且使得樹上所有邊的權(quán)值之和最小的算法。常用的最小生成樹算法包括Prim算法和Kruskal算法。
示例問題：電網(wǎng)規(guī)劃問題 給定一個城市的地理信息和建設(shè)電網(wǎng)的成本信息，要求設(shè)計一種電網(wǎng)規(guī)劃方案，使得連接城市的成本最小。
示例代碼：
from heapq import heapify, heappop, heappush
def minimum_spanning_tree(graph):
visited = set()
start_vertex = list(graph.keys())[0]
visited.add(start_vertex)
edges = [(cost, start_vertex, next_vertex) for next_vertex, cost in graph[start_vertex]]
heapify(edges)
while edges:
cost, u, v = heappop(edges)
if v not in visited:
visited.add(v)
for next_vertex, next_cost in graph[v]:
if next_vertex not in visited:
heappush(edges, (next_cost, v, next_vertex))
return visited
# 示例用法
graph = {
'A': [('B', 5), ('C', 1)],
'B': [('A', 5), ('C', 2), ('D', 1)],
'C': [('A', 1), ('B', 2), ('D', 4)],
'D': [('B', 1), ('C', 4)]
}
result = minimum_spanning_tree(graph)
print("最小生成樹的頂點集合:", result)
通過本文對拓?fù)渑判颉⒆址ヅ渌惴ê妥钚∩蓸涞脑敿?xì)介紹，以及相應(yīng)的示例代碼和應(yīng)用場景，相信讀者能夠更好地理解和掌握這些重要的數(shù)據(jù)結(jié)構(gòu)和算法。在實際的編程和問題解決中，根據(jù)具體的需求選擇合適的算法和數(shù)據(jù)結(jié)構(gòu)，將其靈活應(yīng)用，從而提高程序的效率和性能。希望本文對你的學(xué)習(xí)和實踐有所幫助！
到此這篇關(guān)于Python實現(xiàn)經(jīng)典算法拓?fù)渑判?、字符串匹配算法和最小生成樹實例的文章就介紹到這了,更多相關(guān)Python實現(xiàn)經(jīng)典算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
-
這篇文章主要介紹了Python類和方法注釋規(guī)范說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教 2022-06-06
-
弱引用在很多語言中都存在,最常用來解決循環(huán)引用問題,下面這篇文章主要給大家介紹了關(guān)于Python中弱引用的神奇用法與原理的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下 2022-04-04
-
這篇文章主要為大家詳細(xì)介紹了python使用KNN算法識別手寫數(shù)字，具有一定的參考價值，感興趣的小伙伴們可以參考一下 2019-04-04
-
詳解將Python程序(.py)轉(zhuǎn)換為Windows可執(zhí)行文件(.exe)
這篇文章主要介紹了詳解將Python程序(.py)轉(zhuǎn)換為Windows可執(zhí)行文件(.exe)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧 2019-07-07
-
這篇文章主要介紹了Python中生成器和yield語句的用法,生成器是Python編程進(jìn)階中的重要知識點,需要的朋友可以參考下 2015-04-04
-
python中l(wèi)eastsq函數(shù)的使用方法
這篇文章主要介紹了python中l(wèi)eastsq函數(shù)的使用方法，leastsq作用是最小化一組方程的平方和，下面文章舉例說明詳細(xì)內(nèi)容，具有一的參考價值，需要的小伙伴可以參考一下 2022-03-03
-
Python基于keras訓(xùn)練實現(xiàn)微笑識別的示例詳解
Keras是一個由Python編寫的開源人工神經(jīng)網(wǎng)絡(luò)庫，可用于深度學(xué)習(xí)模型的設(shè)計、調(diào)試、評估、應(yīng)用和可視化。本文將基于keras訓(xùn)練實現(xiàn)微笑識別效果，需要的可以參考一下 2022-01-01
-
在本篇文章中小編給大家整理了關(guān)于int在python中的含義以及用法，對此有興趣的朋友們可以跟著學(xué)習(xí)下。 2019-06-06
-
這篇文章主要為大家詳細(xì)介紹了python matlibplot繪制多條曲線圖，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下 2018-07-07
-
Python網(wǎng)頁正文轉(zhuǎn)換語音文件的操作方法
這篇文章主要介紹了Python網(wǎng)頁正文轉(zhuǎn)換語音文件的操作方法,需要的朋友可以參考下 2018-12-12
最新評論
一、拓?fù)渑判?/h2>
拓?fù)渑判蚴且环N對有向無環(huán)圖（DAG）進(jìn)行排序的算法。它可以解決依賴關(guān)系的排序問題，常用于構(gòu)建任務(wù)調(diào)度、編譯器優(yōu)化等領(lǐng)域。
拓?fù)渑判蛩惴ǖ幕舅枷胧峭ㄟ^不斷刪除入度為0的節(jié)點，并更新相關(guān)節(jié)點的入度，直到所有節(jié)點都被訪問。
示例問題：課程安排問題 給定一些課程和它們的先修課程關(guān)系，要求安排課程的學(xué)習(xí)順序，使得先修課程在后修課程之前學(xué)習(xí)。
示例代碼：
from collections import defaultdict, deque
def topological_sort(num_courses, prerequisites):
# 構(gòu)建鄰接表和入度數(shù)組
graph = defaultdict(list)
indegree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
# 使用隊列進(jìn)行拓?fù)渑判?
queue = deque()
for course in range(num_courses):
if indegree[course] == 0:
queue.append(course)
result = []
while queue:
course = queue.popleft()
result.append(course)
for neighbor in graph[course]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
if len(result) != num_courses:
return []
return result
# 示例用法
num_courses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
result = topological_sort(num_courses, prerequisites)
print("課程學(xué)習(xí)順序:", result)二、字符串匹配算法
字符串匹配算法用于在文本串中查找給定模式串的出現(xiàn)位置。常見的字符串匹配算法包括暴力匹配算法、KMP算法、Boyer-Moore算法等。這些算法根據(jù)不同的思想和技巧，實現(xiàn)了高效的字符串匹配過程。
示例問題：在文本串中查找模式串 給定一個文本串和一個模式串，要求在文本串中查找模式串的出現(xiàn)位置。
示例代碼：
def string_match(text, pattern):
m, n = len(text), len(pattern)
for i in range(m - n + 1):
j = 0
while j < n:
if text[i + j] != pattern[j]:
break
j += 1
if j
== n:
return i
return -1
# 示例用法
text = "Hello, World!"
pattern = "World"
result = string_match(text, pattern)
if result != -1:
print("模式串在文本串中的位置:", result)
else:
print("模式串不存在于文本串中")三、最小生成樹
最小生成樹是一種在無向帶權(quán)圖中找到一棵包含所有頂點的生成樹，并且使得樹上所有邊的權(quán)值之和最小的算法。常用的最小生成樹算法包括Prim算法和Kruskal算法。
示例問題：電網(wǎng)規(guī)劃問題 給定一個城市的地理信息和建設(shè)電網(wǎng)的成本信息，要求設(shè)計一種電網(wǎng)規(guī)劃方案，使得連接城市的成本最小。
示例代碼：
from heapq import heapify, heappop, heappush
def minimum_spanning_tree(graph):
visited = set()
start_vertex = list(graph.keys())[0]
visited.add(start_vertex)
edges = [(cost, start_vertex, next_vertex) for next_vertex, cost in graph[start_vertex]]
heapify(edges)
while edges:
cost, u, v = heappop(edges)
if v not in visited:
visited.add(v)
for next_vertex, next_cost in graph[v]:
if next_vertex not in visited:
heappush(edges, (next_cost, v, next_vertex))
return visited
# 示例用法
graph = {
'A': [('B', 5), ('C', 1)],
'B': [('A', 5), ('C', 2), ('D', 1)],
'C': [('A', 1), ('B', 2), ('D', 4)],
'D': [('B', 1), ('C', 4)]
}
result = minimum_spanning_tree(graph)
print("最小生成樹的頂點集合:", result)通過本文對拓?fù)渑判颉⒆址ヅ渌惴ê妥钚∩蓸涞脑敿?xì)介紹，以及相應(yīng)的示例代碼和應(yīng)用場景，相信讀者能夠更好地理解和掌握這些重要的數(shù)據(jù)結(jié)構(gòu)和算法。在實際的編程和問題解決中，根據(jù)具體的需求選擇合適的算法和數(shù)據(jù)結(jié)構(gòu)，將其靈活應(yīng)用，從而提高程序的效率和性能。希望本文對你的學(xué)習(xí)和實踐有所幫助！
到此這篇關(guān)于Python實現(xiàn)經(jīng)典算法拓?fù)渑判?、字符串匹配算法和最小生成樹實例的文章就介紹到這了,更多相關(guān)Python實現(xiàn)經(jīng)典算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
- 這篇文章主要介紹了Python類和方法注釋規(guī)范說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
- 弱引用在很多語言中都存在,最常用來解決循環(huán)引用問題,下面這篇文章主要給大家介紹了關(guān)于Python中弱引用的神奇用法與原理的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-04-04
- 這篇文章主要為大家詳細(xì)介紹了python使用KNN算法識別手寫數(shù)字，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-04-04
-
詳解將Python程序(.py)轉(zhuǎn)換為Windows可執(zhí)行文件(.exe)
這篇文章主要介紹了詳解將Python程序(.py)轉(zhuǎn)換為Windows可執(zhí)行文件(.exe)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-07-07 - 這篇文章主要介紹了Python中生成器和yield語句的用法,生成器是Python編程進(jìn)階中的重要知識點,需要的朋友可以參考下2015-04-04
-
python中l(wèi)eastsq函數(shù)的使用方法
這篇文章主要介紹了python中l(wèi)eastsq函數(shù)的使用方法，leastsq作用是最小化一組方程的平方和，下面文章舉例說明詳細(xì)內(nèi)容，具有一的參考價值，需要的小伙伴可以參考一下2022-03-03 -
Python基于keras訓(xùn)練實現(xiàn)微笑識別的示例詳解
Keras是一個由Python編寫的開源人工神經(jīng)網(wǎng)絡(luò)庫，可用于深度學(xué)習(xí)模型的設(shè)計、調(diào)試、評估、應(yīng)用和可視化。本文將基于keras訓(xùn)練實現(xiàn)微笑識別效果，需要的可以參考一下2022-01-01 - 在本篇文章中小編給大家整理了關(guān)于int在python中的含義以及用法，對此有興趣的朋友們可以跟著學(xué)習(xí)下。2019-06-06
- 這篇文章主要為大家詳細(xì)介紹了python matlibplot繪制多條曲線圖，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-07-07
-
Python網(wǎng)頁正文轉(zhuǎn)換語音文件的操作方法
這篇文章主要介紹了Python網(wǎng)頁正文轉(zhuǎn)換語音文件的操作方法,需要的朋友可以參考下2018-12-12