ДСо18-12-Графы (Лекции Северов Часть 3)

Carnegie MellonГрафыАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 12, 23 ноября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Основные понятияграф G = (V,E)V – множество вершин {A, B, C, D, …}Е – множество ребер {AB, BC, CD, …}¢ в полном графе любая пара вершин есть ребро¢ подграф G g=(v,e): v Í V и e Í EB¢ (не)направленость рёбер¢ число ненаправленных рёберполного графа с N вершинамиDравно N(N-1)/2¢AC2Основные понятияВзвешеный граф имеет вес каждогоребра¢ Путь PAC из A в C – последовательностьсвязанных рёбрами вершин графа¢ В простом пути различны все вершины¢ Связный граф имеет путь между любойпарой вершин¢ Цикл – путь, где конец совпадает сначалом¢ В простом цикле различны всевершины, кроме начала и конца¢ABDC3Структуры данных для представления графов¢Матрица смежностиA0ABCD¢B10C240D3560Список примыканийABBCDDCACADBDABC45Данные типа Graf#include <stdio.h>#include <stdarg.h>typedef int T;#include "SQL.h"void List_print(Link_List a) {Link_Item p = a->Front;while(p) { printf("%d ", Item_get_node(p)+1);p=Item_get_next(p); }}typedef struct Graf {Link_List S; int N; } *Link_Graf;6Методы типа GrafLink_Graf Graf_create(int n) { int i;Link_Graf p = (Link_Graf)calloc(1,sizeof(struct Graf));p->S = (Link_List)calloc(p->N=n,sizeof(struct List));for(i=0;i<n;i++) List_ini(&p->S[i]); p->N=n; return p; }void Graf_delete(Link_Graf *a) { free((*a)->S); free(*a);*a=NULL; }Link_List Graf_Get_node(Link_Graf a, T name) {return &a->S[name]; }void Graf_Set_node(Link_Graf a,T name,...) { T v;va_list p; va_start(p,name);while(v=va_arg(p,T)) List_Insert_back(&a->S[name-1],v-1);va_end(p); }void Graf_print(Link_Graf a) {int i;for(i=0;i<a->N;i++) { printf("%d: ",i+1);List_print(&a->S[i]); putchar('\n'); } }78Основная программаint main() {Link_Graf G = Graf_create(7), g = Graf_create(7);Graf_Set_node(G,1,2,4,0);Graf_Set_node(g,1,2,4,0);Graf_Set_node(G,2,1,5,7,0);Graf_Set_node(g,2,1,5,7,0);Graf_Set_node(G,3,4,6,7,0);Graf_Set_node(g,3,4,6,7,0);Graf_Set_node(G,4,1,3,5,0);Graf_Set_node(g,4,1,3,5,0);Graf_Set_node(G,5,2,4,6,7,0);Graf_Set_node(g,5,2,4,6,7,0);Graf_Set_node(G,6,3,5,0);Graf_Set_node(g,6,3,5,0);Graf_Set_node(G,7,2,3,5,0);Graf_Set_node(g,7,2,3,5,0);Graf_print(G);print_V(G,0); Graf_delete(&G); putchar('\n');print_G(g,0); Graf_delete(&g);1return 0;}324657910Алгоритмы обхода¢¢В глубинуВ ширинуAADBDBFECFEC11Обход в глубину (Си)void print_V(Link_Graf A, int k) {struct Stack Q; Stack_ini(&Q);int *a = (int*)calloc(A->N,sizeof(int));Stack_push(&Q,k); a[k]=1;while(!Stack_Is_Empty(&Q)) {while(!List_Is_Empty(Graf_Get_node(A,k))){T i=List_Remove_front(Graf_Get_node(A,k));if(!a[i]) { a[i]=1; Stack_push(&Q,i);printf("(%d,%d)\n",k+1,i+1); k=i;}}k=Stack_pop(&Q);}}12Обход в ширину (Си)void print_G(Link_Graf A, int k) {struct Queue Q; Queue_ini(&Q);int *a = (int*)calloc(A->N,sizeof(int));Queue_put(&Q,k); a[k]=1;while(!Queue_Is_Empty(&Q)) {k=Queue_get(&Q);while(!List_Is_Empty(Graf_Get_node(A,k))) {T i=List_Remove_front(Graf_Get_node(A,k));if(!a[i]) { Queue_put(&Q,i); a[i]=1;printf("(%d,%d)\n",k+1,i+1); }}}}1314132465715Описание шаблона типа Graphtemplate <typename T, int N> class Graph {List<T> S[N]; int B[N];public:Graph() { for(int i=0;i<N;i++) B[i]=0; }List<T>& operator()(int n) { return S[n]; }void operator()(int n,int m, T f, ...) {va_list pt; va_start(pt,f); T v=f;for(int i=0;i<m;i++) { S[n].push_back(v); v=va_arg(pt,T); }va_end(pt); }int& operator[](int n) { return B[n]; }friend ostream& operator<<(ostream& a, Graph<T,N> b) {for(int i=0;i<N;i++) a << i << ": " << b(i) << endl; return a;}};16Основная программаint main() {Graph<int,7> A;A(0,2,1,3); A(1,3,0,4,6); A(2,3,3,5,6); A(3,3,0,2,4);A(4,4,1,3,5,6); A(5,2,2,4); A(6,3,1,2,4);cout << A << endl;print_V(A,0); cout << endl;136Graph<int,7> B;B(0,2,1,3); B(1,3,0,4,6); B(2,3,3,5,6); B(3,3,0,2,4);B(4,4,1,3,5,6); B(5,2,2,4); B(6,3,1,2,4);print_G(B,0);return 0; }245717Обход в глубинуvoid print_V(Graph<int,7> A, int k) {Stack<int> Q; Q.push(k); A[k]++;while(!Q.empty()) {while(!A(k).empty()) {int i=A(k).pop_front();if(!A[i]) { A[i]++; Q.push(i);cout << '(' << k+1 << ',' << i+1 << ")\n"; k=i;}}k=Q.pop(); } // end while}18Обход в ширинуvoid print_G(Graph<int,7> A, int k) {Queue<int> Q; Q.put(k); A[k]++;while(!Q.empty()) {k=Q.get();while(!A(k).empty()) {int i=A(k).pop_front();if(!A[i]) { Q.put(i); A[i]++;cout << '(' << k+1 << ',' << i+1 << ")\n"; }}} // end while}192021Построение Минимального Остового ДереваОстовое дерево графа§ подграф из всех вершин и части рёбер§ связный§ ациклический¢ МОД взвешенного графа§ остовое дерево§ минимального суммарного веса¢ Трудоемкость полного перебора О(exp(N))¢ Жадный алгоритм¢§ на каждом шаге по части данных выберем лучший следующий23Алгоритм Прима роста МОДV = M È M’ È RM – уже найденные вершины МОД (дерево)M’ – вершины, смежные с вершинами М (кайма)R = V\M\M’ – остальные вершины графаУкоренить дерево (выбрать корень)¢ Окаймить корень¢ Пока кайма не опустеет¢§ Выбирать между деревом и каймой легчайшее ребро§ Дополнять дерево найденным ребром§ Уточнять кайму: вершины и рёбраотнесение к дереву – на диагонали матрицы смежности24Задание матрицей смежности#include <iostream>using namespace std;int N=7, B[7][7], A[7][7]={{0,2,4,7,0,5,0},{0,0,0,6,3,0,8},{0,0,0,0,0,6,0},{0,0,0,0,0,1,6},{0,0,0,0,0,0,7},{0,0,0,0,0,0,6},4{0,0,0,0,0,0,0}};A 2C5716F 66D6B8G3E725Вспомогательные функцииint r() { // дерево растёт ?for(int i=0;i<N;i++)if(!A[i][i]) return 1;return 0; }void min(int& n,int& m) { // Легчайшее в каймеint min=0;for(int i=0;i<N;i++) for(int j=0;j<N;j++)if(!B[i][j]) continue;else if((!min || B[i][j]<min) && !A[j][j])min=B[n=i][m=j];}26Растим деревоvoid mst(int k) { // Растить МОД от корняint i,j,m,n;for(n=0;n<N;n++) for(m=0;m<N;m++) { B[n][m]=0;if(n==m) A[n][n]=0;else if (n>m) A[n][m]=A[m][n]; }A[k][k]=1; // укоренить деревоfor(m=0;m<N;m++)B[k][m]=A[k][m]; // окаймить кореньwhile( r() ) { // пока дерево растётmin(n,k); // найти легчайшееA[k][k]=1; // внести конец в деревоcout << char('A'+n) << char('A'+k) << endl;27Уточняем каймуfor(m=0;m<N;m++)// новые ребра в каймуB[k][m]=!A[m][m]?A[k][m]:0;// каждое ребро в кайме если...for(m=0;m<N;m++) for(k=n=0;n<N;n++) if(B[n][m])if(!k) // первое?k=B[i=n][j=m]; // взять легчайшимelse if(B[n][m]>k) // тяжелее?B[n][m]=0; // убрать из каймыelse {B[i][j]=0;k=B[i=n][j=m];} // взять легчайшим// рёбра в кайме пересчитаны}// дерево выросло в МОД}int main() { mst(0); return 0; }28Результат4A75C666638D1FB2GE729Поиск кратчайших путей¢ищем не легчайшее, а элемент кратчайшего пути4A75C66D1FB2E8663G730Алгоритм ДейкстрыV = M È M’ È RM – уже найденные вершины карты (дерево)M’ – вершины смежные с вершинами М (кайма)R = V\M\M’ – остальные вершины графа¢Начать карту§ выбрать начальную вершину дерева¢¢Окаймить началоПока нет конца§ Найти в кайме ближайшую к начальной§ Дополнить карту§ Уточнить кайму: вершины и рёбрарасстояние до начала – на диагонали матрицы смежности31Вспомогательные функцииint r() { // дерево растёт ?for(int i=0;i<N;i++)if(!A[i][i]) return 1;return 0; }int min() { int r,min=0; // ближайшаяfor(int i=0;i<N;i++) if(!B[i][i]) continue;else if((!min || B[i][i]<min) && !A[i][i])min=B[r=i][i];return r;}void print_B() { cout << endl; // вывод каймыfor(int n=0;n<N;n++) { cout << char('A'+n) <<":\t";for(int m=0;m<N;m++) cout << (n==m?0:B[n][m]) << ' ';cout << '\t' << B[n][n] << endl; }}32Основная программа – 1int main() {int d,n,m,k=0;for(n=0;n<N;n++) for(m=0;m<N;m++) { B[n][m]=0;if(n>m) A[n][m]=A[m][n]; }for(m=0;m<N;m++) B[m][m]=B[k][m]=A[k][m];A[k][k]=1; // начать картуwhile( r() ) { // пока дерево растётk=min(); // найти ближайшуюA[k][k]=1; // внести в деревоfor(m=0;m<N;m++) //найти связи// себя, несвязанные, пройденные - пропуститьif(k==m || !A[k][m] || A[m][m]) continue;33Основная программа – 2else { d=B[k][k]+A[k][m]; // расстояние доначала// для новой - запомнить расстояние и реброif(!B[m][m]) { B[m][m]=d; B[k][m]=A[k][m]; }// для расстояния длиннее - ребро не добавлятьelse if(B[m][m]<=d) B[k][m]=0;// иначе - запомнить расстояние и реброelse { B[m][m]=d; B[k][m]=A[k][m];for(n=0;n<N;n++) // удалить старую связьif(n!=m && n!=k && B[n][m])B[n][m]=0; }} // расстояние учтено} // дерево выросло в карту кратчайших путейprint_B(); return 0;}34Результат4CA2B5D8F1G3E35ЦиклыЦикл – путь, где конец совпадает сначалом¢ В простом цикле различны всевершины, кроме начала и конца¢ Гамильтонов цикл прост исодержит все вершины графа¢ Эйлеров граф содержит цикл,проходящий через каждое ребрографа ровно один раз¢DBAC36Задача коммивояжера – найтигамильтонов циклAGBCDEFG1612136711A21188195B201315C14104D27E9FBFCED37Алгоритм поиска пути¢Пока не найден полный цикл§ Добавлять в путь ребро..1.2.3.легчайшеене третье при любой вершине путине образующее неполного циклаколичество рёбер пути при вершине – надиагонали матрицы смежности38Задача коммивояжераAGBCDEFG1612136711A21188195B201315C14104D27E9FBFCED39Задача коммивояжераAGBCDEFG1612136711A21188195B201315C14104D27E9FBFCEDДлина найденного пути- 5340Задание матрицы смежности#include <iostream>using namespace std;int N=7, int B[7][7], A[7][7]={{0,16,12,13,6,7,11},{0, 0,21,18,8,19,5},{0, 0, 0,20,1,3,15},BC{0, 0, 0,0,14,10,4},16 1221{0, 0, 0,0, 0, 2,7},{0, 0, 0,0, 0, 0,9},{0, 0, 0,0, 0, 0,0}};DEFG136711A188195B201315C14104D27E9F41Проверка на возникновение циклаint r() { for(int i=0;i<N;i++) if(A[i][i]!=2) return 1; return 0; }jjint loop(int i, int j) { int nxt,prd=i;i=prdif(A[i][i]<2 || A[j][j]<2) return 0;do {i’for(nxt=0;nxt<N;nxt++)if(nxt==prd) continue; else if(B[i][nxt]) break;prd=i; i=nxt; } while(A[nxt][nxt]==2 && i!=j);if(i==j) if( !r() ) return 0; else return 1; else return 0;}nxt42Выбор следующего ребраvoid min(int& i,int& j) {int n,m,k=0;while(!k) {for(m=1;m<N;m++) for(n=0;n<m;n++)if(A[n][m]>0 && (!k || A[n][m]<k) &&A[n][n]<2 && A[m][m]<2) k=A[i=n][j=m];A[i][i]++; A[j][j]++;if(loop(i,j)) { A[i][i]--; A[j][j]--; A[i][j]=k=0; }else { B[i][j]=B[j][i]=A[i][j]; A[i][j]=0; }}}43Основная программаvoid print_B() { int s=0; cout << endl;for(int n=0;n<N;n++) { cout << char('A'+n) <<":\t";for(int m=0;m<N;m++) { s+=B[n][m]; cout << B[n][m] << ' '; }cout << endl; }cout << "Length= " << s/2 << endl;}int main() { int n,m;for(n=0;n<N;n++) for(m=0;m<N;m++) B[n][m]=0;while( r() ) min(n,m);print_B();return 0;}44Матрица примыкания:C(u,w) ≤ C(u,v) + C(v,w)BAC#include <iostream>#include “SQL.h“const int N=7; using namespace std;int B[N][N],A[N][N]={{0,16,12,13,6,7,11},{0,0,21,18,8,19,5},{0,0,0,20,1,3,15},{0,0,0,0,14,10,4},{0,0,0,0, 0, 2,17},{0,0,0,0, 0, 0, 9}};GFDE45Обход МОДDBEGACF46Построение МОД и гамильтонова цикла на егоосновеvoid gloop(int k,Queue<int>& a) { a.put(k);for(int m=0;m<N;m++) if(B[k][m]) gloop(m,a); }void main() { int k,m,i=0;Queue<int> a;mst(3); gloop(3,a); k=a.get(); a.put(k);cout << char('A'+k);while(!a.empty()) { m=a.get(); i+=A[k][m]; k=m;cout << "-->" << char('A'+k); }cout << "\nlen= " << i << endl; }47Гамильтонов циклBCDEFG1612136711A21188195B201315C14104D27E9FDàGàBàEàAàCàFàDДлина найденногопути – 48Длина оптимальногопути – 41BACGDFE48Гамильтонов циклBCDEFG1612136711A21188195B201315C14104D27E9FDàGàBàEàAàCàFàDДлина найденногопути – 48Длина оптимальногопути – 41DàGàBàEàCàFàAàDBACGDFE49Литература:Р.Седжвик «Алгоритмы на С++» -М.:«И.Д.

Вильямс», 2011. ISBN 978-5-8459-1650-1¢ Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн«Алгоритмы: построение и анализ» -М.:«И.Д. Вильямс», 2015. ISBN 5-8459-0857-4¢ Н.Вирт «Алгоритмы и структуры данных»-СПб.: Невский Диалект, 2001.ISBN 5-7940-0065-1¢50.