mafulechka
mafulechkaШілде 15, 2019, 3:37 Т.Ж.

Көршілестік матрицасы

Іршілестік матрицасы – G = {V, E} графигін логикалық матрица ретінде көрсету тәсілі.


Көршілес матрицаны бейнелеу

Матрицаның өлшемі VxV, мұнда V - графиктегі төбелер саны және Aij жазбасының мәні i төбесінен j шыңына дейін жиектің бар-жоғына байланысты 1 немесе 0.

Көршілестік матрицасының мысалы

Төмендегі суретте график және оның эквивалентті көршілестік матрицасы көрсетілген.

Бағытсыз график жағдайында матрица диагональ бойынша симметриялы болады, өйткені әрбір жиектің (i, j) шеті де (j, i) болады.

Көршілес матрицаның артықшылықтары

Жиекті қосу, жиекті алып тастау және i төбесінен j шыңына дейін жиекті тексеру сияқты негізгі операциялар уақытты өте тиімді пайдалану болып табылады. Тұрақты уақытпен орындалатын операциялар.

Егер график тығыз болса және жиектер саны көп болса, іргелес матрица бірінші таңдау болуы керек. График пен іргелес матрица сирек болса да, біз оны сирек матрицалық деректер құрылымдарының көмегімен көрсете аламыз.

Дегенмен, ең үлкен пайда матрицаларды пайдаланудан келеді. Аппараттық құралдардың соңғы жетістіктері графикалық өңдеу блогында (GPU) тіпті қымбат матрицалық операцияларды орындауға мүмкіндік береді.

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

Көршілестік матрицасының кемшіліктері

VxV іргелес матрицаның кеңістік талабына байланысты жады жеткіліксіз болуы мүмкін. Бірақ әдетте графиктердің тым көп байланыстары болмайды және бұл көршілес тізімдердің көптеген мәселелер үшін ең жақсы таңдау болуының басты себебі.

Негізгі операциялар қарапайым болғанымен, inEdges және outEdges сияқты операциялар іргелес матрицаны көрсетуді пайдалану кезінде қымбатқа түседі.

Көршілестік матрицалық коды

Егер сіз екі өлшемді массивтерді құруды білсеңіз, онда сіз іргелес матрицаны қалай құру керектігін де білесіз.

С++ тіліндегі көршілестік матрицасы

#include <iostream>
using namespace std;
class Graph {
private:
      bool** adjMatrix;
      int numVertices;
public:
      Graph(int numVertices) {
            this->numVertices = numVertices;
            adjMatrix = new bool*[numVertices];
            for (int i = 0; i < numVertices; i++) {
                  adjMatrix[i] = new bool[numVertices];
                  for (int j = 0; j < numVertices; j++)
                        adjMatrix[i][j] = false;
          }
    }

      void addEdge(int i, int j) {
                  adjMatrix[i][j] = true;
                  adjMatrix[j][i] = true;
    }

      void removeEdge(int i, int j) {
                  adjMatrix[i][j] = false;
                  adjMatrix[j][i] = false;
    }

      bool isEdge(int i, int j) {
                  return adjMatrix[i][j];
    }
    void toString() {
      for (int i = 0; i < numVertices; i++) {
                  cout << i << " : ";
                  for (int j = 0; j < numVertices; j++)
                        cout << adjMatrix[i][j] << " ";
                  cout << "\n";
      }
    }

