Warning: session_start(): open(C:\Windows\temp\sess_2t0njq8kcbqloqraq6qomf3f31, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 15 Warning: session_commit(): open(C:\Windows\temp\sess_2t0njq8kcbqloqraq6qomf3f31, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 36 Warning: session_commit(): Failed to write session data (files). Please verify that the current setting of session.save_path is correct (C:\Windows\temp) in C:\www\lemma4.1php\login.php on line 36 Основы языка Си


Визуальное представление графа является очень наглядным и удобным для понимания.


Ассоциативная связь


Программно представлять граф можно различными способами. Рассмотрим представления в виде матрицы смежности, списка дуг и списка смежности.


Матрица смежности


Матрицей смежности ms графа G=(V, E) называется матрица размерности, равной числу вершин (порядку) графа и состоящая из 0 и 1. Элемент ms[i,j] равен 1, если (vi,vj) принадлежит E и 0 – в противном случае.


Для графа, изображенного на рисунке выше матрица смежности будет иметь вид:



0

1

2

3

4

5

6

7

8

9

0

0

1

1

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

1

0

0

2

0

0

0

1

1

0

0

0

0

0

3

0

0

0

0

0

0

0

0

0

0

4

0

0

0

0

0

1

0

0

0

0

5

0

0

0

0

0

0

0

0

0

0

6

0

0

0

0

0

0

0

0

1

0

7

0

0

0

0

1

0

1

0

0

0

8

0

0

0

0

0

0

0

0

0

1

9

0

0

0

0

0

0

0

0

0

0



Матрица смежности проста и удобна для работы с графом. На ее основе разрабонано множество эффективных алгоритмов.


Список дуг


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


0 1

0 2

1 7

2 3

2 4

4 5

6 8

7 4

7 6

8 9


Списки смежности


Как и в других задачах, использующих списки, представление графа в виде списков дуг позволяет работать с динамически изменяющейся информацией.


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


Ассоциативная связь


Если точно известно, что множество вершин не будет изменяться, то граф можно представлять одномерным массивом с числом элементов, равным числу вершин, где i-й элемент - есть указатель на список вершин, смежных с данной вершиной. Для рассматриваемого графа соответствующий массив списков смежности будут выглядеть следующим образом:


Ассоциативная связь

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


Приведем фрагмент программы, осуществляющей преобразование матрицы смежности в массив списков смежности


Ассоциативная связь: