Is the graph a tree [closed]
Want to improve this question? Reformulate the question so that it can be answered based on facts and quotations.
Closed 5 years ago.
Improve the questionProblem: Propose an algorithm that determines whether a graph is a tree.
My decision, which, as it turned out, is wrong
bool is_rec( int arr[SIZE][SIZE], int current, int root, int find )
{
bool endFlag = true;
for(int i = 0; i < SIZE; ++i){
if((arr[current][i] == 1)&&(i!=root)){
if(i!=find){
endFlag = endFlag&&is_rec(arr,i,current,find);
}else{
return false;
}
}
}
return endFlag;
}
bool IsTree( int arr[SIZE][SIZE] )
{
return is_rec(arr,0,0,0);
}
I think some people will be interested in solving :)
4 answers
A tree is a connected graph with n-1 edges.
bool dfs(int i, int arr[SIZE][SIZE], bool col[SIZE]) {
if (col[i]) {
return 0;
}
col[i] = true;
for (int j = 0; j < SIZE; ++j) {
if (ar[i][j]) {
dfs(j, arr, col);
}
}
}
bool IsTree(int arr[SIZE][SIZE]) {
int edges = 0;
for (int i = 0; i < SIZE; ++i) {
for (int j = i + 1; j < SIZE; ++j) {
if (arr[i][j]) {
edges++;
}
}
}
if (edges != SIZE - 1) {
return false;
}
bool col[SIZE];
memset(col, 0, sizeof(col));
dfs(0, arr, col);
for (int i = 0; i < SIZE; ++i) {
if (!col[i]) {
return false;
}
}
return true;
}
My solution is in Pascal. The graph is given by the adjacency matrix (1-there is an edge, 0-otherwise). maxV - the maximum number of vertices maxE - maximum number of edges I store the graph with a list of edges.
const
maxV = 111;
maxE = 111111*2;
var
n,m,i,j,x : longint;
ef,es,next : array [1..maxE] of longint;
first,last : array [1..maxV] of longint;
c : longint;
used : array [1..maxV] of boolean;
flag : boolean;
procedure add(v1,v2 : longint);
begin
inc(c);
ef[c] := v1; es[c] := v2;
if last[v1] <> 0 then next[last[v1]] := c;
if first[v1] = 0 then first[v1] := c;
last[v1] := c;
end;
procedure dfs(v,dad : longint);
var
h,e : longint;
begin
used[v] := true;
h := first[v];
while h > 0 do begin
e := es[h];
if used[e] and (e <> dad) then begin
flag := false;
exit;
end;
if e <> dad then
dfs(e,v);
if not flag then
exit;
h := next[h];
end;
end;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(n);
for i := 1 to n do
for j := 1 to n do begin
read(x);
if x = 1 then
add(i,j);
end;
flag := true;
dfs(1,1);
for i := 1 to n do
if not used[i] then
flag := false;
if not flag then
writeln('NO')
else
writeln('YES');
end.
There are several ways to solve it. You can use the acyclicity property with counting the number of vertices, those traversing the graph in width/depth, counting the number of traversed vertices, if we traversed the graph and did not meet any vertex twice, and the total number of vertices and the number of traversed vertices are equal, then this is a tree .
We perform a normal pass through the graph and enter each passed node in the list, while checking whether it is already contained in it. If contained then everything is not a tree :-)