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

1// A C++ Program to check whether a graph is tree or not 
2#include<iostream> 
3#include <list> 
4#include <limits.h> 
5using namespace std; 
6  
7// Class for an undirected graph 
8class Graph 
9{ 
10    int V;    // No. of vertices 
11    list<int> *adj; // Pointer to an array for adjacency lists 
12    bool isCyclicUtil(int v, bool visited[], int parent); 
13public: 
14    Graph(int V);   // Constructor 
15    void addEdge(int v, int w);   // to add an edge to graph 
16    bool isTree();   // returns true if graph is tree 
17}; 
18  
19Graph::Graph(int V) 
20{ 
21    this->V = V; 
22    adj = new list<int>[V]; 
23} 
24  
25void Graph::addEdge(int v, int w) 
26{ 
27    adj[v].push_back(w); // Add w to v’s list. 
28    adj[w].push_back(v); // Add v to w’s list. 
29} 
30  
31// A recursive function that uses visited[] and parent to 
32// detect cycle in subgraph reachable from vertex v. 
33bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
34{ 
35    // Mark the current node as visited 
36    visited[v] = true; 
37  
38    // Recur for all the vertices adjacent to this vertex 
39    list<int>::iterator i; 
40    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
41    { 
42        // If an adjacent is not visited, then recur for  
43        // that adjacent 
44        if (!visited[*i]) 
45        { 
46           if (isCyclicUtil(*i, visited, v)) 
47              return true; 
48        } 
49  
50        // If an adjacent is visited and not parent of current 
51        // vertex, then there is a cycle. 
52        else if (*i != parent) 
53           return true; 
54    } 
55    return false; 
56} 
57  
58// Returns true if the graph is a tree, else false. 
59bool Graph::isTree() 
60{ 
61    // Mark all the vertices as not visited and not part of  
62    // recursion stack 
63    bool *visited = new bool[V]; 
64    for (int i = 0; i < V; i++) 
65        visited[i] = false; 
66  
67    // The call to isCyclicUtil serves multiple purposes. 
68    // It returns true if graph reachable from vertex 0  
69    // is cyclcic. It also marks all vertices reachable  
70    // from 0. 
71    if (isCyclicUtil(0, visited, -1)) 
72             return false; 
73  
74    // If we find a vertex which is not reachable from 0  
75    // (not marked by isCyclicUtil(), then we return false 
76    for (int u = 0; u < V; u++) 
77        if (!visited[u]) 
78           return false; 
79  
80    return true; 
81} 
82  
83// Driver program to test above functions 
84int main() 
85{ 
86    Graph g1(5); 
87    g1.addEdge(1, 0); 
88    g1.addEdge(0, 2); 
89    g1.addEdge(0, 3); 
90    g1.addEdge(3, 4); 
91    g1.isTree()? cout << "Graph is Tree\n": 
92                 cout << "Graph is not Tree\n"; 
93  
94    Graph g2(5); 
95    g2.addEdge(1, 0); 
96    g2.addEdge(0, 2); 
97    g2.addEdge(2, 1); 
98    g2.addEdge(0, 3); 
99    g2.addEdge(3, 4); 
100    g2.isTree()? cout << "Graph is Tree\n": 
101                 cout << "Graph is not Tree\n"; 
102  
103    return 0; 
104}

