پیمایش گراف (BFS و DFS)

برنامه نویسی

پیمایش گراف یکی از مفاهیم اساسی در علوم کامپیوتر است که در بسیاری از الگوریتم‌ها و برنامه‌های کاربردی استفاده می‌شود. در این مقاله، ابتدا به کاربردهای پیمایش گراف می‌پردازیم، سپس پیمایش اول سطح (BFS) و پیمایش اول عمق (DFS) را به‌طور کامل توضیح داده و پیاده‌سازی آن‌ها را در زبان‌های پایتون، سی‌پلاس‌پلاس و جاوا ارائه می‌کنیم. در پایان، این دو روش را با هم مقایسه کرده و شرایط مناسب برای استفاده از هر کدام را بررسی می‌کنیم.

کاربردهای پیمایش گراف

پیمایش گراف در بسیاری از مسائل و پروژه‌های واقعی کاربرد دارد. برخی از این کاربردها عبارتند از:

  1. پیدا کردن کوتاه‌ترین مسیر: در شبکه‌های کامپیوتری، سیستم‌های ناوبری و مسیریابی.

  2. جستجو در شبکه‌های اجتماعی: پیدا کردن دوستان مشترک یا ارتباط بین افراد.

  3. تحلیل شبکه‌های ارتباطی: بررسی ارتباط بین گره‌ها در شبکه‌های کامپیوتری یا اجتماعی.

  4. تشخیص چرخه در گراف: بررسی وجود چرخه در گراف‌های جهت‌دار یا بدون جهت.

  5. مسائل بهینه‌سازی: مانند مسئله فروشنده دوره‌گرد (TSP) یا رنگ‌آمیزی گراف.

  6. هوش مصنوعی و یادگیری ماشین: در الگوریتم‌های جستجو و تصمیم‌گیری.

پیمایش اول سطح (BFS - Breadth-First Search)

پیمایش اول سطح (BFS) یک الگوریتم پیمایش گراف است که از یک گره شروع می‌شود و تمام گره‌های همسایه را قبل از رفتن به لایه‌های بعدی بررسی می‌کند. این الگوریتم از یک صف (Queue) برای مدیریت گره‌هایی که باید بررسی شوند استفاده می‌کند.

مراحل الگوریتم BFS:

  1. گره شروع را به صف اضافه کرده و آن را به عنوان بازدید شده علامت‌گذاری کنید.

  2. تا زمانی که صف خالی نشده است:

    • گره جلوی صف را خارج کنید.

    • تمام همسایه‌های بازدید نشده این گره را به صف اضافه کرده و آن‌ها را به عنوان بازدید شده علامت‌گذاری کنید.

  3. وقتی صف خالی شد، پیمایش کامل می‌شود.

پیاده سازی در Python

				
					from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=" ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# مثال استفاده
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')  # خروجی: A B C D E F

پیاده سازی در ++C

				
					#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

