مولفه های قویا همبند در گراف و گراف قویا همبند

یک مولفه قویا همبند، بخشی از یک جهت‌دار است که در آن مسیری از هر راس به راس دیگر وجود دارد. مولفه قویا همبند فقط روی گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... جهت‌دار معنی دارد است.

برای مثال گراف زیر را در نظر بگیرید:

مولفه های قویا همبند گراف بالا به شکل زیر خواهند بود:

می‌توان مشاهده کرد که در هر مولفه قویا همبند، هر راس می‌تواند از طریق مسیری به راس‌های دیگر برسد. این مؤلفه‌ها را می‌توان با استفاده از الگوریتم کساراجو یافت.

حتما بخوانید :

معرفی کامل نظریه گراف (Graph Theory)

الگوریتم کساراجو

الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد کساراجو بر اساس الگوریتم جستجوی عمق اولالگوریتم جستجوی اول عمق ⚡️ آموزش الگوریتم dfs گرافدر این مقاله عالی الگوریتم جستجوی اول عمق بررسی و الگوریتم dfs گراف آموزش داده شده و مثال ها و پیاده سازی و کاربردهای الگوریتم جستجوی اول (DFS) عمق بیان شده است که دو بار اجرا شده است. این الگوریتم سه مرحله دارد:

مرحله اول

یک جستجوی عمقی در کل گراف انجام دهید. در واقع از راس 0 شروع می‌کنیم، تمام رئوس فرزند آن را مشاهده کرده و رئوس بازدید شده را به‌عنوان ویزیت شده علامت‌گذاری می‌کنیم. اگر یک راس به یک راس از قبل بازدید شده منتهی شود، آن راس را در پشتهساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان دادهاین مقاله عالی توضیح داده که پشته چیست و کاربرد پشته در ساختمان داده چیست، همچنین نحوه کارکرد پشته، پیاده سازی پشته و عملیات های پشته را معرفی کرده قرار می‌دهیم.

به‌عنوان‌مثال: با شروع از راس 0، به راس 1، راس 2 و سپس به راس 3 بروید. راس 3 به راس 0 که از قبل بازدید شده منتهی می‌شود، بنابراین راس مبدأ (یعنی راس 3) را در پشته قرار می‌دهیم.

به راس قبلی (راس 2) می‌رویم و رئوس فرزند آن یعنی راس 4، رأس 5، رأس 6 و رأس 7 را به ترتیب مشاهده می‌کنیم. ازآنجایی‌که از راس 7 جایی برای رفتن وجود ندارد، آن را در پشته قرار می‌دهیم.

به راس قبلی (راس 6) می‌رویم و رئوس فرزند آن را می‌بینیم. تمام رئوس فرزند آن بازدید می‌شود، بنابراین آن را درون پشته قرار می‌دهیم و به همین نحو کل پشتهساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان دادهاین مقاله عالی توضیح داده که پشته چیست و کاربرد پشته در ساختمان داده چیست، همچنین نحوه کارکرد پشته، پیاده سازی پشته و عملیات های پشته را معرفی کرده را می‌سازیم:

مرحله دوم

جهت‌ها را در گراف اصلی برعکس می‌کنیم:

مرحله سوم

در این مرحله، ابتدا یک جستجوی عمقی در گراف معکوس انجام می‌دهیم؛ در واقع از راس بالای پشته شروع می‌کنیم. از تمام رئوس فرزند آن عبور می‌کنیم. پس از رسیدن به راس بازدید شده از قبل، یک مولفه قوی تشکیل می‌شود.

به‌عنوان‌مثال: راس 0 را از پشته بردارید. با شروع از راس 0، از رئوس فرزند آن (راس 0، راس 1، راس 2، رأس 3 به ترتیب) عبور کنید و آنها را به‌عنوان بازدید شده علامت‌گذاری کنید. فرزند راس 3 قبلاً بازدید شده است، بنابراین این رئوس بازدید شده یک مولفه قویا همبند را تشکیل می‌دهند.

