实现图形程序

Question

我正在尝试使用数组通过邻接矩阵实现图形。但是我偶然发现了一个问题我的图表有像 5、7、3、6 这样的顶点（它们不是为了映射到数组索引）。我知道要实现的是它们与数组索引相同。我想制作另一个带有顶点和数组索引的查找数组。

但是这样会使得它的时间复杂度很高。我也尝试在 Google 上搜索，但我找到的只是数组索引。

任何建议都会对邻接表或矩阵有所帮助

Answer 1

我可以想到两个直接的选择：

1.顶点标记

对于您阅读的每个顶点，用标签标识它。在你的情况下：

vertex | tag
-------|-----
  5    |  0
  7    |  1
  3    |  2
  6    |  3

为了获得良好的性能，您应该使用 unordered_map（或散列映射）以正反顺序映射顶点，这样当给定一个顶点时，您可以得到它的标签在 O(1) 中带有 forward[vertex]，当你得到一个标签时，你可以在 O(1) 中用 backwards[tag]:

找到它的顶点

int tag = 0;
unordered_map<int, int> forward, backwards;

for(int v : vertices){
    forward[v] = tag;
    backwards[tag] = v;
    tag++;
}

最后，如您所知，使用标记 0、1、...、n - 1 将您的图表示为邻接表。

2。直接映射

这更容易。不要为顶点使用数组，而是使用 unordered_map 将顶点值映射到它的邻接列表：

unordered_map<int, vector<int>> G;

for(int v : vertices){
    G[v] = vector<int>();
    vector<int> &adj = G[v];
    //add all nodes adjacent to v in adj
}

如果你想遍历5的邻接表，只需这样做：

vector<int> &adjList = G[5];

for(int v : adjList){
    //stuff
}

实现图形程序

Implementing Graph Program

algorithm

graph

graph-algorithm