我需要删除重复的顶点(邻接表)
I need to remove duplicate vertices(adjacency list)
文件test.txt
6(这是顶点数)
1 4 (Еhe第一个是顶点的编号,第二个是正在构造边的顶点的编号。
1 6
2 1
2 3
2 4
2 5
3 2
3 5
4 1
4 2
4 5
5 2
5 3
5 4
6 1
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
class edge
{
private:
int node2id, nodeid;
public:
edge(int id, int id2)
{
node2id = id2;
nodeid = id;
}
int getnodeid()
{
return nodeid;
}
int getnodeid2()
{
return node2id;
}
};
int main()
{
int totalnode, node1, node2;
ifstream input("test.txt");
input >> totalnode;
vector<list<edge>>adjList(totalnode);
while (input >> node1 >> node2)
{
adjList[node1 - 1].push_back(edge(node2, node1));
}
int c = 1;
vector<list<edge>>::iterator i;
for (i = adjList.begin(); i != adjList.end(); i++)
{
cout << c << " -- ";
list<edge> li = *i;
list<edge>::iterator iter;
for (iter = li.begin(); iter != li.end(); iter++)
{
cout << "[" << (*iter).getnodeid() << "] ";
}
cout << endl;
c++;
}
while (input >> node1 >> node2)
{
adjList[node1 - 1].push_back(edge(node1, node1));
}
cout << "\n";
在这部分,创建了新的顶点,我不知道如何删除相同的顶点。
vector<list<edge>>::iterator j;
for (j = adjList.begin(); j != adjList.end(); j++)
{
//cout << c << " -- ";
list<edge> li = *j;
list<edge>::iterator iter;
for (iter = li.begin(); iter != li.end(); iter++)
{
cout << c <<" -- " << "[" << (*iter).getnodeid2() << "] " << "[" << (*iter).getnodeid() << "]\n";
c++;
}
}
return 0;
}
输出
将创建邻接表
1 -- [2] [4] [6]
2 -- [1] [3] [4] [5]
3 -- [2] [5]
4 -- [1] [2] [5]
5 -- [2] [3] [4]
6 -- [1]
这些顶点已创建,但例如,顶点 7 和 10(依此类推)具有相同的连接。并且你需要确保没有相同的顶点。
7 -- [1] [2]
8 -- [1] [4]
9 -- [1] [6]
10 -- [2] [1]
11 -- [2] [3]
12 -- [2] [4]
13 -- [2] [5]
14 -- [3] [2]
15 -- [3] [5]
16 -- [4] [1]
17 -- [4] [2]
18 -- [4] [5]
19 -- [5] [2]
20 -- [5] [3]
21 -- [5] [4]
22 -- [6] [1]
根据您目前的情况,您似乎并不真的需要 edge
class。所有信息都可以存储在 int
中。
为了解决您想要的问题,您可以先将所有边存储在 std::vector<std::set<int>
中,例如:
while (input >> node1 >> node2)
{
adjList[node1 - 1].insert(node2);
}
通过使用集合,所有边都按数字升序存储。所以而不是:
10 -- [2] [1]
你会:
10 -- [1] [2]
现在您可以将向量解析为 std::map
,例如:
std::map<std::set<int>, int> tempMap;
for(auto i = 0; i < totalnode; ++i)
{
s.try_emplace(adjList[i], i);
}
这会自动删除已经有另一个节点的节点,该节点具有相同的相邻节点集(就像您在问题中描述的那样)。
但是,我只是将其称为 tempMap
,因为目前,它们是按邻接顺序排序的,而不是按名称排序的。
所以你可以做的是:
std::map<int, std::set<int>> adjMap;
for(auto& [key, value] : tempMap)
{
adjMap.emplace(value, key);
}
现在您可以像这样遍历整个地图:
for(auto& [node, edges] : adjMap
{
std::cout << node << " -- ";
for(auto& edge: edges)
{
std::cout << "[" << edge << "]";
}
std::cout << "\n";
}
旁注,我注意到您编写了如下代码:
vector<list<edge>>::iterator i;
for (i = adjList.begin(); i != adjList.end(); i++) { // your loop }
相反,您可以使用:
for(auto it = adjList.begin(); it != adjList.end(); ++it) { // your loop }
^^^^
它会自动为 i
分配适合该容器的迭代器类型。
甚至在很多情况下:
for(auto& item : adjList) { // your loop }
您可以在循环中使用 item
,就像前面示例中的 *i
一样。
文件test.txt
6(这是顶点数)
1 4 (Еhe第一个是顶点的编号,第二个是正在构造边的顶点的编号。
1 6
2 1
2 3
2 4
2 5
3 2
3 5
4 1
4 2
4 5
5 2
5 3
5 4
6 1
#include <iostream> #include <fstream> #include <vector> #include <list> using namespace std; class edge { private: int node2id, nodeid; public: edge(int id, int id2) { node2id = id2; nodeid = id; } int getnodeid() { return nodeid; } int getnodeid2() { return node2id; } }; int main() { int totalnode, node1, node2; ifstream input("test.txt"); input >> totalnode; vector<list<edge>>adjList(totalnode); while (input >> node1 >> node2) { adjList[node1 - 1].push_back(edge(node2, node1)); } int c = 1; vector<list<edge>>::iterator i; for (i = adjList.begin(); i != adjList.end(); i++) { cout << c << " -- "; list<edge> li = *i; list<edge>::iterator iter; for (iter = li.begin(); iter != li.end(); iter++) { cout << "[" << (*iter).getnodeid() << "] "; } cout << endl; c++; } while (input >> node1 >> node2) { adjList[node1 - 1].push_back(edge(node1, node1)); } cout << "\n";
在这部分,创建了新的顶点,我不知道如何删除相同的顶点。
vector<list<edge>>::iterator j;
for (j = adjList.begin(); j != adjList.end(); j++)
{
//cout << c << " -- ";
list<edge> li = *j;
list<edge>::iterator iter;
for (iter = li.begin(); iter != li.end(); iter++)
{
cout << c <<" -- " << "[" << (*iter).getnodeid2() << "] " << "[" << (*iter).getnodeid() << "]\n";
c++;
}
}
return 0;
}
输出
将创建邻接表
1 -- [2] [4] [6]
2 -- [1] [3] [4] [5]
3 -- [2] [5]
4 -- [1] [2] [5]
5 -- [2] [3] [4]
6 -- [1]
这些顶点已创建,但例如,顶点 7 和 10(依此类推)具有相同的连接。并且你需要确保没有相同的顶点。
7 -- [1] [2]
8 -- [1] [4]
9 -- [1] [6]
10 -- [2] [1]
11 -- [2] [3]
12 -- [2] [4]
13 -- [2] [5]
14 -- [3] [2]
15 -- [3] [5]
16 -- [4] [1]
17 -- [4] [2]
18 -- [4] [5]
19 -- [5] [2]
20 -- [5] [3]
21 -- [5] [4]
22 -- [6] [1]
根据您目前的情况,您似乎并不真的需要 edge
class。所有信息都可以存储在 int
中。
为了解决您想要的问题,您可以先将所有边存储在 std::vector<std::set<int>
中,例如:
while (input >> node1 >> node2)
{
adjList[node1 - 1].insert(node2);
}
通过使用集合,所有边都按数字升序存储。所以而不是:
10 -- [2] [1]
你会:
10 -- [1] [2]
现在您可以将向量解析为 std::map
,例如:
std::map<std::set<int>, int> tempMap;
for(auto i = 0; i < totalnode; ++i)
{
s.try_emplace(adjList[i], i);
}
这会自动删除已经有另一个节点的节点,该节点具有相同的相邻节点集(就像您在问题中描述的那样)。
但是,我只是将其称为 tempMap
,因为目前,它们是按邻接顺序排序的,而不是按名称排序的。
所以你可以做的是:
std::map<int, std::set<int>> adjMap;
for(auto& [key, value] : tempMap)
{
adjMap.emplace(value, key);
}
现在您可以像这样遍历整个地图:
for(auto& [node, edges] : adjMap
{
std::cout << node << " -- ";
for(auto& edge: edges)
{
std::cout << "[" << edge << "]";
}
std::cout << "\n";
}
旁注,我注意到您编写了如下代码:
vector<list<edge>>::iterator i;
for (i = adjList.begin(); i != adjList.end(); i++) { // your loop }
相反,您可以使用:
for(auto it = adjList.begin(); it != adjList.end(); ++it) { // your loop }
^^^^
它会自动为 i
分配适合该容器的迭代器类型。
甚至在很多情况下:
for(auto& item : adjList) { // your loop }
您可以在循环中使用 item
,就像前面示例中的 *i
一样。