الگوریتم کروسکال به صورت مرحله به مرحله عمل می‌کند و در هر مرحله، یالی که کمترین وزن را دارد و دو رأس متفاوت را به هم متصل می‌کند را به درخت پوشا اضافه می‌کند. این کار را تا زمانی ادامه می‌دهد که همه رئوس درخت پوشا به یکدیگر متصل شوند یا تا زمانی که دیگر یالی برای اضافه کردن وجود نداشته باشد.
الگوریتم کروسکال معمولا با استفاده از ساختار داده‌ای به نام "ترتیب اتحادیه" (Union-Find) برای ردیابی و ادغام مجموعه‌های مختلف رئوس استفاده می‌کند. این ساختار داده به الگوریتم امکان می‌دهد که به سرعت بررسی کند که آیا افزودن یالی که دو رأس را به هم متصل می‌کند، باعث ایجاد دور می‌شود یا خیر. با استفاده از الگوریتم کروسکال، می‌توان درخت پوشای کمینه را در یک گراف وزن‌دار پیدا کرد. این الگوریتم در مسائلی مانند شبکه‌سازی، طراحی شبکه‌ها و بهینه‌سازی مسیریابی مورد استفاده قرار می‌گیرد.
پیاده سازی الگوریتم کروسکال
الگوریتم کروسکال را می‌توان با استفاده از زبان‌های برنامه‌نویسی مختلف پیاده‌سازی کرد. در زیر، یک نمونه پیاده‌سازی الگوریتم کروسکال در زبان پایتون آورده شده است:
class UnionFind:
def __init__(self, vertices):
self.parent = {}
self.rank = {}
for v in vertices:
self.parent[v] = v
self.rank[v] = 0
def find(self, v):
if self.parent[v] != v:
self.parent[v] = self.find(self.parent[v])
return self.parent[v]
def union(self, v1, v2):
root1 = self.find(v1)
root2 = self.find(v2)
if root1 != root2:
if self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
elif self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
else:
self.parent[root2] = root1
self.rank[root1] += 1
def kruskal(graph):
minimum_spanning_tree = []
edges = []
for u in graph:
for v, weight in graph[u]:
edges.append((u, v, weight))
edges.sort(key=lambda x: x[2])
vertices = set()
for edge in edges:
u, v, weight = edge
vertices.add(u)
vertices.add(v)
uf = UnionFind(vertices)
for edge in edges:
u, v, weight = edge
if uf.find(u) != uf.find(v):
uf.union(u, v)
minimum_spanning_tree.append(edge)
return minimum_spanning_tree
در این پیاده‌سازی، ابتدا یک کلاس به نام UnionFind تعریف شده است که از ساختار داده ترتیب اتحادیه برای ردیابی و ادغام مجموعه‌های مختلف استفاده می‌کند. سپس، تابع kruskal تعریف شده است که الگوریتم کروسکال را پیاده‌سازی می‌کند. این تابع یک گراف ورودی دریافت می‌کند و درخت پوشای کمینه را بازمی‌گرداند. برای استفاده از این پیاده‌سازی، می‌توانید گراف وزن‌دار خود را تعریف کنید و به عنوان ورودی به تابع kruskal بدهید. سپس، درخت پوشای کمینه به عنوان خروجی دریافت خواهد شد. مقادیر و گراف ورودی باید به صورت مناسب تعریف شوند تا پیاده‌سازی صحیح عمل کند.
مراحل فرایند اجرای الگوریتم
مراحل اجرای الگوریتم کروسکال به صورت زیر است:
1. ساختار داده‌ها را آماده کنید:
- ایجاد یک مجموعه خالی برای ذخیره درخت پوشای کمینه (minimum_spanning_tree).
- ایجاد یک لیست خالی برای ذخیره یال‌های گراف (edges).
2. لیست یال‌های گراف را بسازید:
- برای هر راس u در گراف:
- برای هر یال (v, weight) که به u وصل است:
- اضافه کردن یال (u, v, weight) به لیست یال‌ها.
3. مرتب‌سازی لیست یال‌ها بر اساس وزن هر یال. (مرتب‌سازی صعودی)
4. ساختار داده ترتیب اتحادیه (Union-Find) را آماده کنید:
- برای هر راس در گراف، یک نود در ترتیب اتحادیه ایجاد کنید و به عنوان والد خود تنظیم کنید.
- برای هر نود در ترتیب اتحادیه، یک رتبه صفر تنظیم کنید.
5. بررسی یال‌ها به ترتیب از کمترین وزن تا بیشترین وزن:
- برای هر یال (u, v, weight) در لیست یال‌ها:
- اگر ترتیب اتحادیه از u و v متفاوت است (یعنی اضافه کردن این یال به درخت پوشای کمینه دور ایجاد نمی‌کند):
- یال (u, v, weight) را به درخت پوشای کمینه اضافه کنید.
- ترتیب اتحادیه u و v را به‌روز کنید (یعنی آنها را به یکدیگر متصل کنید).
6. درخت پوشای کمینه را به عنوان خروجی بازگردانید.
در این مراحل، الگوریتم کروسکال یال‌های گراف را به ترتیب از کمترین وزن تا بیشترین وزن بررسی می‌کند و این یال‌ها را به درخت پوشای کمینه اضافه می‌کند. ساختار داده ترتیب اتحادیه برای اجرای بهینه‌تر عملیات اضافه کردن یال و بررسی وجود دور استفاده می‌شود. به این ترتیب، در نهایت درخت پوشای کمینه با حداقل وزن را بدست می‌آورید.
مثالی از الگوریتم کروسکال
به عنوان یک مثال، فرض کنید گراف زیر را داریم:
A---2---B
/ \ /
1 3 4
/ \ /
C---5---D
حال می‌خواهیم الگوریتم کروسکال را روی این گراف اجرا کنیم تا درخت پوشای کمینه را بدست آوریم. مراحل را به ترتیب اجرا می‌کنیم:
1. ساختار داده‌ها را آماده می‌کنیم:
minimum_spanning_tree = []
edges = []
2. لیست یال‌های گراف را بسازیم:
- برای A: اضافه کردن (A, B, 2) به لیست یال‌ها
- برای A: اضافه کردن (A, C, 1) به لیست یال‌ها
- برای B: اضافه کردن (B, D, 4) به لیست یال‌ها
- برای C: اضافه کردن (C, D, 5) به لیست یال‌ها
- برای D: اضافه کردن (D, B, 3) به لیست یال‌ها
لیست یال‌ها: [(A, B, 2), (A, C, 1), (B, D, 4), (C, D, 5), (D, B, 3)]
3. مرتب‌سازی لیست یال‌ها بر اساس وزن هر یال:
- لیست یال‌ها: [(A, C, 1), (A, B, 2), (D, B, 3), (B, D, 4), (C, D, 5)]
4. ساختار داده ترتیب اتحادیه را آماده می‌کنیم:
راس A: پدر = A، رتبه = 0
راس B: پدر = B، رتبه = 0
راس C: پدر = C، رتبه = 0
راس D: پدر = D، رتبه = 0
5. بررسی یال‌ها به ترتیب از کمترین وزن تا بیشترین وزن:
- (A, C, 1): ترتیب اتحادیه A و C متفاوت است، پس یال را به درخت پوشای کمینه اضافه می‌کنیم و ترتیب اتحادیه را به‌روز می‌کنیم.
- (A, B, 2): ترتیب اتحادیه A و B متفاوت است، پس یال را به درخت پوشای کمینه اضافه می‌کنیم و ترتیب اتحادیه را به‌روز می‌کنیم.
- (D, B, 3): ترتیب اتحادیه D و B متفاوت است، پس یال را به درخت پوشای کمینه اضافه می‌کنیم و ترتیب اتحادیه را به‌روز می‌کنیم.
- (B, D, 4): ترتیب اتحادیه B و D یکسان است، پس اضافه کردن این یال به درخت پوشای کمینه دور ایجاد می‌کند. اکنون درخت پوشای کمینه به صورت زیر است:
A---2---B
/
1
/
C
6. باقی مانده است. (C, D, 5): ترتیب اتحادیه C و D متفاوت است، پس یال را به درخت پوشای کمینه اضافه می‌کنیم و ترتیب اتحادیه را به‌روز می‌کنیم. در نهایت، درخت پوشای کمینه به صورت زیر خواهد بود:
A---2---B
/ \
1 4
/ \
C---5---D
در این مثال، الگوریتم کروسکال یال‌های گراف را بررسی می‌کند و یال‌هایی که در ایجاد دور در درخت پوشای کمینه نقش دارند را نادیده می‌گیرد. در نهایت، درخت پوشای کمینه با حداقل وزن را بدست می‌آوریم.
مثال های کدنویسی شده الگوریتم کروسکال
الگوریتم کروسکال برای یافتن درخت پوشای کمینه یک گراف، می‌تواند با استفاده از ساختار داده‌هایی مانند ترتیب اتحادیه (Union-Find) پیاده‌سازی شود. در زیر، مثالی از کد نویسی الگوریتم کروسکال با استفاده از زبان برنامه‌نویسی پایتون قرار داده شده است:
# کلاس برای نمایش یک یال در گراف
class Edge:
def __init__(self, src, dest, weight):
self.src = src
self.dest = dest
self.weight = weight
# کلاس برای نمایش یک گراف کامل
class Graph:
def __init__(self, vertices):
self.V = vertices
self.edges = []
def add_edge(self, src, dest, weight):
edge = Edge(src, dest, weight)
self.edges.append(edge)
# کلاس برای نمایش یک مجموعه از ترتیب اتحادیه
class UnionFind:
def __init__(self, vertices):
self.parent = {}
self.rank = {}
for v in vertices:
self.parent[v] = v
self.rank[v] = 0
def find(self, v):
if self.parent[v] != v:
self.parent[v] = self.find(self.parent[v])
return self.parent[v]
def union(self, v1, v2):
root1 = self.find(v1)
root2 = self.find(v2)
if self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
elif self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
else:
self.parent[root2] = root1
self.rank[root1] += 1
# الگوریتم کروسکال برای یافتن درخت پوشای کمینه
def kruskal_algorithm(graph):
minimum_spanning_tree = []
graph.edges = sorted(graph.edges, key=lambda edge: edge.weight)
# مرتب‌سازی یال‌ها بر اساس وزن
union_find = UnionFind(list(range(graph.V)))
# ایجاد یک ترتیب اتحادیه برای راس‌ها
for edge in graph.edges:
src_root = union_find.find(edge.src)
dest_root = union_find.find(edge.dest)
if src_root != dest_root:
# اگر ترتیب اتحادیه دو راس متفاوت باشد
minimum_spanning_tree.append(edge)
# یال را به درخت پوشای کمینه اضافه کن
union_find.union(src_root, dest_root)
# اتحاد دو راس را انجام بده
return minimum_spanning_tree
# مثال استفاده از الگوریتم کروسکال
g = Graph(4)
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 1)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 4)
g.add_edge(2, 3, 5)
minimum_spanning_tree = kruskal_algorithm(g)
# نمایش درخت پوشای کمینه
for edge in minimum_spanning_tree:
print(f"{edge.src} -- {edge.dest} : {edge.weight}")
این کد پایتون شامل سه کلاس Edge، Graph و UnionFind است. کلاس Edge برای نمایش هر یال در گراف استفاده می‌شود، کلاس Graph برای نمایش یک گراف کامل به همراه توابعی برای افزودن یال به گراف و کلاس UnionFind برای نمایش یک مجموعه از ترتیب اتحادیه استفاده می‌شود. سپس، الگوریتم کروسکال با تابع kruskal_algorithm پیاده‌سازی شده است. این الگوریتم با استفاده از ترتیب اتحادیه و مرتب‌سازی یال‌ها بر اساس وزن، درخت پوشای کمینه را محاسبه می‌کند. در نهایت، درخت پوشای کمینه نمایش داده می‌شود. برای استفاده از الگوریتم کروسکال، یک نمونه از کلاس Graph ایجاد شده و یال‌ها با استفاده از تابع add_edge به آن اضافه می‌شوند. سپس تابع kruskal_algorithm فراخوانی شده و درخت پوشای کمینه نمایش داده می‌شود. در مثال فوق، یال‌ها و وزن‌های آنها به صورت سخت‌گیرانه تعریف شده است. شما می‌توانید ورودی خود را بر اساس نیاز تعریف کنید و الگوریتم را اجرا کنید.
کاربردهای الگوریتم کروسکال
الگوریتم کروسکال یک الگوریتم مهم در حوزه گراف است و برای یافتن درخت پوشای کمینه یک گراف بکار می‌رود. این الگوریتم در بسیاری از مسائل و کاربردها مورد استفاده قرار می‌گیرد. در زیر، به برخی از کاربردهای الگوریتم کروسکال اشاره می‌کنم:
- شبکه‌های کابلی: الگوریتم کروسکال می‌تواند در برنامه‌ریزی و طراحی شبکه‌های کابلی مورد استفاده قرار گیرد. با استفاده از الگوریتم کروسکال، می‌توان درخت پوشای کمینه‌ای را برای اتصال کابل‌ها بین نقاط مختلف در یک شبکه برقرار کرد. این درخت پوشا بهینه‌ترین مسیرها را برای انتقال اطلاعات فراهم می‌کند و هزینه کابل‌کشی را به حداقل می‌رساند.
- شبکه‌های ارتباطی: در طراحی شبکه‌های ارتباطی، الگوریتم کروسکال برای انتخاب اتصالات بهینه بین مراکز و تجهیزات استفاده می‌شود. با استفاده از الگوریتم کروسکال، می‌توانیم درخت پوشای کمینه‌ای را برای ارتباط بین مراکز و تجهیزات در شبکه بسازیم که هزینه ارتباط را به حداقل می‌رساند و عملکرد شبکه را بهبود می‌بخشد.
- ترافیک و حمل و نقل: در برنامه‌ریزی و بهینه‌سازی حمل و نقل و مسائل مربوط به ترافیک، الگوریتم کروسکال می‌تواند مورد استفاده قرار گیرد. با استفاده از الگوریتم کروسکال، می‌توانیم درخت پوشای کمینه‌ای را برای اتصال جاده‌ها، مسیرهای حمل و نقل یا شبکه‌های ترافیکی بسازیم که هزینه و زمان مسافرت را به حداقل می‌رساند و ترافیک را بهبود می‌بخشد.
- شبکه‌های اجتماعی: الگوریتم کروسکال می‌تواند در تحلیل و بررسی شبکه‌های اجتماعی به کار رود. با استفاده از این الگوریتم، می‌توان مجموعه‌ای از روابط مهم و ارتباطات قوی بین افراد را در شبکه‌های اجتماعی شناسایی کرد.
- پردازش تصویر: الگوریتم کروسکال می‌تواند در برخی مسائل پردازش تصویر نیز مورد استفاده قرار گیرد. به عنوان مثال، می‌توان از این الگوریتم برای تشخیص و اتصال اجزای مختلف یک تصویر (مانند ردیابی اشیا، تصویرسازی سه‌بعدی و ...) استفاده کرد.
- برنامه‌ریزی زمان بندی: در برنامه‌ریزی زمان بندی و برنامه‌ریزی پروژه، الگوریتم کروسکال می‌تواند در تعیین ترتیب و اولویت انجام فعالیت‌ها و وظایف مورد استفاده قرار بگیرد.
- مسائل بهینه‌سازی: الگوریتم کروسکال در حل مسائل بهینه‌سازی مورد استفاده قرار می‌گیرد. با استفاده از این الگوریتم، می‌توانیم به صورت کلی و بهینه مسئله‌هایی را حل کنیم که با مفهوم گراف مرتبط هستند.
- حل مسائل کمینه‌سازی: الگوریتم کروسکال می‌تواند در حل مسائل کمینه‌سازی مورد استفاده قرار گیرد. به عنوان مثال، می‌توان از این الگوریتم برای یافتن کمترین مسیر بین دو نقطه در یک شبکه استفاده کرد.
موارد یاد شده، تنها چند مثال از کاربردهای الگوریتم کروسکال هستند و در عمل می‌توان از این الگوریتم در بسیاری از مسائل دیگر نیز استفاده کرد.
ماهنامه شبکه را از کجا تهیه کنیم؟
ماهنامه شبکه را می‌توانید از کتابخانه‌های عمومی سراسر کشور و نیز از دکه‌های روزنامه‌فروشی تهیه نمائید.
ثبت اشتراک نسخه کاغذی ماهنامه شبکه
ثبت اشتراک نسخه آنلاین
کتاب الکترونیک +Network راهنمای شبکه‌ها
- برای دانلود تنها کتاب کامل ترجمه فارسی +Network اینجا کلیک کنید.
کتاب الکترونیک دوره مقدماتی آموزش پایتون
- اگر قصد یادگیری برنامه‌نویسی را دارید ولی هیچ پیش‌زمینه‌ای ندارید اینجا کلیک کنید.
نظر شما چیست؟