Граф (1238814)

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

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

Семинар 7 Графы

Граф G - это совокупность узлов V (вершин) и соединяющих их ребер E (дуг); G = (V,E).

Граф называется ориентированным графом (орграфом), если дуги имеют направление.

Цепь – последовательность ребер, соединяющих две вершины u и v. В направленном графе это «путь» . Циклом называется цепь из какой-нибудь вершины v в нее саму. Дерево это граф без циклов.

Граф связный, если есть цепь между любой парой вершин. Если не связный граф можно разбить на k связных компонент – он называется k-связным.

Взвешенные графы или сеть, в которых каждое ребро имеет вес.

Полный граф, в котором проведены все возможные ребра (для n вершин таких ребер n(n-1)/2).

Матрица смежности A[i,j] графа с N вершинами – это матрица размером NхN, где каждый элемент с индексами (i,j) является логическим значением (1или 0) и показывает, есть ли дуга из вершины i в вершину j или нет. Для неориентированного графа она симметрична, Для ориентированного асимметрична.

а) неориентированный граф и его матрица смежности б) ориентированный граф и его матрица смежности

Весовая матрица D[i,j] графа с N вершинами – это матрица размером N на N, где каждый элемент с индексами (i,j) равен «весу» ребра из вершины i в вершину j.

а) неориентированный граф и его весовая матрица б) ориентированный граф и его весовая матрица

Задача Прима-Краскала

Дано n городов с известными координатами. Нужно соединить все города телефонной сетью так, чтобы длина телефонных линий была минимальная и двигаясь по проводам можно добраться из любог города в любой другой.

Формулировка графа

Дан связный неориентированный граф G = (V,E) с n вершинами; длины ребер заданы матрицей {d_ij}, i,j=1..n. Найти множество ребер Т, соединяющий все вершины графа (он называется остовным деревом) и имеющий минимальную длину

Алгоритм (жадный)

1. Покрасить все вершины в разные цвета.

2. Сделать n-1 раз в цикле l выбрать ребро (i,j) минимальной длины, соединяющее вершины разного цвета; l запомнить его в массиве ребер; l перекрасить все вершины, имеющие цвет j, в цвет i.

3. Вывести результат.

Код.

struct rebro { int i, j; }; // ребро соединяет вершины i и j

const int N = 5;

void main()

{

int D[N][N], Col[N], i, j, k, Dmin, jMin, iMin, col_j;

rebro Reb[N-1];

// здесь надо ввести матрицу D

for ( i = 0; i < N; i ++ ) // покрасить все вершины

Col[i] = i; // в разные цвета

for ( k = 0; k < N-1; k ++ ) {

Dmin = 30000;

for ( i = 0; i < N-1; i ++ )

for ( j = i+1; j < N; j ++ )

if ( Col[i] != Col[j] && // ищем самое короткое ребро,

D[i][j] < Dmin ) { // не образующее цикла

Dmin = D[i][j];

iMin = i;

jMin = j;

}

Reb[k].i = iMin; // запомнить найденное ребро

Reb[k].j = jMin;

col_j = Col[jMin];

for ( i = 0; i < N; i ++ ) // перекрасить все вершины, цвет

if ( Col[i] == col_j ) // которых совпал с цветом

Col[i] = Col[iMin]; // вершины jMin

}

// здесь надо вывести найденные ребра }

}

Дополнительно можно рассчитывать общую длину выбранных ребер – минимальный путь.

2. Минимаксная задача размещения

Имеется n населенных пунктов, в одном из которых надо разместить медпункт скорой помощи. Надо расположить его так, чтобы самый дальний объект достигался за минимальное время. Допускается размещать объект на ребрах сети (между вершинами графа).

Алгоритм

Для каждого ребра (i,j) с нижней оценкой, меньше уже полученной, сделать следующие операции:

1. Найти самую дальнюю вершину k из всех тех вершин, в которые надо ехать через вершину i (то есть d_ik > d_jk) ;

2. найти самую дальнюю вершину l из всех тех вершин, в которые надо ехать через вершину j (то есть d_il < d_jl) ;

3. вычислить середину расстояния между вершинами k и l; если она попадает на ребро (i,j) и расстояние до самых дальних вершин меньше уже найденного, запомнить это место

Код алгоритма

minDist = 32767; // большое число

for (i = 0; i < N-1; i ++ ) for (j = i+1; j < N; j ++ ) { // перебрать все ребра (i,j)

maxDi = maxDj = 0;

for (k = 0; k < N; k ++ ) { // перебрать все вершины

if ( k == i || k == j ) continue;

if (D[j,k] < D[i,k])

if (D[j,k] < maxDj) maxDj = D[j,k];

else

if (D[j,k] < maxDj) maxDj = D[j,k];

}

dist = (maxDi + D[i][j] + maxDj) / 2;

if (dist < minDist && dist > maxDi && dist < maxDi+D[i][j] ) {

minDist = dist; // запомнить новый вариант

...

}

}

Задача коммивояжера

Имеется n городов соединенных дорогами. Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу в неизвестном порядке города 2,3,...n, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Если надо только вычислить кратчайшие расстояния между всеми вершинами, но не требуется знать сами кратчайшие маршруты, можно использовать весьма элегантный и простой алгоритм Флойда-Уоршелла:

