我正在寻找 C++ 中图形的简洁和精确的邻接表表示。我的节点只是节点 ID。这是我的做法。只是想知道专家对此有何看法。有没有更好的办法？
这是类实现（没什么花哨的，现在不关心公共/私有方法）
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
using namespace std;
class adjList {
public:
int head;
vector<int> listOfNodes;
void print();
};
void adjList :: print() {
for (int i=0; i<listOfNodes.size(); ++i) {
cout << head << "-->" << listOfNodes.at(i) << endl;
}
}
class graph {
public:
vector<adjList> list;
void print();
};
void graph :: print() {
for (int i=0; i<list.size(); ++i) {
list.at(i).print();
cout << endl;
}
}
我的 main 函数逐行解析输入文件。其中每一行解释如下：
<source_node> <node1_connected_to_source_node> <node2_connected_to_source_node <node3_connected_to_source_node> <...>
这是主要的：
int main()
{
fstream file("graph.txt", ios::in);
string line;
graph g;
while (getline(file, line)) {
int source;
stringstream str(line);
str >> source;
int node2;
adjList l;
l.head = source;
while (str >> node2) {
l.listOfNodes.push_back(node2);
}
g.list.push_back(l);
}
file.close();
g.print();
getchar();
return 0;
}
我知道我应该在 adjList 类中添加 addEdge() 函数，而不是直接从 main() 修改它的变量，但是现在我只是想知道最好的结构。
编辑： 我的方法有一个缺点。对于具有大量节点的复杂图，节点确实是一个结构/类，在这种情况下，我将通过存储整个对象来复制值。在那种情况下，我认为我应该使用指针。例如对于无向图，我将在 adjList 中存储节点对象的副本（节点 1 和 2 之间的连接意味着 1 的邻接列表将具有 2，反之亦然）。我可以通过将节点对象的指针存储在 adjList 而不是整个对象中来避免这种情况。检查从这种方法中受益的 dfs 实现。在那里我需要确保每个节点只被访问一次。拥有同一个节点的多个副本会让我的生活更加艰难。不？
在这种情况下，我的类定义将改变如下：
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <map>
using namespace std;
class node {
public:
node() {}
node(int id, bool _dirty): node_id(id), dirty(_dirty) {}
int node_id;
bool dirty;
};
class adjList {
public:
node *head;
vector<node*> listOfNodes;
void print();
~adjList() { delete head;}
};
void adjList :: print() {
for (int i=0; i<listOfNodes.size(); ++i) {
cout << head->node_id << "-->" << listOfNodes.at(i)->node_id << endl;
}
}
class graph {
public:
vector<adjList> list;
void print();
void dfs(node *startNode);
};
void graph::dfs(node *startNode) {
startNode->dirty = true;
for(int i=0; i<list.size(); ++i) {
node *stNode = list.at(i).head;
if (stNode->node_id != startNode->node_id) { continue;}
for (int j=0; j<list.at(i).listOfNodes.size(); ++j) {
if (!list.at(i).listOfNodes.at(j)->dirty) {
dfs(list.at(i).listOfNodes.at(j));
}
}
}
cout << "Node: "<<startNode->node_id << endl;
}
void graph :: print() {
for (int i=0; i<list.size(); ++i) {
list.at(i).print();
cout << endl;
}
}
这就是我实现 main() 函数的方式。我正在使用 map<> 来避免对象的重复。仅在之前未定义时才创建新对象。通过 id 检查对象是否存在。
int main()
{
fstream file("graph.txt", ios::in);
string line;
graph g;
node *startNode;
map<int, node*> nodeMap;
while (getline(file, line)) {
int source;
stringstream str(line);
str >> source;
int node2;
node *sourceNode;
// Create new node only if a node does not already exist
if (nodeMap.find(source) == nodeMap.end()) {
sourceNode = new node(source, false);
nodeMap[source] = sourceNode;
} else {
sourceNode = nodeMap[source];
}
adjList l;
l.head = sourceNode;
nodeMap[source] = sourceNode;
while (str >> node2) {
// Create new node only if a node does not already exist
node *secNode;
if (nodeMap.find(node2) == nodeMap.end()) {
secNode = new node(node2, false);
nodeMap[node2] = secNode;
} else {
secNode = nodeMap[node2];
}
l.listOfNodes.push_back(secNode);
}
g.list.push_back(l);
startNode = sourceNode;
}
file.close();
g.print();
g.dfs(startNode);
getchar();
return 0;
}
第二次编辑 在Ulrich Eckhardt建议将邻接列表放入节点类之后，我认为这是一种更好的数据结构来存储图形并执行 dfs()、dijkstra() 类操作。请注意，邻接列表合并到节点类中。
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <map>
using namespace std;
class node {
public:
node() {
}
node(int id, bool _dirty): node_id(id), dirty(_dirty) {
//cout << "In overloaded const\n";
}
int node_id;
bool dirty;
vector<node*> listOfNodes;
};
class graph {
public:
vector<node*> myGraph;
void dfs(node* startNode);
};
void graph::dfs(node* startNode) {
startNode->dirty = true;
for (int j=0; j<startNode->listOfNodes.size(); ++j) {
if (!startNode->listOfNodes.at(j)->dirty) {
dfs(startNode->listOfNodes.at(j));
}
}
cout << "Node: "<<startNode->node_id << endl;
}
我们能做得比这更好吗？