Ağac əldə et#978

Ağac əldə et (Həll təhlili)

Birinci tətikdən başlayaraq dərindən axtarış (DFS) həyata keçirək. Dərindən axtarış ağacını qururuq və onun bütün qövslərini göstərək.

Misal

Misaldakı qrafıq aşağıdakı kimidir:

Dərindən axtarışa tətiq $1$ -dən başlayaraq kənarları keçəcək: $(1, 2), (2, 3), (3, 4)$ (1, 2), (2, 3), (3, 4).

Alqoritmin icrası

Qrafın qonşuluq matrisini $g$ massivində saxlayırıq.

#define MAX 101
int g[MAX][MAX], used[MAX];

dfs funksiyası tətiq $v$ -dən başlayaraq dərindən axtarış həyata keçirir. Dərindən axtarış ağacına daxil olan hər bir kənarı $(v, i)$ göstəririk.

void dfs(int v)
{
  used[v] = 1;
  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i])
    {
      printf("%d %d\n",v,i);
      dfs(i);
    }
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d",&n,&m);
memset(g,0,sizeof(g)); memset(used,0,sizeof(used));
while(m--)
{
  scanf("%d %d",&a,&b);
  g[a][b] = g[b][a] = 1;
}

C++

Birinci tətiqdən dərindən axtarışı başlatırıq.

dfs(1);

Java icrası

import java.util.*;

public class Main
{
  static int g[][], used[];
  static int n, m;
  
  static void dfs(int v)
  {
    used[v] = 1;
    for(int i = 1; i <= n; i++) 
      if (g[v][i] == 1 && used[i] == 0)
      {
        System.out.println(v + " " + i);
        dfs(i);
      }
    used[v] = 2;    
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    g = new int[n+1][n+1];
    used = new int[n+1];
    
    for(int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();      
      g[a][b] = g[b][a] = 1;
    }
    
    dfs(1);
    con.close();
  }
}

Java