{"id":26323,"date":"2017-10-26T21:03:39","date_gmt":"2017-10-26T15:33:39","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26323"},"modified":"2017-10-26T21:03:39","modified_gmt":"2017-10-26T15:33:39","slug":"c-algorithm-check-given-graph-tree-not","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-check-given-graph-tree-not\/","title":{"rendered":"C++ Algorithm – Check if a given graph is tree or not"},"content":{"rendered":"

Write a function that returns true if a given undirected graph is tree and false otherwise. For example, the following graph is a tree.<\/span><\/p>\n

 <\/p>\n

But the following graph is not a tree.<\/p>\n

An undirected graph is tree if it has following properties.
\n1) There is no cycle.
\n2) The graph is connected.<\/p>\n

For an undirected graph we can either use BFS or DFS to detect above two properties.<\/p>\n

How to detect cycle in an undirected graph?<\/strong>
\nWe can either use BFS or DFS. For every visited vertex \u2018v\u2019, if there is an adjacent \u2018u\u2019 such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don\u2019t find such an adjacent for any vertex, we say that there is no cycle (See Detect cycle in an undirected graph for more details).<\/p>\n

How to check for connectivity?<\/strong>
\nSince the graph is undirected, we can start BFS or DFS from any vertex and check if all vertices are reachable or not. If all vertices are reachable, then graph is connected, otherwise not.<\/p>\n[ad type=”banner”]\n

C++ \u00a0Programming:<\/strong><\/p>\n

<\/div> 
\/\/ 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 graphclass 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\u2019s list.    adj[w].push_back(v); \/\/ Add v to w\u2019s 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 functionsint 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;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Graph is Tree\r\nGraph is not Tree<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C++ Algorithm – Check if a given graph is tree or not –  Graph Algorithm – Write a function that returns true if a given undirected graph is tree <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,1,74168,73906],"tags":[78368,76523,76546,76185,76184,76183,78377,76187,76525,78378,76522,78376,78375,78367],"class_list":["post-26323","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-dfs-and-bfs","category-graph-algorithms","tag-c-program-to-check-whether-the-given-graph-is-tree","tag-cycle-in-directed-graph","tag-detect-cycle-in-directed-graph","tag-detect-cycle-in-directed-graph-in-c","tag-detect-cycle-in-directed-graph-java","tag-detect-cycle-in-undirected-graph","tag-detect-cycle-in-undirected-graph-bfs","tag-detect-cycle-in-undirected-graph-in-c","tag-detect-cycle-in-undirected-graph-java","tag-detect-cycle-in-undirected-graph-using-dfs","tag-find-all-cycles-in-an-undirected-graph","tag-given-an-array-of-integers-print-the-2-elements-with-least-absolute-difference","tag-how-to-check-if-a-directed-graph-is-a-tree","tag-how-to-check-if-a-graph-is-a-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26323","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26323"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26323\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26323"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26323"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26323"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}