Является ли граф деревом [закрыт]

#алгоритм #графы #дерево

        
             
                
                    
                        
                            Закрыт. На этот вопрос невозможно дать объективный ответ.
Ответы на него в данный момент не принимаются.
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Переформулируйте вопрос,
чтобы на него можно было дать ответ, основанный на фактах и цитатах, отредактировав его.
                        
                        Закрыт 4 года назад.
                                                                                
           
                
        
Задачка: Предложите алгоритм, который определяет, является ли граф деревом.
Мое решение, которое, как оказалась, неверное 
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);
}

Думаю, некоторым будет интересно решить :)    

Ответы

Ответ 1

Дерево - связный граф с n-1 ребром.
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;
}


Ответ 2

Моё решение на Pascal. Граф задаётся матрицей смежности (1 - есть ребро, 0 - иначе).
maxV - максимальное число вершин
maxE - максимальное число рёбер
Храню граф списком рёбер.
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.


Ответ 3

Есть несколько способов решения. Можно использовать свойство ацикличности с подсчетом
количества вершин, те обходим граф в ширину/глубину, подсчитывая число обойденных вершин,
если мы обошли граф и не встретили ни одну вершину два раза, а также общее количество
вершин и число обойденных вершин равны, то это дерево .


Ответ 4

Выполняем обычный проход по графу и каждую пройденный узел заносим в список, при
этом проверяем не содержится ли он в нем уже. Если содержится то всё не дерево :-)