Алгоритмы поиска в графе. Поиск в глубину и в ширину. Классификация рёбер

Ребра при поиске в глубину делятся  на древесные ребра (Tree edges), обратные  ребра (Back edges), прямые дуги (Forwarg edges) и перекрестные дуги (Cross edges).

Древесные ребра (T) - ребра подграфа предшествования.

Обратные ребра (B) - ребра (u, v), соединяющие вершину u с ее предком v в дереве поиска в глубину.

Прямые дуги (F) - соединяют вершину u с ее потомком, но не входят в дерево поиска в глубину.

Перекрестные дуги  (C) - все остальные ребра графа. Они могут соединять две вершины одного дерева поиска в глубину, если ни одна из этих вершин не является предком другой, или вершины разных поддеревьев.

Понятия прямых и перекрестных дуги применимо только для ориентированных  графов

ПРОГРАММА

# include <iostream.h>

# include <conio.h>

#include <mem.h>

# include <stdio.h>

#include<alloc.h>

#include<process.h>

int MI[100][100], MS[100][100],color[100], parent[100],n,m,k,start;

struct Data

{

int data[1000];

virtual void Push(int x) {}

virtual void Del() {}

virtual int Top(){}

virtual int isEmpty() {}

};

struct Query: Data

{

unsigned char q1, q2;

Query() {q1=q2=0;}

virtual void Push(int x){data[q2++]=x;}

virtual void Del() {q1++;}

virtual int Top() {return data[q1];}

virtual int isEmpty() {return q1==q2;}

};

struct Stack: Data

{

unsigned char t;

Stack()   {t=0;}

virtual void Push(int x){data[t++]=x;}

virtual void Del() {--t;}

virtual int Top() {return data[t-1];}

virtual int isEmpty() {return !t;}

};

struct node{

int v;

node *next;

node(int x, node * t){v=x;next=t; }

};

typedef node *lnk;

lnk adj[100];

void Visit(int u){

Data* Ptr;

if (k)  Ptr = new Stack;

else Ptr = new Query;

Ptr->Push(u);

printf("%d ",u+1);

  parent[u]=-1;

color[u]=1;

do

{

int v;

u = Ptr->Top();

lnk tmp = adj[u];

while(tmp){

v =tmp->v;

if(color[v]==0)

break;

tmp=tmp->next;

}

if(tmp){

color[v]=1;

parent[v]=u;

Ptr->Push(v);

printf("%d ",v+1);

}

else

Ptr->Del();

} while (!Ptr->isEmpty());

delete Ptr;

}

void Iterative()

{

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

if(color[u]==0)

Visit(u);

}

void FMI()

{

    printf("Matritsa Intsidentnosti\n");

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

printf("Vvedite %d  stroku\n", i+1);

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

scanf("%d",&MI[i][j]);

    }

}

void FMS()

{

    printf("Matritsa Smejnosti\n");

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

printf("Vvedite %d stroku\n",i+1);

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

scanf("%d",&MS[i][j]);

    }

}

void FSS()

{

    int tmp;

printf("Spisok Smejnosti\n");

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

printf("Vvedite vershinu sviazanuiu s %d\n",i+1);

    printf( "%d: ",i+1);

scanf("%d",&tmp);

while(tmp){

adj[i]=new node(tmp-1,adj[i]);

    scanf("%d",&tmp);

    }

   }

}

void FMSvSS()

{

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

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

if(MS[i][j])

adj[i]=new node(j,adj[i]);

}

void FSSvMI()

{

    int m=0;

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

lnk tmp=adj[i];

        while(tmp){

MI[m][i]=-1;

   MI[m++][tmp->v]=1;

               tmp=tmp->next;

        }

}

}

void FMIvMS()

{

    int i,j,k,l;

for (i=0;i<m;i++){

        for (j=0;j<n;j++){

            if(MI[i][j]==-1) k=j;

            if(MI[i][j]==1) l=j;

        }

        MS[k][l]=1;

    }

}

void printm()

{

    printf("Matritsa Intsidentnosti\n");

    for(int i=0;i<m;i++){

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

printf("%2d ",MI[i][j]);

                    printf("\n");

    }

    printf("Matritsa Smejnosti\n");

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

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

                    printf("%2d ",MS[i][j]);

    printf("\n");

    }

printf("\nSpisok Smejnosti\n");

for(i=1;i<=n;i++){

printf("%d : ",i);

lnk tmp=adj[i-1];

while(tmp){

   printf("%d ",tmp->v+1);

   tmp=tmp->next;

}

printf("0\n");

}

}

int is_preced(int u,int v)

{

  int tmp=v;

  while(tmp!=u && tmp!=-1)

tmp=parent[tmp];

  return tmp==u;

}

main()

{

clrscr();

printf("Vvedi kolicestvo vershin i dug\n");

scanf("%d%d",&n,&m);

printf("Sposob vvoda\n1.Matritsa Intsidentnosti\n2.Matritsa Smejnosti\n3.Spisok Smejnosti\n");

scanf("%d",&k);

switch(k){

case 1: FMI() ;  FMIvMS(); FMSvSS(); break;

case 2: FMS(); FMSvSS(); FSSvMI(); break;

case 3: FSS(); FSSvMI(); FMIvMS(); break;

}

printm();

metka:printf("Vvedite DFS - 1  BFS - 0  END -2\ni startovuiu vershinu\n");

scanf("%d",&k);

if(k==2) exit(0);

scanf("%d",&start);

printf("\nOtvet ");

Visit(--start);

Iterative();

printf("\nKlassifikatsiea   reober\n");

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

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

                    if(MS[i][j]){

                                  if(parent[j]==i)

  printf("%d->%d ! TREE\n",i+1,j+1);

else if(is_preced(i,j))

  printf("%d->%d ! FORWARD\n",i+1,j+1);

else if (is_preced(j,i))

  printf("%d->%d ! BACK\n",i+1,j+1);

else

  printf("%d->%d ! CROSS\n",i+1,j+1);

                    }

memset(color,0,100);

goto metka;

}