Eninə dolaşma (Həll təhlili)

$s$ -dən $f$ -ə qədər qrafın ən qısa yolunu genişlik üzrə axtarışla tapırıq.

Nümunə

Nümunədə verilmiş qraf belə görünür:

Alqoritmin realizasiyası

Qrafı saxlamaq üçün qonşuluq matrisasını $g$ , zirvələrə qədər başlanğıcdan olan ən qısa məsafələri saxlamaq üçün isə $d i s t$ massivini elan edirik.

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

bfs funksiyası $s t a r t$ zirvəsindən genişlik üzrə axtarışı həyata keçirir.

void bfs(int start)
{

$d i s t$ massivini ilkləndiririk. Əgər $d i s t [i] = - 1$ dist[i] = -1 isə, deməli $i$ zirvəsi hələ ziyarət edilməyib.

  memset(dist, -1, sizeof(dist));
  dist[start] = 0;

Növbəti $q$ elan edir və ilkləndiririk.

  queue<int> q;
  q.push(start);

Növbə boş olana qədər genişlik üzrə axtarışı davam etdiririk.

  while (!q.empty())
  {

Başdan zirvə $v$ -ni çıxardırıq və növbədən götürürük.

    int v = q.front(); q.pop();

Zirvə $v$ -dən haraya gedə bilər? $v \to t o$ v → to qablağını yoxlayırıq.

    for (int to = 1; to <= n; to++)

Əgər $v$ -dən $t o$ -ya qədər qablağı varsa və $t o$ zirvəsi hələ keçilməyibsə, o zaman ora gedirik (qablaq $(v, t o)$ (v, to) genişlik üzrə axtarışda ağac qablağıdır).

      if (g[v][to] && dist[to] == -1)
      {

Zirvə $t o$ -nu növbənin sonuna əlavə edirik. $d i s t [t o]$ dist[to] ən qısa məsafəni hesablamaq.

        q.push(to);
        dist[to] = dist[v] + 1;
      }
  }
}

Proqramın əsas hissəsi. Giriş verilənləri oxuyuruq.

scanf("%d %d %d", &n, &s, &f);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
  scanf("%d", &g[i][j]);

$s$ zirvəsindən genişlik üzrə axtarışa başlayırıq.

bfs(s);

Ən qısa məsafəni çıxardırıq. Əgər $f$ zirvəsinə yol yoxdur $(d i s t [f] < 0)$ (dist[f] < 0) isə $d i s t [f] = 0$ dist[f] = 0 təyin edirik.

if (dist[f] < 0) dist[f] = 0;
printf("%d\n", dist[f]);

Alqoritmin realizasiyası — qonşuluq siyahısı

Qrafı saxlamaq üçün qonşuluq siyahısını $g$ , zirvələrə qədər başlanğıcdan olan ən qısa məsafələri saxlamaq üçün $d i s t$ massivini elan edirik.

vector<vector<int> > g;
vector<int> dist;

bfs funksiyası $s t a r t$ zirvəsindən genişlik üzrə axtarışı həyata keçirir.

void bfs(int start)
{

$d i s t$ massivini ilkləndiririk. Əgər $d i s t [i] = - 1$ dist[i] = -1 isə, deməli $i$ zirvəsi hələ ziyarət edilməyib.

  dist = vector<int>(n + 1, -1);
  dist[start] = 0;

Növbəti $q$ elan edir və ilkləndiririk.

  queue<int> q;
  q.push(start);

Növbə boş olana qədər genişlik üzrə axtarışı davam etdiririk.

  while (!q.empty())
  {

Başdan zirvə $v$ -ni çıxardırıq və növbədən götürürük.

    int v = q.front(); q.pop();

Zirvə $v$ -dən haraya gedə bilər? $v \to t o$ v → to qablağını yoxlayırıq.

    for (int to : g[v])

Əgər $t o$ zirvəsi hələ keçilməyibsə, o zaman ora gedirik (qablaq $(v, t o)$ (v, to) genişlik üzrə axtarışda ağac qablağıdır).

      if (dist[to] == -1)
      {

Zirvə $t o$ -nu növbənin sonuna əlavə edirik. $d i s t [t o]$ dist[to] ən qısa məsafəni hesablamaq.

        q.push(to);
        dist[to] = dist[v] + 1;
      }
  }
}

Proqramın əsas hissəsi. Giriş verilənləri oxuyuruq.

scanf("%d %d %d", &n, &s, &f);
g.resize(n + 1);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
  scanf("%d", &val);
  if (val == 1) g[i].push_back(j);
}

C++

$s$ zirvəsindən genişlik üzrə axtarışa başlayırıq.

bfs(s);

Ən qısa məsafəni çıxardırıq. Əgər $f$ zirvəsinə yol yoxdur $(d i s t [f] < 0)$ (dist[f] < 0) isə $d i s t [f] = 0$ dist[f] = 0 təyin edirik.

if (dist[f] < 0) dist[f] = 0;
printf("%d\n", dist[f]);

Java realizasiyası — qonşuluq matrisası

import java.util.*;

public class Main
{
  static int g[][], dist[];
  static int n, s, f;
    
  static void bfs(int start)
  {
    Arrays.fill(dist,-1);
    dist[start] = 0;

    Queue<Integer> q = new LinkedList<Integer>();
    q.add(start);

    while(!q.isEmpty())
    {
      int v = q.poll();
      for(int to = 1; to <= n; to++)
        if (g[v][to] == 1 && dist[to] == -1)
        {
          q.add(to);
          dist[to] = dist[v] + 1;
        }
    }
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    s = con.nextInt();
    f = con.nextInt();
    g = new int[n+1][n+1];
    dist = new int[n+1];
 
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)    	
      g[i][j] = con.nextInt();
    
