در این مطلب، برنامه تشخیص درخت بودن یک گراف در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «پایتون» (Python) و «جاوا» (Java) ارائه شده است. در واقع، هدف نوشتن تابعی است که یک گراف بدون جهت را دریافت کرده و بررسی کند که آیا درخت است یا نه. در صورتی که گراف یک درخت بود «مقدار یک» و در غیر این صورت، «مقدار صفر» را بازگرداند. برای مثال، گراف زیر یک درخت است.

برنامه تشخیص درخت بودن یک گراف -- راهنمای کاربردی

اما، گراف زیر یک درخت نیست.

برنامه تشخیص درخت بودن یک گراف -- راهنمای کاربردی

یک گراف بدون جهت، در صورتی درخت است که مشخصات زیر را داشته باشد:

  1. هیچ دوری نداشته باشد.
  2. گراف هم‌بند باشد.

برای یک گراف بدون جهت، می‌توان از الگوریتم‌های «جستجوی اول سطح» (Breadth-First Search | BFS) یا «جستجوی اول عمق» (Depth-First Search | DFS) برای تشخیص وجود دو ویژگی بالا استفاده کرد. شایان ذکر است، برای مطالعه بیشتر پیرامون گراف و درخت، مطالعه مطالب «گراف — تعاریف و انواع آن به زبان ساده» و «درخت در گراف — به زبان ساده» توصیه می‌شود.

روش شناسایی دور در یک گراف بدون جهت

همانطور که پیش‌تر بیان شد، برای تعیین درخت بودن یا نبودن یک گراف بدون جهت، می‌توان از الگوریتم‌های BFS یا DFS استفاده کرد. برای هر یک از راس‌های بازدید شده v، اگر یک راس هم‌جوار u وجود داشته باشد که پیش از این بازدید شده باشد و u والد v نباشد، یک دور در گراف وجود دارد. اگر چنین راس هم‌جواری برای هیچ یک از راس‌ها یافت نشود، هیچ دوری در گراف وجود ندارد.

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

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

برنامه تشخیص درخت بودن یک گراف در ++C

// A C++ Program to check whether a graph is tree or not 
#include<iostream> 
#include <list> 
#include <limits.h> 
using namespace std; 
  
// Class for an undirected graph 
class Graph 
{ 
    int V;    // No. of vertices 
    list<int> *adj; // Pointer to an array for adjacency lists 
    bool isCyclicUtil(int v, bool visited[], int parent); 
public: 
    Graph(int V);   // Constructor 
    void addEdge(int v, int w);   // to add an edge to graph 
    bool isTree();   // returns true if graph is tree 
}; 
  
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
    adj[w].push_back(v); // Add v to w’s list. 
} 
  
// A recursive function that uses visited[] and parent to 
// detect cycle in subgraph reachable from vertex v. 
bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
{ 
    // Mark the current node as visited 
    visited[v] = true; 
  
    // Recur for all the vertices adjacent to this vertex 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
    { 
        // If an adjacent is not visited, then recur for  
        // that adjacent 
        if (!visited[*i]) 
        { 
           if (isCyclicUtil(*i, visited, v)) 
              return true; 
        } 
  
        // If an adjacent is visited and not parent of current 
        // vertex, then there is a cycle. 
        else if (*i != parent) 
           return true; 
    } 
    return false; 
} 
  
// Returns true if the graph is a tree, else false. 
bool Graph::isTree() 
{ 
    // Mark all the vertices as not visited and not part of  
    // recursion stack 
    bool *visited = new bool[V]; 
    for (int i = 0; i < V; i++) 
        visited[i] = false; 
  
    // The call to isCyclicUtil serves multiple purposes. 
    // It returns true if graph reachable from vertex 0  
    // is cyclcic. It also marks all vertices reachable  
    // from 0. 
    if (isCyclicUtil(0, visited, -1)) 
             return false; 
  
    // If we find a vertex which is not reachable from 0  
    // (not marked by isCyclicUtil(), then we return false 
    for (int u = 0; u < V; u++) 
        if (!visited[u]) 
           return false; 
  
    return true; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    Graph g1(5); 
    g1.addEdge(1, 0); 
    g1.addEdge(0, 2); 
    g1.addEdge(0, 3); 
    g1.addEdge(3, 4); 
    g1.isTree()? cout << "Graph is Tree\n": 
                 cout << "Graph is not Tree\n"; 
  
    Graph g2(5); 
    g2.addEdge(1, 0); 
    g2.addEdge(0, 2); 
    g2.addEdge(2, 1); 
    g2.addEdge(0, 3); 
    g2.addEdge(3, 4); 
    g2.isTree()? cout << "Graph is Tree\n": 
                 cout << "Graph is not Tree\n"; 
  
    return 0; 
}

برنامه تشخیص درخت بودن یک گراف در جاوا

// A Java Program to check whether a graph is tree or not 
import java.io.*; 
import java.util.*; 
  
// This class represents a directed graph using adjacency 
// list representation 
class Graph 
{ 
    private int V;   // No. of vertices 
    private LinkedList<Integer> adj[]; //Adjacency List 
  
    // Constructor 
    Graph(int v) 
    { 
        V = v; 
        adj = new LinkedList[v]; 
        for (int i=0; i<v; ++i) 
            adj[i] = new LinkedList(); 
    } 
  