پیچیدگی زمانی الگوریتم کساراجو

الگوریتم کساراجو در زمان خطی یعنی O(V+E) اجرا می‌شود.

حتما بخوانید :

فیلم‌های آموزشی ریاضی گسسته

پیاده‌سازی الگوریتم کساراجو

Python

from collections import defaultdict

class Graph:
    def __init__(self, vertex):
        self.V = vertex
        self.graph = defaultdict(list)

    # Add edge into the graph
    def add_edge(self, s, d):
        self.graph[s].append(d)

    # dfs
    def dfs(self, d, visited_vertex):
        visited_vertex[d] = True
        print(d, end="")
        for i in self.graph[d]:
            if not visited_vertex[i]:
                self.dfs(i, visited_vertex)

    def fill_order(self, d, visited_vertex, stack):
        visited_vertex[d] = True
        for i in self.graph[d]:
            if not visited_vertex[i]:
                self.fill_order(i, visited_vertex, stack)
        stack = stack.append(d)

    # transpose the matrix
    def transpose(self):
        g = Graph(self.V)

        for i in self.graph:
            for j in self.graph[i]:
                g.add_edge(j, i)
        return g

    # Print stongly connected components
    def print_scc(self):
        stack = []
        visited_vertex = [False] * (self.V)

        for i in range(self.V):
            if not visited_vertex[i]:
                self.fill_order(i, visited_vertex, stack)

        gr = self.transpose()

        visited_vertex = [False] * (self.V)

        while stack:
            i = stack.pop()
            if not visited_vertex[i]:
                gr.dfs(i, visited_vertex)
                print("")

g = Graph(8)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(2, 4)
g.add_edge(3, 0)
g.add_edge(4, 5)
g.add_edge(5, 6)
g.add_edge(6, 4)
g.add_edge(6, 7)

print("Strongly Connected Components:")
g.print_scc()

from collections import defaultdict

class Graph:
    def __init__(self, vertex):
        self.V = vertex
        self.graph = defaultdict(list)

    # Add edge into the graph
    def add_edge(self, s, d):
        self.graph[s].append(d)

    # dfs
    def dfs(self, d, visited_vertex):
        visited_vertex[d] = True
        print(d, end="")
        for i in self.graph[d]:
            if not visited_vertex[i]:
                self.dfs(i, visited_vertex)

    def fill_order(self, d, visited_vertex, stack):
        visited_vertex[d] = True
        for i in self.graph[d]:
            if not visited_vertex[i]:
                self.fill_order(i, visited_vertex, stack)
        stack = stack.append(d)

    # transpose the matrix
    def transpose(self):
        g = Graph(self.V)

        for i in self.graph:
            for j in self.graph[i]:
                g.add_edge(j, i)
        return g

    # Print stongly connected components
    def print_scc(self):
        stack = []
        visited_vertex = [False] * (self.V)

        for i in range(self.V):
            if not visited_vertex[i]:
                self.fill_order(i, visited_vertex, stack)

        gr = self.transpose()

        visited_vertex = [False] * (self.V)

        while stack:
            i = stack.pop()
            if not visited_vertex[i]:
                gr.dfs(i, visited_vertex)
                print("")

g = Graph(8)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(2, 4)
g.add_edge(3, 0)
g.add_edge(4, 5)
g.add_edge(5, 6)
g.add_edge(6, 4)
g.add_edge(6, 7)

print("Strongly Connected Components:")
g.print_scc()

Java

// Kosaraju's algorithm to find strongly connected components in Java

import java.util.*;
import java.util.LinkedList;

class Graph {
    private int V;
    private LinkedList adj[];

    // Create a graph
    Graph(int s) {
        V = s;
        adj = new LinkedList[s];
        for (int i = 0; i < s; ++i)
            adj[i] = new LinkedList();
    }

