Комбинаторные алгоритмы для программистов



             

Программa


Программа 1. Обход бинарного дерева в глубину

//Обход ориентированных графов - поиск в глубину - //обобщение обхода дерева в прямом порядке #include <stdio.h> #include <string.h> #include <conio.h> #include <stdlib.h>

int matr_sm[50][50]; int mark[50]; int n;

void vvod () {int v1,v2; printf("Введите кол-во вершин в графе: "); do { scanf("%d",&n); if (n>51) printf("Ошибка!! Введите кол-во вершин в графе: "); } while (n>51);

for (int i=0;i <50;i++) for (int j=0;j <50;j++) matr_sm[i][j]=0;

printf("\nВведите связанные вершины : \n"); do { scanf("%d ",&v1); if (v1>n) //исходящая вершина { printf("ОШИБКА ВВОДА !!!!!!!!!"); abort(); } if (v1==0){break;} // конец ввода scanf(" %d ",&v2); if (v2>n) // входящая вершина { printf("ОШИБКА ВВОДА !!!!!!!!!"); abort(); } if (v2==0){break;} //конец ввода matr_sm[v2-1][v1-1]=1; } while(1); }

void vivod() { for (int j=0;j <n;j++) { for (int i=0;i<n;i++) printf("%d ",matr_sm[j][i]); printf("\n"); } }

void dfs(int v) { int w; mark[v]=1; //посетили printf("%i ",v+1); //и выдали на экран for (w=0;w<n;w++) if (matr_sm[v][w]==1); else if (mark[w]==0) dfs(w); }

void main() { clrscr(); vvod(); // printf("\n"); printf("МАТРИЦА СМЕЖНОСТИ\n"); // vivod();

printf("\n РЕЗУЛЬТАТ ПОИСКА В ГЛУБИНУ \n"); for (int v=0;v<50;v++) mark[v]=0; for (v=0;v<n;v++) //если вершина не посещалась, то посетить if (mark[v]==0) dfs(v);

getch(); }




Содержание  Назад