    // Function to add an edge into the graph 
    void addEdge(int v,int w) 
    { 
        adj[v].add(w); 
        adj[w].add(v); 
    } 
  
    // A recursive function that uses visited[] and parent 
    // to detect cycle in subgraph reachable from vertex v. 
    Boolean isCyclicUtil(int v, Boolean visited[], int parent) 
    { 
        // Mark the current node as visited 
        visited[v] = true; 
        Integer i; 
  
        // Recur for all the vertices adjacent to this vertex 
        Iterator<Integer> it = adj[v].iterator(); 
        while (it.hasNext()) 
        { 
            i = it.next(); 
  
            // If an adjacent is not visited, then recur for 
            // that adjacent 
            if (!visited[i]) 
            { 
                if (isCyclicUtil(i, visited, v)) 
                    return true; 
            } 
  
            // If an adjacent is visited and not parent of  
            // current vertex, then there is a cycle. 
            else if (i != parent) 
               return true; 
        } 
        return false; 
    } 
  
    // Returns true if the graph is a tree, else false. 
    Boolean isTree() 
    { 
        // Mark all the vertices as not visited and not part 
        // of recursion stack 
        Boolean visited[] = new Boolean[V]; 
        for (int i = 0; i < V; i++) 
            visited[i] = false; 
  
        // The call to isCyclicUtil serves multiple purposes 
        // It returns true if graph reachable from vertex 0 
        // is cyclcic. It also marks all vertices reachable 
        // from 0. 
        if (isCyclicUtil(0, visited, -1)) 
            return false; 
  
        // If we find a vertex which is not reachable from 0 
        // (not marked by isCyclicUtil(), then we return false 
        for (int u = 0; u < V; u++) 
            if (!visited[u]) 
                return false; 
  
        return true; 
    } 
  
    // Driver method 
    public static void main(String args[]) 
    { 
        // Create a graph given in the above diagram 
        Graph g1 = new Graph(5); 
        g1.addEdge(1, 0); 
        g1.addEdge(0, 2); 
        g1.addEdge(0, 3); 
        g1.addEdge(3, 4); 
        if (g1.isTree()) 
            System.out.println("Graph is Tree"); 
        else
            System.out.println("Graph is not Tree"); 
  
        Graph g2 = new Graph(5); 
        g2.addEdge(1, 0); 
        g2.addEdge(0, 2); 
        g2.addEdge(2, 1); 
        g2.addEdge(0, 3); 
        g2.addEdge(3, 4); 
  
        if (g2.isTree()) 
            System.out.println("Graph is Tree"); 
        else
            System.out.println("Graph is not Tree"); 
  
    } 
} 
// This code is contributed by Aakash Hasija

برنامه تشخیص درخت بودن یک گراف در پایتون

# Python Program to check whether  
# a graph is tree or not 
  
from collections import defaultdict 
  
class Graph(): 
  
    def __init__(self, V): 
        self.V = V 
        self.graph  = defaultdict(list) 
  
    def addEdge(self, v, w): 
        # Add w to v ist. 
        self.graph[v].append(w)  
        # Add v to w list. 
        self.graph[w].append(v)  
  
    # A recursive function that uses visited[]  
    # and parent to detect cycle in subgraph  
    # reachable from vertex v. 
    def isCyclicUtil(self, v, visited, parent): 
  
        # Mark current node as visited 
        visited[v] = True
  
        # Recur for all the vertices adjacent  
        # for this vertex 
        for i in self.graph[v]: 
            # If an adjacent is not visited,  
            # then recur for that adjacent 
            if visited[i] == False: 
                if self.isCyclicUtil(i, visited, v) == True: 
                    return True
  
            # If an adjacent is visited and not  
            # parent of current vertex, then there  
            # is a cycle. 
            elif i != parent: 
                return True
  
        return False
  
    # Returns true if the graph is a tree,  
    # else false. 
    def isTree(self): 
        # Mark all the vertices as not visited  
        # and not part of recursion stack 
        visited = [False] * self.V 
  
        # The call to isCyclicUtil serves multiple  
        # purposes. It returns true if graph reachable  
        # from vertex 0 is cyclcic. It also marks  
        # all vertices reachable from 0. 
        if self.isCyclicUtil(0, visited, -1) == True: 
            return False
  
        # If we find a vertex which is not reachable 
        # from 0 (not marked by isCyclicUtil(),  
        # then we return false 
        for i in range(self.V): 
            if visited[i] == False: 
                return False
  
        return True
  
# Driver program to test above functions 
g1 = Graph(5) 
g1.addEdge(1, 0) 
g1.addEdge(0, 2) 
g1.addEdge(0, 3) 
g1.addEdge(3, 4) 
print "Graph is a Tree" if g1.isTree() == True \ 
                          else "Graph is a not a Tree"
  
g2 = Graph(5) 
g2.addEdge(1, 0) 
g2.addEdge(0, 2) 
g2.addEdge(2, 1) 
g2.addEdge(0, 3) 
g2.addEdge(3, 4) 
print "Graph is a Tree" if g2.isTree() == True \ 
                          else "Graph is a not a Tree"
                            
# This code is contributed by Divyanshu Mehta

خروجی

Graph is Tree
Graph is not Tree

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد.

مشاهده بیشتر