1// A Java Program to check whether a graph is tree or not 
2import java.io.*; 
3import java.util.*; 
4  
5// This class represents a directed graph using adjacency 
6// list representation 
7class Graph 
8{ 
9    private int V;   // No. of vertices 
10    private LinkedList<Integer> adj[]; //Adjacency List 
11  
12    // Constructor 
13    Graph(int v) 
14    { 
15        V = v; 
16        adj = new LinkedList[v]; 
17        for (int i=0; i<v; ++i) 
18            adj[i] = new LinkedList(); 
19    } 
20  
21    // Function to add an edge into the graph 
22    void addEdge(int v,int w) 
23    { 
24        adj[v].add(w); 
25        adj[w].add(v); 
26    } 
27  
28    // A recursive function that uses visited[] and parent 
29    // to detect cycle in subgraph reachable from vertex v. 
30    Boolean isCyclicUtil(int v, Boolean visited[], int parent) 
31    { 
32        // Mark the current node as visited 
33        visited[v] = true; 
34        Integer i; 
35  
36        // Recur for all the vertices adjacent to this vertex 
37        Iterator<Integer> it = adj[v].iterator(); 
38        while (it.hasNext()) 
39        { 
40            i = it.next(); 
41  
42            // If an adjacent is not visited, then recur for 
43            // that adjacent 
44            if (!visited[i]) 
45            { 
46                if (isCyclicUtil(i, visited, v)) 
47                    return true; 
48            } 
49  
50            // If an adjacent is visited and not parent of  
51            // current vertex, then there is a cycle. 
52            else if (i != parent) 
53               return true; 
54        } 
55        return false; 
56    } 
57  
58    // Returns true if the graph is a tree, else false. 
59    Boolean isTree() 
60    { 
61        // Mark all the vertices as not visited and not part 
62        // of recursion stack 
63        Boolean visited[] = new Boolean[V]; 
64        for (int i = 0; i < V; i++) 
65            visited[i] = false; 
66  
67        // The call to isCyclicUtil serves multiple purposes 
68        // It returns true if graph reachable from vertex 0 
69        // is cyclcic. It also marks all vertices reachable 
70        // from 0. 
71        if (isCyclicUtil(0, visited, -1)) 
72            return false; 
73  
74        // If we find a vertex which is not reachable from 0 
75        // (not marked by isCyclicUtil(), then we return false 
76        for (int u = 0; u < V; u++) 
77            if (!visited[u]) 
78                return false; 
79  
80        return true; 
81    } 
82  
83    // Driver method 
84    public static void main(String args[]) 
85    { 
86        // Create a graph given in the above diagram 
87        Graph g1 = new Graph(5); 
88        g1.addEdge(1, 0); 
89        g1.addEdge(0, 2); 
90        g1.addEdge(0, 3); 
91        g1.addEdge(3, 4); 
92        if (g1.isTree()) 
93            System.out.println("Graph is Tree"); 
94        else
95            System.out.println("Graph is not Tree"); 
96  
97        Graph g2 = new Graph(5); 
98        g2.addEdge(1, 0); 
99        g2.addEdge(0, 2); 
100        g2.addEdge(2, 1); 
101        g2.addEdge(0, 3); 
102        g2.addEdge(3, 4); 
103  
104        if (g2.isTree()) 
105            System.out.println("Graph is Tree"); 
106        else
107            System.out.println("Graph is not Tree"); 
108  
109    } 
110} 
111// This code is contributed by Aakash Hasija

1# Python Program to check whether  
2# a graph is tree or not 
3  
4from collections import defaultdict 
5  
6class Graph(): 
7  
8    def __init__(self, V): 
9        self.V = V 
10        self.graph  = defaultdict(list) 
11  
12    def addEdge(self, v, w): 
13        # Add w to v ist. 
14        self.graph[v].append(w)  
15        # Add v to w list. 
16        self.graph[w].append(v)  
17  
18    # A recursive function that uses visited[]  
19    # and parent to detect cycle in subgraph  
20    # reachable from vertex v. 
21    def isCyclicUtil(self, v, visited, parent): 
22  
23        # Mark current node as visited 
24        visited[v] = True
25  
26        # Recur for all the vertices adjacent  
27        # for this vertex 
28        for i in self.graph[v]: 
29            # If an adjacent is not visited,  
30            # then recur for that adjacent 
31            if visited[i] == False: 
32                if self.isCyclicUtil(i, visited, v) == True: 
33                    return True
34  
35            # If an adjacent is visited and not  
36            # parent of current vertex, then there  
37            # is a cycle. 
38            elif i != parent: 
39                return True
40  
41        return False
42  
43    # Returns true if the graph is a tree,  
44    # else false. 
45    def isTree(self): 
46        # Mark all the vertices as not visited  
47        # and not part of recursion stack 
48        visited = [False] * self.V 
49  
50        # The call to isCyclicUtil serves multiple  
51        # purposes. It returns true if graph reachable  
52        # from vertex 0 is cyclcic. It also marks  
53        # all vertices reachable from 0. 
54        if self.isCyclicUtil(0, visited, -1) == True: 
55            return False
56  
57        # If we find a vertex which is not reachable 
58        # from 0 (not marked by isCyclicUtil(),  
59        # then we return false 
60        for i in range(self.V): 
61            if visited[i] == False: 
62                return False
63  
64        return True
65  
66# Driver program to test above functions 
67g1 = Graph(5) 
68g1.addEdge(1, 0) 
69g1.addEdge(0, 2) 
70g1.addEdge(0, 3) 
71g1.addEdge(3, 4) 
72print "Graph is a Tree" if g1.isTree() == True \ 
73                          else "Graph is a not a Tree"
74  
75g2 = Graph(5) 
76g2.addEdge(1, 0) 
77g2.addEdge(0, 2) 
78g2.addEdge(2, 1) 
79g2.addEdge(0, 3) 
80g2.addEdge(3, 4) 
81print "Graph is a Tree" if g2.isTree() == True \ 
82                          else "Graph is a not a Tree"
83                            
84# This code is contributed by Divyanshu Mehta