Въведение в Графи

Ориентирани и неориентирани графи и мултиграфи. Представяния на графи. Предимства и недостатъци на различните представяния. Анализ по сложността по време на алгоритмите върху графи - въвеждане на асимптотични нотации на функции на две променливи. Линейна сложност по време при графи.

Представяне на графи в паметта

Операция/Представяне Матрица на съседство Списък на наследниците Списък на ребрата Матрица на Инцидетност
Добавяне на ребро $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;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License