Курсовая работа: Разработка программ с использованием динамической памяти
- список смежности;
- список дуг (ребер);
- и др.
Список смежности – для вершины v есть список концов дуг, исходящих из вершины v, в случае орграфа, или список смежных с v вершин, в случае неориентированного графа.
Список дуг – это список, в котом каждой дуге ставится в соответствие пара <x,y> , где x – начало дуги, а y – ее конец. Для нагруженных графов – тройка <x,y,z> ,где x – начало дуги, y – конец дуги, z – вес дуги.
Матрица смежности – это квадратная матрица, строки и столбцы которой соответствуют вершинам графа. Элемент матрицы (i,j) равен 1, если вершина i связана с вершиной j ребром, иначе элемент матрицы равен 0.
Для неориентированных графов матрица смежности является симметричной относительно главной диагонали. Т.е. для получения информации о графе достаточно знать верхнюю или нижнюю треугольную матрицу смежности. Для ориентированных графов матрица смежности не является симметричной.
Матрица инцидентности – это матрица, строки которой – список вершин, а столбцы – список ребер. Элемент матрицы инциденций (i,j) равен 1, если вершина i инцидентна соответствующему ребру.
Для неориентированных графов:
Для ориентированных графов:
Например, дан граф G (см.рис. .1)
 |
Рисунок 2.1 – Граф G
Представление графа списком смежности отображено на рисунке 2.2
 |
??????? 2.2 ? ?????? ????????? ????? G
Представление графа с помощью списка дуг имеет вид отображено на рисунке .3
 |
Рисунок 2.3 – Список дуг графа G
Представление графа с помощью матрицы смежности показано в таблице 2.1
Таблица 2.1 – Матрица смежности
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x1 |
0 |
1 |
К-во Просмотров: 448
Бесплатно скачать Курсовая работа: Разработка программ с использованием динамической памяти
|