Въведение в Графи
Ориентирани и неориентирани графи и мултиграфи. Представяния на графи. Предимства и недостатъци на различните представяния. Анализ по сложността по време на алгоритмите върху графи - въвеждане на асимптотични нотации на функции на две променливи. Линейна сложност по време при графи.
Представяне на графи в паметта
Операция/Представяне | Матрица на съседство | Списък на наследниците | Списък на ребрата | Матрица на Инцидетност |
---|---|---|---|---|
Добавяне на ребро | $O(1)$ | $O(logN)$ | $O(logM)$ | cell-content |
Изтриване на ребро | $O(1)$ | $O(logN)$ | $O(logM)$ | cell-content |
Проверка за съществуване на ребро | $O(1)$ | $O(logN)$ | $O(logM)$ | cell-content |
Намиране на наследниците на връх | $O(n)$ | $O(Di)$ | $O(n + logM)$ | cell-content |
Проверка за свързаност на два върха с път | $O(n^2)$ | $O(n+m)$ | $O(n*logM)$ | cell-content |
Необходима памет | $O(n^2)$ | $O(m)$ | $O(m)$ | cell-content |
Матрица на съседство
Това представяне позволява графът да се пази като матрица с размери NxN, където N е броят на върховете.
Свойствата на това представяне:
- За неориентирани графи, ребро между връх i и връх j се представя като A[i][j] = 1; A[j][i] = 1;
- За ориентирани графи е достатъчно само едната посока (в зависимост от ориентацията)
- Ако имаме тежест на ребрата, тя лесно може да се запише в матрицата (вместо 1 се записва съответната стойност)
Една малка програмата, която показва основните операции с Матрица на Съседство
#include <stdio.h> #define V 10 int A[V][V]; // 9 vertexes starting from position 1 void addUnorientedEdge(int from, int to) { A[from][to] = 1; A[to][from] = 1; } int main() { // init all cells with 0 for(int i = 0; i < V; ++i ) { for(int j = 0; j < V; ++j) { A[i][j] = 0; } } // hard-code a graph addUnorientedEdge(1,2); addUnorientedEdge(1,4); addUnorientedEdge(2,3); addUnorientedEdge(2,5); addUnorientedEdge(4,5); addUnorientedEdge(4,7); addUnorientedEdge(5,6); addUnorientedEdge(5,8); addUnorientedEdge(5,9); // check if there is an edge between to vetexes /* if(A[i][j] == 1) { // there is an edge } else { // there is no edge between these two vertexes } */ // go through all neighbours of a vertex int N = 1; for(int i = 0; i < V; ++i) { if(A[n][i] != 0) { // neighbour } } // print the matrix for(int i = 0; i < V; ++i) { for(int j = 0; j < V; ++j) { printf("%d ", A[i][j]); } printf("%s", "\n"); } return 0; }
page revision: 8, last edited: 03 Jun 2011 19:35