如何从邻接矩阵创建无向图？

Question

你好，到处都有一个通过绘图热来创建图形的解释。矩阵。但是，我需要简单的伪代码或算法......我知道如何从 adj 中绘制它。矩阵，不知道为什么没有人在哪里解释如何实际将其放入代码中。我不是指实际的代码，而是至少指算法...很多人说.. 1 是如果有一个我知道的边缘.. 我已经创建了 adj。矩阵，不知道如何将其转换为图形。我的顶点没有名称，它们只是矩阵的索引。例如 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 结束...

没有人告诉我如何从矩阵中实现图形（没有笔） ：

谢谢

Answer 1

对称性

邻接矩阵是图的表示。对于无向图，其矩阵是对称的。例如，如果存在从顶点 i 到顶点 j 的边，则也必须存在从顶点 j 到顶点的边我。这实际上是同一个边缘。

* 
  * 
    *     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);
        }
    }
}

Answer 2

您可以将图从邻接矩阵表示形式转换为基于节点的表示形式，如下所示：

#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;
}

这里，图表示为节点数组，其中包含指向可到达的相邻节点的指针。设置节点及其邻居指针后，您可以使用此数据结构来执行所需的图形算法，在此（简单的）示例中打印出每个节点具有的出站有向边的数量。