Алгоритм Флойда-Уоршелла. Версия с запоминанием маршрута

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

for ( j = 0; j < N; j ++ )

c[i][j] = i;

...

for ( k = 0; k < N; k ++ )

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

for ( j = 0; j < N; j ++ )

if ( W[i][j] > W[i][k] + W[k][j] )

{

W[i][j] = W[i][k] + W[k][j];

c[i][j] = c[k][j];

}

Поиск «в ширину». Дерево предшественников

typedef enum{WHITE,GREY,BLACK} colors_t;

const int INFTY = 0x7fffffff; // = 2³¹ - 1

typedef struct {

int V,E ; // V – число вершин, Е – число ребер графа

int **adj; // adj[u] – массив вершин, смежных u

int *ne; // ne[u] – размер массив вершин adj[u], смежных u

int *pi; // pi[u] –вершина, предыдущая u, из которой попали в u

int *color; // color[u] – цвет вершины u

int *d; // d[u] – длина кратчайшего пути до вершины u

}

/*Здесь должны быть описаны функции для работы с очередью:*/

// queue_t *new_queue(int n) – создать очередь с максимальным размером n

// void delete_queue(queue_t *q) – удалить очередь q

// int dequeue(queue_t *q, int *p) – извлечь идентификатор вершины из очереди и поместить в адрес *p

// int enqueue(queue_t *q, int x) – Поместить x в очередь q

/* Здесь надо вставить функцию main(), где определить граф g */

// Функция обхода «в ширину» bfs(graf_t *g, int s): s – идентификатор вершины начала обхода

void bfs(graf_t *g, int s) {

int i, u, v;

for (I = 0; i < g―>V;i++) {

g―>color[i] = WHITE;

g―>d[i] = INFTY;

g―> pi[i] = -1;

}

queue_t *q = new_queue(g―>V) ;

enqueue(queue_t *q, int s);

g―>d[s] = 0;

g―>color[s] = GREY

while(dequeue(queue_t *q, &u)) {

for (i = 0 ; i < g―>ne[u]; i++) {

v = adj[u][i];

if(g―>color[v] == WHITE) {

g―> pi[v] = u;

g―>d[v] = g―>d[u] + 1;

g―>color[v] = GREY;

enqueue(queue_t *q, int v);

}

}

g―>color[v] = BLACK;

}

void delete_queue(queue_t *q)

}

Обход графа в глубину (топологическая сортировка)

typedef enum{WHITE,GREY,BLACK} colors_t;

typedef struct {

int V,E ; // V – число вершин, Е – число ребер графа

int **adj; // adj[u] – массив вершин, смежных u

int *ne; // ne[u] – размер массив вершин adj[u], смежных u

int *color; // color[u] – цвет вершины u

}

/* Здесь надо вставить функцию main(), где определить граф g */

// Функция обхода «в глубину» dfs_visit(v) выводит все вершины графа, пройденные перед вершиной v, // затем саму вершину

void dfs_visit(v) {

int i;

color[v] = GREY;

for (i = 0; i < ne[v]; i++) {

int u = adj[v][i];

if(color[u] == 0) {

dfs_visit(u);

}

}

printf(« %d »,v) ;

color[v] = BLACK;

}

void tsort() {

int v ;while(dequeue(queue_t *q, &u)) {

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

color[v] == WHITE;

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

if(color[v] == WHITE);

dfs_visit(u);

}

Спецификация класса Graph

ОБЪЯВЛЕНИЕ

const int MaxGraphSize =25;

template <class T>

class Graph

{

private:

// основные данные включают список вершин, матрицу смежности и размер (число вершин) графа

SeqList<T> vertexList;

int edge [MaxGraphSize];

int graphsize;

// методы для поиска вершины и указания ее позиции в списке

int FindVertex(SeqList<T> &L, const T& vertex);

int GetVertexPos(const T& vertex);

public:

// конструктор

Graph(void);

// методы тестирования графа

int GraphEmpty(void) const;

int GraphFull(void) const;

// методы обработки данных

int NumberOfVertices(void) const;

int NumberOfEdges(void) const;

int GetWeight(const T& vertexl, const T& vertex2);

SeqList<T>& GetNeighbors(const T& vertex);

// методы модификации графа

void InsertVertex(const T& vertex);

void InsertEdge(const T& vertexl, const T& vertex2, int weight);

void DeleteVertex(const T& vertex);

void DeleteEdge(const T& vertexl, const T& vertex2);

// утилиты

void ReadGraph(char *filename);

int MinimumPath(const T& sVertex, const T& sVertex);

SeqList<T>& DepthFirstSearch(const T& beginVertex);

SeqList<T>& BreadthFirstSearch(const T& beginVertex);

// итератор для обхода вершин

friend class VertexIterator<T>;

};

Реализация класса Graph

Конструктор класса Graph "отвечает" за инициализацию матрицы смежности размера MaxGraphSize x MaxGraphSize и обнуление переменной graphsize. Конструктором обнуляется каждый элемент матрицы для указания на отсутствие ребер.

// конструктор, обнуляет матрицу смежности и переменную graphsize

template <class T>

Graph<T>::Graph(void)

{

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

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

edgefi][j] - 0;

graphsize = 0;

}

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов семинаров