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

1,595 views
WAP to find whether given adjacency matrix represents Graph or Tree?
posted Nov 11, 2013

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....

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?
``````#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;
}
``````