top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+5 votes
1,601 views
WAP to find whether given adjacency matrix represents Graph or Tree?
posted Nov 11, 2013 by Prakash Singh

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button
Every graph is a tree so looks that your question is "WAP to know if a given graph is tree from using its adjacency matrix?"
yes sir you are right every tree is a graph.... actually we have to find cycle... if exist we say its a graph otherwise tree...
Yes see the answer by Anderson....

3 Answers

+4 votes

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.

answer Nov 12, 2013 by anonymous
what is n here?
+3 votes
#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 Nov 12, 2013 by Vikas Upadhyay
+1 vote

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.

answer Nov 12, 2013 by Anderson
Similar Questions
+7 votes

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.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...