ДСо18-12-Графы (1238950)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций