تا ۵۰٪ تخفیف در جشنواره کوله پشتی بهار
دیدن تخفیف‌ها و شرکت در جشنواره
مدت زمان باقیمانده :
ثانیه -
دقیقه -
ساعت -
روز -
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

این صفحه عالی مولفه های قویا همبند در گراف را معرفی و نحوه محاسبه آن و الگوریتم بدست آوردن آن را آموزش داده و گراف قویا همبند را نیز معرفی کرده است

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

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

 تصویر گراف

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

تصویر گراف همبند 

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

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

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

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();
    }
}

++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();
}

کاربردها

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

جمع‌بندی

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

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

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

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

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

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

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

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

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

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (1 امتیاز)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200