    ~Graph() {
            for (int i = 0; i < numVertices; i++)
                  delete[] adjMatrix[i];
            delete[] adjMatrix;
    }
};
int main(){
        Graph g(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.toString();
        /* Outputs
           0: 0 1 1 0 
           1: 1 0 1 0 
           2: 1 1 0 1 
           3: 0 0 1 0 
          */
}

Java іргелестік матрицасы

public class Graph {
      private boolean adjMatrix[][];
      private int numVertices;

      public Graph(int numVertices) {
          this.numVertices = numVertices;
          adjMatrix = new boolean[numVertices][numVertices];
    }

      public void addEdge(int i, int j) {
                adjMatrix[i][j] = true;
                adjMatrix[j][i] = true;
    }

      public void removeEdge(int i, int j) {
                adjMatrix[i][j] = false;
                adjMatrix[j][i] = false;
    }

      public boolean isEdge(int i, int j) {
                  return adjMatrix[i][j];
    }
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < numVertices; i++) {
            s.append(i + ": ");
            for (boolean j : adjMatrix[i]) {
                s.append((j?1:0) + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }
    public static void main(String args[])
    {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);

        System.out.print(g.toString());
        /* Outputs
           0: 0 1 1 0 
           1: 1 0 1 0 
           2: 1 1 0 1 
           3: 0 0 1 0 
          */
    }
}

Python тіліндегі көршілестік матрицасы

class Graph(object):
    def __init__(self, size):
        self.adjMatrix = []
        for i in range(size):
            self.adjMatrix.append([0 for i in range(size)])
        self.size = size
    def addEdge(self, v1, v2):
        if v1 == v2:
            print("Same vertex %d and %d" % (v1, v2))
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1
    def removeEdge(self, v1, v2):
        if self.adjMatrix[v1][v2] == 0:
            print("No edge between %d and %d" % (v1, v2))
            return
        self.adjMatrix[v1][v2] = 0
        self.adjMatrix[v2][v1] = 0
    def containsEdge(self, v1, v2):
        return True if self.adjMatrix[v1][v2] > 0 else False
    def __len__(self):
        return self.size

    def toString(self):
        for row in self.adjMatrix:
            for val in row:
                print('{:4}'.format(val)),
            print

def main():
        g = Graph(5)
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);

        g.toString()

if __name__ == '__main__':
   main()
Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Ол саған ұнайды ма? Әлеуметтік желілерде бөлісіңіз!

Пікірлер

Тек рұқсаты бар пайдаланушылар ғана пікір қалдыра алады.
Кіріңіз немесе Тіркеліңіз
AD

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:50ұпай,
  • Бағалау ұпайлары-4
m
  • molni99
  • Қаз. 26, 2024, 9:07 Т.Ж.

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:80ұпай,
  • Бағалау ұпайлары4
m
  • molni99
  • Қаз. 26, 2024, 8:59 Т.Ж.

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:20ұпай,
  • Бағалау ұпайлары-10
Соңғы пікірлер
i
innorwallҚар. 14, 2024, 7:33 Т.Ж.
Qt тілінде ойын қалай жазылады - 3-сабақ. Басқа объектілермен әрекеттесу what is priligy tablets What happens during the LASIK surgery process
i
innorwallҚар. 14, 2024, 4:39 Т.Ж.
C++ файлдарының ішінде CMakeLists.txt ішінде жарияланған айнымалы мәндерді пайдалану where can i buy priligy online safely Tom Platz How about things like we read about in the magazines like roid rage and does that really
i
innorwallҚар. 12, 2024, 6:42 Т.Ж.
Django - Оқулық 055. Автоматты толтыру өрісі функциясын қалай жазу керек Freckles because of several brand names retin a, atralin buy generic priligy
i
innorwallҚар. 12, 2024, 2:53 Т.Ж.
QML - Сабақ 035. C++ қолданбай QML тілінде сандарды пайдалану priligy cvs 24 Together with antibiotics such as amphotericin B 10, griseofulvin 11 and streptomycin 12, chloramphenicol 9 is in the World Health Organisation s List of Essential Medici…
i
innorwallҚар. 12, 2024, 12:20 Т.Ж.
Qt/C++ - 052-сабақ. Qt аудио ойнатқышын AIMP стилінде теңшеу It decreases stress, supports hormone balance, and regulates and increases blood flow to the reproductive organs buy priligy online safe Promising data were reported in a PDX model re…
Енді форумда талқылаңыз
i
innorwallҚар. 14, 2024, 9:09 Т.Ж.
добавить qlineseries в функции Listen intently to what Jerry says about Conditional Acceptance because that s the bargaining chip in the song and dance you will have to engage in to protect yourself and your family from AMI S…
i
innorwallҚар. 11, 2024, 7:25 Т.Қ.
Всё ещё разбираюсь с кешем. priligy walgreens levitra dulcolax carbs The third ring was found to be made up of ultra relativistic electrons, which are also present in both the outer and inner rings
9
9AnonimҚаз. 25, 2024, 4:40 Т.Қ.
Машина тьюринга // Начальное состояние 0 0, ,<,1 // Переход в состояние 1 при пустом символе 0,0,>,0 // Остаемся в состоянии 0, двигаясь вправо при встрече 0 0,1,>…

Бізді әлеуметтік желілерде бақылаңыз