void bfs(unordered_map<char, vector<char>>& graph, char start) {
    unordered_set<char> visited;
    queue<char> q;
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        char node = q.front();
        q.pop();
        cout << node << " ";

        for (char neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

int main() {
    unordered_map<char, vector<char>> graph = {
        {'A', {'B', 'C'}},
        {'B', {'A', 'D', 'E'}},
        {'C', {'A', 'F'}},
        {'D', {'B'}},
        {'E', {'B', 'F'}},
        {'F', {'C', 'E'}}
    };

    bfs(graph, 'A');  // خروجی: A B C D E F
    return 0;
}

پیاده سازی در Java

				
					import java.util.*;

public class BFS {
    public static void bfs(Map<Character, List<Character>> graph, char start) {
        Set<Character> visited = new HashSet<>();
        Queue<Character> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            char node = queue.poll();
            System.out.print(node + " ");

            for (char neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Map<Character, List<Character>> graph = new HashMap<>();
        graph.put('A', Arrays.asList('B', 'C'));
        graph.put('B', Arrays.asList('A', 'D', 'E'));
        graph.put('C', Arrays.asList('A', 'F'));
        graph.put('D', Arrays.asList('B'));
        graph.put('E', Arrays.asList('B', 'F'));
        graph.put('F', Arrays.asList('C', 'E'));

        bfs(graph, 'A');  // خروجی: A B C D E F
    }
}

پیمایش اول عمق (DFS - Depth-First Search)

پیمایش اول عمق (DFS) یک الگوریتم پیمایش گراف است که از یک گره شروع می‌شود و تا جایی که ممکن است به عمق گراف پیش می‌رود، سپس به عقب برمی‌گردد و مسیرهای دیگر را بررسی می‌کند. این الگوریتم از بازگشت (Recursion) یا پشته (Stack) استفاده می‌کند.

 

مراحل الگوریتم DFS:

 

  1. گره شروع را به عنوان بازدید شده علامت‌گذاری کنید.

  2. برای هر همسایه بازدید نشده این گره:

    • همسایه را به عنوان بازدید شده علامت‌گذاری کنید.

    • به‌طور بازگشتی الگوریتم DFS را روی آن همسایه اجرا کنید.

پیاده سازی در Python

				
					def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# مثال استفاده
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')  # خروجی: A B D E F C

پیاده سازی در ++C

				
					#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

void dfs(unordered_map<char, vector<char>>& graph, char start, unordered_set<char>& visited) {
    visited.insert(start);
    cout << start << " ";

    for (char neighbor : graph[start]) {
        if (visited.find(neighbor) == visited.end()) {
            dfs(graph, neighbor, visited);
        }
    }
}

int main() {
    unordered_map<char, vector<char>> graph = {
        {'A', {'B', 'C'}},
        {'B', {'A', 'D', 'E'}},
        {'C', {'A', 'F'}},
        {'D', {'B'}},
        {'E', {'B', 'F'}},
        {'F', {'C', 'E'}}
    };

    unordered_set<char> visited;
    dfs(graph, 'A', visited);  // خروجی: A B D E F C
    return 0;
}

پیاده سازی در Java

				
					import java.util.*;

public class DFS {
    public static void dfs(Map<Character, List<Character>> graph, char start, Set<Character> visited) {
        visited.add(start);
        System.out.print(start + " ");

        for (char neighbor : graph.get(start)) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        Map<Character, List<Character>> graph = new HashMap<>();
        graph.put('A', Arrays.asList('B', 'C'));
        graph.put('B', Arrays.asList('A', 'D', 'E'));
        graph.put('C', Arrays.asList('A', 'F'));
        graph.put('D', Arrays.asList('B'));
        graph.put('E', Arrays.asList('B', 'F'));
        graph.put('F', Arrays.asList('C', 'E'));

        Set<Character> visited = new HashSet<>();
        dfs(graph, 'A', visited);  // خروجی: A B D E F C
    }
}

مقایسه BFS و DFS

 

ویژگیBFSDFS
ساختار دادهصف (Queue)پشته (Stack) یا بازگشت
کاربردهاپیدا کردن کوتاه‌ترین مسیرپیدا کردن مسیرهای عمیق
پیچیدگی زمانیO(V+E)O(V+E)
پیچیدگی فضاییO(V) (در بدترین حالت)O(V) (در بدترین حالت)
پایداریبلهخیر
مناسب برایگراف‌های با عرض کمگراف‌های با عمق کم

 

نتیجه‌گیری

  • BFS برای پیدا کردن کوتاه‌ترین مسیر در گراف‌های بدون وزن مناسب است و در گراف‌هایی که عرض کمی دارند بهتر عمل می‌کند.

  • DFS برای بررسی مسیرهای عمیق در گراف و حل مسائلی مانند تشخیص چرخه یا رنگ‌آمیزی گراف مناسب است.

انتخاب بین BFS و DFS به نیازهای مسئله و ساختار گراف بستگی دارد. اگر هدف پیدا کردن کوتاه‌ترین مسیر باشد، BFS گزینه بهتری است، اما اگر هدف بررسی تمام مسیرهای ممکن باشد، DFS مناسب‌تر است.

برچسب ها:

دیدگاهتان را بنویسید