Является ли граф деревом

Question

Является ли граф деревом

Рейтинг: 3Ответов: 2Опубликовано: 18.01.2011

Задачка: Предложите алгоритм, который определяет, является ли граф деревом.

Мое решение, которое, как оказалась, неверное

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);
}

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

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

Источник: Stack Overflow на русском

Answer 1

▲ 4

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

Answer 2

▲ 3

Моё решение на 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.

Является ли граф деревом

Ответы