Некоторые задачи на графах

Далее приводится демонстрационная программа для нахождения компонент двусвязности в неориентированном графе, использующая алгоритм обхода в глубину. Для представления вершины графа и графа в целом используются объекты. Вершины графа размечаются латинскими буквами.

Для каждой вершины графа вводится строка латинских букв — меток смежных вершин, т. е. исходное представление графа — набор множеств смежности в виде массивов. Пустая строка завершает ввод.

Далее из введённых массивов формируется матрица смежности. Она делается симметричной с нулевой главной диагональю. Тем самым устраняется дублирование и возможная неполнота ввода.

Затем с помощью функции make() матрица смежности преобразуется в списки смежности, которые и поступают на обработку в функцию DBL().

В процессе обхода графа делается контрольный вывод содержимого стека рёбер — после добавления очередного ребра-ветви, после обнаружения хорды и при определении точки сочленения. В последнем случае выводятся текущие значения массивов глубинных номеров NUM и параметров L, а также множество рёбер, образующих компоненту двусвязности, взятую из стека.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <ctype.h>

#include <string.h>

#include <iostream>

using namespace std;

class Node { int d;

Node * next;

public:

Node(){ next = NULL; }

~Node(){ if (next) delete next; }

friend class GR;

};

const int MaxN = 700, MaxV = 26;

char Ch(int s) { return s+'a'; }

class GR {

Node ** LIST;

int num, * NUM, * L, * STACK, ust, n, m;

public:

void DBL (int v, int p);

void Make (int [ MaxV ][ MaxV ]);

void DBL_Exec();

GR(int);

~GR();

};

GR:: GR(int MaxV): num(0), ust(0), n(0), m(0)

{ LIST = new Node * [ MaxV ]; NUM = new int[ MaxV ];

L = new int[ MaxV ]; STACK = new int[ MaxV ];}

GR:: ~GR()

{ delete [ ] STACK; delete [ ] L; delete [ ] NUM; delete [ ] LIST; }

void GR:: DBL_Exec()

{

for (int i = 0; i < n; i++) { NUM[ i ] = 0; L[ i ] = 0; }

num = 0; ust = 0;

for (int i = 0; i < n; i++)

if (NUM[ i ] == 0)

DBL(i, –1);

cout << ‘\n’ << "NUM="; for(int i = 0; i < n; i++) cout << NUM[i] << " ";

cout << ‘\n’ << " L="; for(int i=0; i<n; i++) cout << L[ I ] << " ";

}

void GR:: DBL (int v, int p)

{ Node * u;

int e1, e2;

NUM[ v ] = L[ v ] = ++num;

for (u = LIST[ v ]; u; u = u->next)

{ if (NUM[ u->d ] == 0)

{ STACK[ ust++ ] = u->d; STACK[ ust++ ] = v;

cout << ‘\n’ << "st1:"; for (int i=0; i<ust; i++) cout << Ch(STACK[ i ]); _getch();

DBL(u->d, v);

L[ v ] = L[ u->d ] < L[ v ]? L[ u->d ]: L[ v ];

if (L[ u->d ] >= NUM[ v ])

{

cout << ‘\n’ << "NUM="; for (int i = 0; i < n; i++) cout << NUM[ i ] << " ";

cout << ‘\n’ << " L="; for (int i = 0; i < n; i++) cout << L[ i ] << " ";

cout << ‘\n’ << " ребро <" << Ch(v) << '-' << Ch(u->d) << "> замыкает компоненту [";

do {

e1 = STACK[ --ust ];

e2 = STACK[ --ust ];

cout << Ch(e1) << '-' << Ch(e2) << ';';

} while (((e1!= v) || (e2!= u->d)) && (ust));

cout << "] ";

cout << ‘\n’ << "st3:"; for (int i = 0; i < ust; i++) cout << Ch(STACK[ i ]); _getch();

}

}

else if ((u->d!= p) && (NUM[ u->d ] < NUM[ v ]))

{ STACK[ ust++ ] = u->d; STACK[ ust++ ] = v;

cout << ‘\n’ << "st2:"; for (int i = 0; i < ust; i++) cout << Ch(STACK[ i ]); _getch();

L[ v ] = NUM[ u->d ] < L[ v ]? NUM[ u->d ]: L[ v ];

}

}

cout << " < " << v << '=' << NUM[ v ] << '/' << L[ v ];

}

void GR:: Make(int G[ MaxV ][ MaxV ])

{ int ls = 0, f;

n = m = 0;

for (int i=0; i<MaxV; i++)

{ LIST[ i ] = 0;

G[ i ][ i ] = 0;

f = 0;

cout << ‘\n’ << Ch(i) << ": ";

for (int j = 0; j < MaxV; j++)

if(G[ i ][ j ])

{ f++;

Node *v = new Node;

v->d = j; v->next = LIST[ i ]; LIST[ i ] = v;

cout << Ch(j);

}

else cout << "-";

if(f) n++;

m += f;

if (!((++ls) % 10)) _getch();

}

cout << ‘\n’ << "| V |=" << n << " | E |=" << m/2;

}

void main()

{ int i, j, f, n = 0, G[ MaxV ][ MaxV ];

char s[ 80 ];

setlocale(LC_ALL, "Russian");

for (i = 0; i < MaxV; i++)

for (j = 0; j < MaxV; j++) G[ i ][ j ] = 0;

cout << ‘\n’ << "DBL test ============== (C)lgn, 10.10.03;14.01.13" <<

‘\n’ << " Введите списки смежности (строки букв a до z)..." << ‘\n’;

do{

cout << "v[" << Ch(n) << "]=";

cin >> s;

cout << ‘\n’ << "[" << s << "]" << strlen(s); _getch();

for (int i = 0; i < strlen(s); i++)

if (isalpha(s[ i ])){ j = tolower(s[ i ]) – 'a';

G[ n ][ j ] = G[ j ][ n ] = 1;

}

n++;

} while((strlen(s) > 0) && (n < MaxV));

//Преобразование строк в матрицу, затем – в списки смежности,

//подсчёт мощностей и контрольный вывод

GR Gr(MaxN);

Gr.Make(G);

//Тестирование функции DBL

Gr.DBL_Exec();

printf("\n ===== Конец =====\n");

_getch();

}