На этом шаге мы рассмотрим еще одну область применимости алгоритма Уоршалла.

Рассмотрим матричный алгоритм отыскания компонент сильной связности (бикомпонент) ориентированного графа, следуя монографии [1, с.54-55].

Определение.

Ориентированный граф называется сильно связным, если для любой пары вершин каждая из них достижима из другой [1, с.11].

Сильно связный подграф ориентированного графа называется зоной.

Зона, максимальная относительно включения вершин, называется компонентой сильной связности (бикомпонентой).

Знание матрицы достижимости позволяет выявить все компоненты сильной связности в ориентированном графе.

Определим поэлементное (адамарово) произведение матриц B=(b_ij) и C=(c_ij) по правилу: B *C=(b_ij * c_ij).

Тогда вершины бикомпоненты ориентированного графа, содержащей вершину x_i, определяются единичными элементами i-й строки матрицы R * R^T, где R^T - транспонированная матрица достижимости.

Отсюда следует, что, вычислив поэлементное произведение матриц R и R^T и разбив все ненулевые строки этого произведения на группы одинаковых строк, мы можем определить множество вершин каждой бикомпоненты, поскольку номера строк однозначно определяют номера вершин, входящих в бикомпоненту.

Пример. Нахождение бикомпонент ориентированного графа.

#include <iostream.h>
#define MaxNodes 4

class Warshall
{
  private:
    unsigned Adj[MaxNodes][MaxNodes];  //Матрица смежностей.
    unsigned Path[MaxNodes][MaxNodes]; //Матрица достижимости.
    unsigned PathT[MaxNodes][MaxNodes];//Транспонированная матрица достижимости.
    unsigned Adam[MaxNodes][MaxNodes]; //Результат адамарова 
                                       //произведения Path*PathT.
  public:
    void Vvod();
    void TransClose();
    void Vyvod_D();
    void Trans();
    void Adamar();
    void Vyvod_A();
};

void Warshall::Vvod()
{
  //Ввод матрицы смежностей заданного графа.
  cout <<"Вводите элементы матрицы смежностей по строкам:\n";
  for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
     {
       cout <<"Введите Adj["<< (i+1) << "]["<< (j+1) << "]: ";
       cin >> Adj[i][j];
     }
}

void Warshall::TransClose()
//Вычисление матрицы достижимости.
{
  //Инициализация матрицы Path матрицей смежностей Adj.
  for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
      Path[i][j] = Adj[i][j];
  //Нахождение следующих значений матрицы Path.
  for (int k=0;k<MaxNodes;k++)
    for (i=0;i<MaxNodes;i++)
      if (Path[i][k]==1) 
         for (int j=0;j<MaxNodes;j++)
               Path[i][j] = (Path[i][j] || Path[k][j]);
}

void Warshall::Vyvod_D()
//Вывод матрицы достижимости.
{
  cout << "Матрица достижимости:\n";
  for (int i=0;i<MaxNodes;i++)
  {
    for (int j=0;j<MaxNodes;j++)
      cout << Path[i][j] << " ";
    cout << endl;
  }
}

void Warshall::Trans()
//Транспонирование матрицы Path и помещение результата в
//матрицу PathT.
{
  unsigned k,r;
  for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
    {
      k = Path[i][j]; r = Path[j][i];
      PathT[j][i] = k; PathT[i][j] = r;
    }
}

void Warshall::Adamar()
//Нахождение адамарова произведения PathхPathT.
{
  for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
        Adam[i][j] = Path[i][j]*PathT[i][j];
}

void Warshall::Vyvod_A()
//Вывод адамарова произведения.
{
  cout << "Адамарово произведение:\n";
  for (int i=0;i<MaxNodes;i++)
  {
    for (int j=0;j<MaxNodes;j++)
      cout << Adam[i][j] << " ";
    cout << endl;
  }
}

void main()
{
  Warshall A;
  A.Vvod();
  A.TransClose();
  A.Vyvod_D();
  A.Trans();
  A.Adamar();
  A.Vyvod_A();
}

Текст этой программы можно взять здесь.

Замечания.

Приведенный простейший матричный алгоритм отыскания бикомпонент принадлежит, по-видимому, С.Рамамурти [1, с.119].
[1, с.55]. Более эффективные алгоритмы отыскания бикомпонент основаны на обходе графа в глубину.

⁽¹⁾ Евстигнеев В.А. Применение теории графов в программировании. -М.: Hаука, 1985. - 352 с.

На следующем шаге мы рассмотрим вопросы, связанные с определением рекурсивности процедуры.

Предыдущий шаг Содержание Следующий шаг