Граф алгоритмдері

Лабораториялық жұмыс № 10 – 11

Граф алгоритмдері

График-сызықтармен байланысқан нүктелер жиынтығы. Нүктелер шыңдар немесе түйіндер, ал сызықтар қабырғалар немесе доғалар деп аталады.

Шыңның кіру дәрежесі - оған кіретін қабырғалар саны, шығу дәрежесі – шығатын қабырғалардың саны.

Шыңдардың барлық жұптары арасындағы қабырғалары бар график толық деп аталады.

Егер жиектің екі ұшы сәйкес келсе, яғни ол шыңнан шығып, оған енсе, онда мұндай жиек цикл деп аталады.

[pic 1]

Графтың түрлері:

Байланысқан                  [pic 2]

Байланыспаған             [pic 3]

Бағытталған                  [pic 4]

Бағытталмаған             [pic 5]

Графты ұсыну жолдары:

• көршілес матрица;
• оқиға матрицасы;
• көршілес (инциденттік)тізім;
• қабырғалар тізімі.

Графтың көршілес матрицасы - бұл әр элемент екі мәннің бірін алатын квадратты матрица: 0 немесе 1.

Көршілес матрица жолдарының саны бағандар санына тең және графтың шыңдарының санына сәйкес келеді.

• 0-қабырғаның болмауына сәйкес келеді,
• 1-қабырғаның болуына сәйкес келеді.

[pic 6]

Графтың оқиға матрицасы – бұл жолдар саны шыңдар санына, ал бағандар саны қабырға санына сәйкес келетін матрица.

Оқиға  матрицасында қабырғаларды нөмірлеуді қажет етеді, бұл әрқашан ыңғайлы емес.

[pic 7]

Көршілес (инциденттік)тізім – бұл жадыға қатысты көршілес матрицаларға қарағанда аз талап ететін тізім. Мұндай тізімді кесте түрінде ұсынуға болады, онда бағандар – 2, ал жолдар — бағандағы шыңдардан артық емес.

Бірінші бағандағы әр жолда шығыс шыңы, ал екінші бағанда ағымдағы шыңның қабырғалары кіретін шыңдардың тізімі көрсетілген.

[pic 8]

Қабырғалар тізімінде әр жолда екі іргелес шыңдар және оларды байланыстыратын қабырғаларының салмағы жазылады.

Қабырғалар тізіміндегі жолдар саны әрқашан бағдарланбаған қабырғалар екі еселенген санымен бағдарланған қабырғаларды қосу нәтижесінде алынған мәнге тең болуы керек.

[pic 9]

Листинг Граф құру

#include <iostream>

#include <list>

using namespace std;

class Graph {

private:

    int V;  // Количество вершин графа

    list<int> *adj;  // Указатель на массив списков смежности

public:

    Graph(int V) {

        this->V = V;

        adj = new list<int>[V];

    }

    void addEdge(int v, int w) {

        adj[v].push_back(w);  // Добавление ребра от вершины v к вершине w

    }

    void printGraph() {

        for (int v = 0; v < V; ++v) {

            cout << "Вершина " << v << ": ";

            for (auto it = adj[v].begin(); it != adj[v].end(); ++it) {

                cout << *it << " ";  // Вывод списка смежных вершин

            }

            cout << endl;

        }

    }

};

int main() {

    int V = 5;  // Количество вершин графа

    Graph g(V);  // Создание графа с V вершинами

    // Добавление ребер

    g.addEdge(0, 1);

    g.addEdge(0, 4);

    g.addEdge(1, 3);

    g.addEdge(1, 4);

    g.addEdge(2, 1);

    g.addEdge(3, 2);

    g.addEdge(3, 4);

    g.printGraph();  // Вывод графа

    return 0;

}

Ені бойынша іздеу алгоритмін қолдану(Дейкстр алгоритмі):

#include <iostream>

#include <queue>

#include <stack>

using namespace std;

struct Edge {

  int begin;

  int end;

};

int main()

{

  system("chcp 1251");

  system("cls");

  queue<int> Queue;