Как создать неориентированный граф из матрицы смежности?

Question

Здравствуйте, везде есть объяснения по рисункам в горячем виде для создания графика из прил. матрица. Тем не менее, мне нужен простой псевдокод или алгоритм для этого .... Я знаю, как нарисовать его из adj. Матрица и не знаю, почему никто не объясняет, как на самом деле поместить его в код. Я не имею в виду реальный код, но, по крайней мере, алгоритм ... Многие говорят .. 1, если есть преимущество, я знаю это ... Я создал прил. матрица и не знаю, как перенести его на график. Мои вершины не имеют имен, они просто индексы матрицы. например, 1-9 - это «имена моей матрицы»

  1 2 3 4 5 6 7 8 9
1 0 1 0 0 1 0 0 0 0
2 1 0 1 0 0 0 0 0 0
3 0 1 0 1 0 0 0 0 0
4 0 0 1 0 0 1 0 0 0
5 1 0 0 0 0 0 1 0 0
6 0 0 0 1 0 0 0 0 1
7 0 0 0 0 1 0 0 1 0
8 0 0 0 0 0 0 1 0 0
9 0 0 0 0 0 1 0 0 0

это был первоначально лабиринт ... нужно отметить row1 col4 как начало и row7 col8 конец ...

Никто никогда не говорил мне, как реализовать граф из матрицы (без пера): Pp

спасибо

Answer 1

Вы можете преобразовать график из представления матрицы смежности в представление на основе узлов, например:

#include <iostream>
#include <vector>
using namespace std;

const int adjmatrix[9][9] = {
  {0,1,0,0,1,0,0,0,0},
  {1,0,1,0,0,0,0,0,0},
  {0,1,0,1,0,0,0,0,0},
  {0,0,1,0,0,1,0,0,0},
  {1,0,0,0,0,0,1,0,0},
  {0,0,0,1,0,0,0,0,1},
  {0,0,0,0,1,0,0,1,0},
  {0,0,0,0,0,0,1,0,0},
  {0,0,0,0,0,1,0,0,0}
};

struct Node {
  vector<Node*> neighbours;
  /* optional additional node information */
};

int main (int argc, char const *argv[])
{
  /* initialize nodes */
  vector<Node> nodes(9);

  /* add pointers to neighbouring nodes */
  int i,j;
  for (i=0;i<9;++i) {
    for (j=0;j<9;++j) {
      if (adjmatrix[i][j]==0) continue;
      nodes[i].neighbours.push_back(&nodes[j]);
    }
  }

  /* print number of neighbours */
  for (i=0;i<9;++i) {
    cout << "Node " << i
         << " has " << nodes[i].neighbours.size() <<" outbound edges." << endl;
  }

  return 0;
}

Здесь график представлен в виде массива узлов с указателями на достижимые соседние узлы.После настройки узлов и их соседних указателей вы используете эту структуру данных для выполнения желаемых алгоритмов графа, в этом (тривиальном) примере выведите количество исходящих направленных ребер, которые имеет каждый узел.

Answer 2

Природа симметрии

Матрица смежности является представлением графа.Для неориентированного графа его матрица симметрична.Например, если есть ребро от vertex i до vertex j, также должно быть ребро от vertex j до vertex i.На самом деле это то же самое преимущество.

* 
  * 
    *     A'
  A   * 
        *
          * 

Алгоритм

Заметив эту природу, вы можете реализовать свой алгоритм так просто, как:

void drawGraph(vertices[nRows][nCols])
{
    for (unsigned int i = 0; i < nRows; ++i)
    {
        for (unsigned int j = i; j < nCols; ++j)
        {
            drawLine(i, j);
        }
    }
}