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

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

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

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

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

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

الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد کساراجو بر اساس الگوریتم جستجوی عمق اولالگوریتم جستجوی اول عمق ⚡️ آموزش الگوریتم 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) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته، جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا یک زبان برنامه نویسی همه منظوره، مبتنی بر کلاس و شی گرا است که برای داشتن وابستگی های پیاده سازی کمتر طراحی شده است، زبان برنامه نویسی جاوا شبیه ++C است و سی پلاس پلاسبرنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده می‌پردازیم:

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 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... مستقیم حلقوی از اجزای قویا همبند استفاده کرد.

جمع‌بندی

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

مطالب مرتبط

همه مقالات

معنی باگ چیست | باگ یعنی چه؟ | انواع باگ های نرم افزاری

الگوریتم اینستاگرام چیست و چگونه کار می‌کند؟⚡️ 2023

پیمایش درخت، آموزش پیمایش درخت دودویی

پروژه برنامه نویسی چیست؟ ⚡️ ویژگی های پروژه برنامه نویسی خوب