    bfs(s);

    if (dist[f] < 0) dist[f] = 0;
    System.out.println(dist[f]);
    
    con.close();
  }
}

Java

Java realizasiyası — qonşuluq siyahısı

import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;	
  static int dist[];
  
  static void bfs(int start)
  {
    Arrays.fill(dist,-1);
    dist[start] = 0;

    Queue<Integer> q = new LinkedList<Integer>();
    q.add(start);

    while(!q.isEmpty())
    {
      int v = q.poll();
      for(int i = 0; i < g[v].size(); i++)
      {
        int to = g[v].get(i);
        if (dist[to] == -1)
        {
          q.add(to);
          dist[to] = dist[v] + 1;
        }
      }
    }
  }
  
  @SuppressWarnings("unchecked")  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int s = con.nextInt();
    int f = con.nextInt();
    
    g = new ArrayList[n+1];
    for(int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();
    
    dist = new int[n+1];

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
    {
      int val = con.nextInt();
      if (val == 1) g[i].add(j);
    }

    bfs(s);

    if (dist[f] < 0) dist[f] = 0;
    System.out.println(dist[f]);
    con.close();
  }
}

Java

Python realizasiyası — qonşuluq matrisası

İkidən ibarət növbəni idxal edirik.

from collections import deque

bfs funksiyası $s t a r t$ zirvəsindən genişlik üzrə axtarışı həyata keçirir.

def bfs(start):

Qlobal $d i s t$ siyahısını ilkləndiririk. Əgər $d i s t [i] = - 1$ dist[i] = -1 isə, deməli $i$ zirvəsi hələ ziyarət edilməyib.

  global dist
  dist = [-1] * (n + 1)
  dist[start] = 0

Növbəti $q$ elan edir və ilkləndiririk.

  q = deque([start])

Növbə boş olana qədər genişlik üzrə axtarışı davam etdiririk.

  while q:

Başdan zirvə $v$ -ni çıxardırıq və növbədən götürürük.

    v = q.popleft()

Zirvə $v$ -dən haraya gedə bilər? $v \to t o$ v → to qablağını yoxlayırıq.

    for to in range(1, n + 1):

Əgər $v$ -dən $t o$ -ya qədər qablağı varsa və $t o$ zirvəsi hələ keçilməyibsə, o zaman ora gedirik (qablaq $(v, t o)$ (v, to) genişlik üzrə axtarışda ağac qablağıdır).

      if g[v][to] == 1 and dist[to] == -1:

Zirvə $t o$ -nu növbənin sonuna əlavə edirik. $d i s t [t o]$ dist[to] ən qısa məsafəni hesablamaq.

        q.append(to)
        dist[to] = dist[v] + 1

Proqramın əsas hissəsi. Giriş verilənləri oxuyuruq.

n, s, f = map(int, input().split())
g = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
  g[i] = [0] + list(map(int, input().split()))

$s$ zirvəsindən genişlik üzrə axtarışa başlayırıq.

bfs(s)

Ən qısa məsafəni çıxardırıq. Əgər $f$ zirvəsinə yol yoxdur $(d i s t [f] < 0)$ (dist[f] < 0) isə $d i s t [f] = 0$ dist[f] = 0 təyin edirik.

if dist[f] < 0: dist[f] = 0
print(dist[f])

Python realizasiyası — qonşuluq siyahısı

İkidən ibarət növbəni idxal edirik.

from collections import deque

bfs funksiyası $s t a r t$ zirvəsindən genişlik üzrə axtarışı həyata keçirir.

def bfs(start):

Qlobal $d i s t$ siyahısını ilkləndiririk. Əgər $d i s t [i] = - 1$ dist[i] = -1 isə, deməli $i$ zirvəsi hələ ziyarət edilməyib.

  global dist
  dist = [-1] * (n + 1)
  dist[start] = 0

Növbəti $q$ elan edir və ilkləndiririk.

  q = deque([start])

Növbə boş olana qədər genişlik üzrə axtarışı davam etdiririk.

  while q:

Başdan zirvə $v$ -ni çıxardırıq və növbədən götürürük.

    v = q.popleft()

Zirvə $v$ -dən haraya gedə bilər? $v \to t o$ v → to qablağını yoxlayırıq.

    for to in g[v]:

Əgər $t o$ zirvəsi hələ keçilməyibsə, o zaman ora gedirik (qablaq $(v, t o)$ (v, to) genişlik üzrə axtarışda ağac qablağıdır).

      if dist[to] == -1:

Zirvə $t o$ -nu növbənin sonuna əlavə edirik. $d i s t [t o]$ dist[to] ən qısa məsafəni hesablamaq.

        q.append(to)
        dist[to] = dist[v] + 1

Proqramın əsas hissəsi. Giriş verilənləri oxuyuruq.

n, s, f = map(int, input().split())

Qonşuluq siyahısını $g$ ilkləndirir və qururuq.

g = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
  row = [0] + list(map(int, input().split()))
  for j in range(1, n + 1):
    if row[j] == 1: g[i].append(j)

$s$ zirvəsindən genişlik üzrə axtarışa başlayırıq.

bfs(s)

Ən qısa məsafəni çıxardırıq. Əgər $f$ zirvəsinə yol yoxdur $(d i s t [f] < 0)$ (dist[f] < 0) isə $d i s t [f] = 0$ dist[f] = 0 təyin edirik.

if dist[f] < 0: dist[f] = 0
print(dist[f])