Graph::isTree

Function


bool isTree();

Returns whether this graph is a tree or not.

Parameters

None

Return value

Return true if the graph is a tree, false otherwise.

Example

#include "HKUAL_graph.h"
#include <iostream>
using namespace std;
using namespace HKUAL;

int main(){
    Graph<string> g;
    g.addVertex("A");
    g.addVertex("B");
    g.addVertex("C");
    g.addVertex("D");
    g.addEdge("A","B");
    g.addEdge("A","C");
    g.addEdge("B","D");
    g.addEdge("C","D");

    if (g.isTree())
        cout <<"Yes" << endl;
    else
        cout <<"No" << endl;
        
    Graph<string> g2;
    g2.addVertex("A");
    g2.addVertex("B");
    g2.addVertex("C");
    g2.addVertex("D");
    g2.addEdge("A","B");
    g2.addEdge("A","C");
    g2.addEdge("B","D");

    if (g2.isTree())
        cout <<"Yes" << endl;
    else
        cout <<"No" << endl;
    return 0;
}

Output

No
Yes

Time Complexity

, for is number of edges and is total number of vertives.

© The University of Hong Kong Algorithms Library - hkual@cs.hku.hk