WAP to find whether given adjacency matrix represents Graph or Tree?

Question

A binary tree is given and two nodes of this tree is given, we have to find out the algorithm/code for lowest common ancestor of the two given nodes. Common ancestor are the nodes which can be reached from two nodes by following the parent links. Lowest common ancestor is the common ancestor which has the highest depth.

Answer 1

First simple check is to see whether the given adjacency matrix contains more than (n-1) 1's(in the case of undirected graph (2n-2) 1's). If so it is not a tree. Second simple check is to start a traversal(DFS orBFS) from one of the nodes and look for a node which is already visited. if so it involves a cycle and hence not a tree.

Comments

what is n here?

Answer 2

#define TREE 1
#define GRAPH 2

int find(int v, int *p)
{
    while(v != p[v])
        v = p[v];
    return v;
}
void union(int i, int j, int *p)
{
    if(i > j)
        p[i] = j;
    else
        p[j] = i;
}

int Is_TREE_Or_GRAPH(int a[][] , int n)
{
    int idx, p[n];
    int  u, u1, v, v1;

    for (idx = 0; idx < n; idx++)
        p[idx] = idx;

    for (row = 0; row < n; row++)
    {
        for (col = 0; col < row; col++)
        {
            if(a[row][col] == 1)
            {
                u = row;
                v = col;
                u1 = find(u, p);
                v1 = find(v, p);
                if (u1 == v1)
                    return GRAPH;
                union(u1, v1, p);
            }
        }
    }
    return TREE;
}

Answer 3

Keep the simple face in mind to solve this -
A tree is a directed graph if and only if it has n vertices (nodes) with n-1 edges. Now it should be simple to solve.