图与订购

Question

我试图解决这个问题在c + +代码，我想没有罐头的解决方案（作为提升）。

定义了这个---一个无向连接。假设有一个与他的指标未定尺寸的图形，存储在一个容器：

1 - Obj1 
2 - Obj2 
3 - Obj3 
4 - Obj4 
5 - Obj5 
... 

现在假设有：

1 --- 5 
    2 --- 3 
    4 --- 2 
    ... 

现在我们选择删除3 - 3的OBJ，我想有：

1 - Obj1 
2 - Obj2 
3 - Obj4 
4 - Obj5 
... 

和

1 --- 4 
3 --- 2 
... 

我也想通过索引访问这些对象。 我试图找到一个解决方案，但我不能。

我需要更多处理这些元素：首先添加它们，并将它们的属性存储在对象中，连接的属性也是一样，不需要任何成本。在我需要删除其中一些保留引用之后。

哪个是最简单，最有效的可能实现，关于使用STL的任何想法？

谢谢！

Answer 1

如果你想保持简单，只需要为你的顶点使用一个向量。 V是你的顶点的类型。

std::vector<V> vertex; 
vertex.push(Obj1); 
vertex.push(Obj2); 
vertex.push(Obj3); 
vertex.push(Obj4); 
vertex.push(Obj5); 

你可以通过调用

vertex.erase(vertex.begin()+2); //delete the third entry 

删除一个顶点，之后vertex[2]将Obj4，而不是Obj3。

图的边缘有点复杂。你可以建立一个邻接表，它基本上是一个二维矢量。

std::vector<std::vector<V> > adjacency_list; 

你一定要确保，你删除i列，第的i每个条目，减少所有条目比i大的一个，如果你删除i个顶点。