Дипломная работа: Разработка программ с использованием динамической памяти

Основные способы представления (задания) графов:

1) перечисление множеств V (вершин) и E (ребер), задающих граф. G = (V, E);

2) матричные способы описания;

Пусть G = (V, E), |V| = p, а |E| = q, тогда:

a) матрица смежности – квадратная матрица , где

b) матрица инцидентности – прямоугольная матрица .

3) список дуг:

Пример: задан граф G = (V, E), где V = {v1, v2, v3, v4}, E = {v1v2, v2,v3, v1v3, v1v4, v3,v4} = {e1, e2, e3, e4, e5}. Рисунок 3.1.

v2

v1

v3

v4

Рисунок 3.1. – Пример построения графа

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

head: NULL

Рисунок 3.2. – Пример связности ребер графа

3.2. Операции над графами

При связанном хранении каждая вершина графа представляет собой структуру graf, состоящую из двух элементов: v1,v2 - предназначены для хранения вершин графа, next - для указателя на структуру, содержащую следующую вершину графа. На первые элементы графа указывает указатель head. Для всех операций над графом используется описание:

typedef struct graf

{ int v1,v2;

struct graf* next;

} Graf;

Graf *g, *head, *temp;

Для реализации операций могут использоваться следующие фрагменты программ:

1) определить первый элемент в линейном списке (рисунок 3.1):

printf("v1=");

scanf("%d",&head->v1);

head->next=0;

NULL