  // Add edge
    void addEdge(int s, int d) {
        adj[s].add(d);
    }

    // DFS
    void DFSUtil(int s, boolean visitedVertices[]) {
        visitedVertices[s] = true;
        System.out.print(s + " ");
        int n;

        Iterator i = adj[s].iterator();
        while (i.hasNext()) {
            n = i.next();
            if (!visitedVertices[n])
                DFSUtil(n, visitedVertices);
        }
    }

    // Transpose the graph
    Graph Transpose() {
        Graph g = new Graph(V);
        for (int s = 0; s < V; s++) {
            Iterator i = adj[s].listIterator();
            while (i.hasNext())
                g.adj[i.next()].add(s);
        }
        return g;
    }

    void fillOrder(int s, boolean visitedVertices[], Stack stack) {
        visitedVertices[s] = true;

        Iterator i = adj[s].iterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visitedVertices[n])
                fillOrder(n, visitedVertices, stack);
        }
        stack.push(new Integer(s));
    }

    // Print strongly connected component
    void printSCC() {
        Stack stack = new Stack();

        boolean visitedVertices[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visitedVertices[i] = false;

        for (int i = 0; i < V; i++)
            if (visitedVertices[i] == false)
                fillOrder(i, visitedVertices, stack);

        Graph gr = Transpose();

        for (int i = 0; i < V; i++)
            visitedVertices[i] = false;

        while (stack.empty() == false) {
            int s = (int) stack.pop();

            if (visitedVertices[s] == false) {
                gr.DFSUtil(s, visitedVertices);
                System.out.println();
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(8);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(2, 4);
        g.addEdge(3, 0);
        g.addEdge(4, 5);
        g.addEdge(5, 6);
        g.addEdge(6, 4);
        g.addEdge(6, 7);

        System.out.println("Strongly Connected Components:");
        g.printSCC();
    }
}

// Kosaraju's algorithm to find strongly connected components in Java

import java.util.*;
import java.util.LinkedList;

class Graph {
    private int V;
    private LinkedList adj[];

    // Create a graph
    Graph(int s) {
        V = s;
        adj = new LinkedList[s];
        for (int i = 0; i < s; ++i)
            adj[i] = new LinkedList();
    }

  // Add edge
    void addEdge(int s, int d) {
        adj[s].add(d);
    }

    // DFS
    void DFSUtil(int s, boolean visitedVertices[]) {
        visitedVertices[s] = true;
        System.out.print(s + " ");
        int n;

        Iterator i = adj[s].iterator();
        while (i.hasNext()) {
            n = i.next();
            if (!visitedVertices[n])
                DFSUtil(n, visitedVertices);
        }
    }

    // Transpose the graph
    Graph Transpose() {
        Graph g = new Graph(V);
        for (int s = 0; s < V; s++) {
            Iterator i = adj[s].listIterator();
            while (i.hasNext())
                g.adj[i.next()].add(s);
        }
        return g;
    }

    void fillOrder(int s, boolean visitedVertices[], Stack stack) {
        visitedVertices[s] = true;

        Iterator i = adj[s].iterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visitedVertices[n])
                fillOrder(n, visitedVertices, stack);
        }
        stack.push(new Integer(s));
    }

    // Print strongly connected component
    void printSCC() {
        Stack stack = new Stack();

        boolean visitedVertices[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visitedVertices[i] = false;

        for (int i = 0; i < V; i++)
            if (visitedVertices[i] == false)
                fillOrder(i, visitedVertices, stack);

        Graph gr = Transpose();

        for (int i = 0; i < V; i++)
            visitedVertices[i] = false;

        while (stack.empty() == false) {
            int s = (int) stack.pop();

            if (visitedVertices[s] == false) {
                gr.DFSUtil(s, visitedVertices);
                System.out.println();
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(8);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(2, 4);
        g.addEdge(3, 0);
        g.addEdge(4, 5);
        g.addEdge(5, 6);
        g.addEdge(6, 4);
        g.addEdge(6, 7);

        System.out.println("Strongly Connected Components:");
        g.printSCC();
    }
}

++C

// Kosaraju's algorithm to find strongly connected components in C++

#include 
#include 
#include 

using namespace std;

class Graph
{
    int V;
    list *adj;
    void fillOrder(int s, bool visitedV[], stack &Stack);
    void DFS(int s, bool visitedV[]);

public:
    Graph(int V);
    void addEdge(int s, int d);
    void printSCC();
    Graph transpose();
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list[V];
}

// DFS
void Graph::DFS(int s, bool visitedV[])
{
    visitedV[s] = true;
    cout << s << " ";

    list::iterator i;
    for (i = adj[s].begin(); i != adj[s].end(); ++i)
        if (!visitedV[*i])
            DFS(*i, visitedV);
}

// Transpose
Graph Graph::transpose()
{
    Graph g(V);
    for (int s = 0; s < V; s++)
    {
        list::iterator i;
        for (i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            g.adj[*i].push_back(s);
        }
    }
    return g;
}

// Add edge into the graph
void Graph::addEdge(int s, int d)
{
    adj[s].push_back(d);
}

void Graph::fillOrder(int s, bool visitedV[], stack &Stack)
{
    visitedV[s] = true;

    list::iterator i;
    for (i = adj[s].begin(); i != adj[s].end(); ++i)
        if (!visitedV[*i])
            fillOrder(*i, visitedV, Stack);

    Stack.push(s);
}

// Print strongly connected component
void Graph::printSCC()
{
    stack Stack;

    bool *visitedV = new bool[V];
    for (int i = 0; i < V; i++)
        visitedV[i] = false;

    for (int i = 0; i < V; i++)
        if (visitedV[i] == false)
            fillOrder(i, visitedV, Stack);

    Graph gr = transpose();

    for (int i = 0; i < V; i++)
        visitedV[i] = false;

    while (Stack.empty() == false)
    {
        int s = Stack.top();
        Stack.pop();

        if (visitedV[s] == false)
        {
            gr.DFS(s, visitedV);
            cout << endl;
        }
    }
}

int main()
{
    Graph g(8);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 0);
    g.addEdge(4, 5);
    g.addEdge(5, 6);
    g.addEdge(6, 4);
    g.addEdge(6, 7);

    cout << "Strongly Connected Components:\n";
    g.printSCC();
}

// Kosaraju's algorithm to find strongly connected components in C++

#include 
#include 
#include 

using namespace std;

class Graph
{
    int V;
    list *adj;
    void fillOrder(int s, bool visitedV[], stack &Stack);
    void DFS(int s, bool visitedV[]);

public:
    Graph(int V);
    void addEdge(int s, int d);
    void printSCC();
    Graph transpose();
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list[V];
}

// DFS
void Graph::DFS(int s, bool visitedV[])
{
    visitedV[s] = true;
    cout << s << " ";

    list::iterator i;
    for (i = adj[s].begin(); i != adj[s].end(); ++i)
        if (!visitedV[*i])
            DFS(*i, visitedV);
}

// Transpose
Graph Graph::transpose()
{
    Graph g(V);
    for (int s = 0; s < V; s++)
    {
        list::iterator i;
        for (i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            g.adj[*i].push_back(s);
        }
    }
    return g;
}

// Add edge into the graph
void Graph::addEdge(int s, int d)
{
    adj[s].push_back(d);
}

void Graph::fillOrder(int s, bool visitedV[], stack &Stack)
{
    visitedV[s] = true;

    list::iterator i;
    for (i = adj[s].begin(); i != adj[s].end(); ++i)
        if (!visitedV[*i])
            fillOrder(*i, visitedV, Stack);

    Stack.push(s);
}

// Print strongly connected component
void Graph::printSCC()
{
    stack Stack;

    bool *visitedV = new bool[V];
    for (int i = 0; i < V; i++)
        visitedV[i] = false;

    for (int i = 0; i < V; i++)
        if (visitedV[i] == false)
            fillOrder(i, visitedV, Stack);

    Graph gr = transpose();

    for (int i = 0; i < V; i++)
        visitedV[i] = false;

    while (Stack.empty() == false)
    {
        int s = Stack.top();
        Stack.pop();

        if (visitedV[s] == false)
        {
            gr.DFS(s, visitedV);
            cout << endl;
        }
    }
}

int main()
{
    Graph g(8);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 0);
    g.addEdge(4, 5);
    g.addEdge(5, 6);
    g.addEdge(6, 4);
    g.addEdge(6, 7);

    cout << "Strongly Connected Components:\n";
    g.printSCC();
}

کاربردها

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

مولفه های قویا همبند برای حل مسائل 2-Satisfaction استفاده می‌شود.
مولفه‌های قویا همبند برای تجزیه کامپیوترکامپیوتر چیست؟ ⚡️ کامپیوتر چیست به زبان سادهاین مقاله عالی توضیح داده که کامپیوتر چیست و چه کاربردی دارد و همه چیز درباره کامپیوتر از جمله فواید کامپیوتر و تعریف کامپیوتر و اجزای آن را بیان کرده است Dulmage-Mandelsohn استفاده می‌شود
در سایت‌های شبکه‌های اجتماعی، از مولفه های قویا همبند برای نشان‌دادن گروهی از افراد استفاده می‌شود که با یکدیگر دوست هستند یا علایق مشترکی دارند.
می‌توان از مولفه‌ های قویا همبند برای تبدیل یک گراف به یک گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... مستقیم حلقوی از اجزای قویا همبند استفاده کرد.

جمع‌بندی

مولفه های قویا همبند، بخشی از گراف را نشان می‌دهند که در آن مسیری بین هر جفت رأس وجود دارد. در این مقاله به معرفی این مؤلفه پرداختیم؛ همچنین الگوریتم کساراجو که برای پیداکردن مولفه های قویا همبند در گراف استفاده می‌شود را معرفی کردیم و با پیاده‌سازی آن در زبان‌های برنامه‌نویسی مختلف آشنا شدیم.

چگونه مولفه های قویا همبند را تعیین می‌کنیم؟

اگر بتوانیم از هر راس یک مؤلفه، به هر رأس دیگر در آن مؤلفه برسیم، آن را یک مؤلفه قوی متصل (SCC) می‌نامند. تک گره همیشه یک SCC است.

تفاوت بین مولفه همبند و مولفه های قویا همبند چیست؟

مولفه همبند معمولاً در گراف‌های بدون جهت (یال‌های دوطرفه) معنی دارد. یعنی بین هر دو گره یک مسیر وجود دارد. مولفه قویا همبند معمولاً در گراف‌های جهت‌دار (یال‌های یک‌طرفه) معنی دارد. یعنی بین هر دو گره یک مسیر وجود دارد.

چرا از مولفه های قویا همبند استفاده می‌کنیم؟

مولفه های قویا همبند برای حل مشکلات 2-Satisfaction استفاده می‌شود؛ همین‌طور در سایت‌های شبکه‌های اجتماعی، از مؤلفه‌های قویا همبند برای نشان‌دادن گروهی از افرادی استفاده می‌شود که با یکدیگر دوست هستند یا علایق مشترکی دارند.

چگونه متوجه می‌شویم که یک گراف قویا همبند است؟

اگر بتوان از هر رأس در گراف ، به هر رأس دیگر دست‌یافت، می‌گوییم گراف قویا همبند است. یک گراف جهت‌دار دلخواه به زیرگراف‌هایی قویا همبند، توسط مولفه های قویا همبند تقسیم می‌شود.