<分区>
我有一个类似于以下内容的文本文件:
person: head, body
head: eyes, nose, ears, mouth
body: arm, leg
arm: elbow, hand
leg: thigh, knee, foot
我试图用邻接表或有向图来表示它。最好的方法是什么？我想不出最好的数据结构或如何在 C++ 中表示它。
我已经尝试使用一个结构，其键值(person、head 等)和它的父索引，它的子元素作为 vector :
struct Node
{
string key;
int parentIndex;
vector<string> children;
};
但这似乎效率不高。有什么想法吗？
也许这样会更好？
struct {
string key;
Node* parent;
vector<Node> children;
};
最佳答案
您的数据样本中有几个问题尚未得到解答:是否始终只有一个入口点(例如:人)？它总是自上而下的分解(即每个元素最多有一个父元素)吗？元素是否总是以正确的方式出现:首先是顶部，然后是底部？
如果所有三个问题的答案都是肯定的，那么您建议的结构是合适的:
还有几点需要修正:
如您所见，最佳数据结构不仅取决于内容，还取决于您将如何使用它。
有很多其他方法可以做到这一点，以不同的方式平衡性能方面。例如:
class mygraph {
struct node { // nodes that you read:
string name;
int id; // index of the node in the nodes vector
vector<int> in; // parent(s) that can lead to this node
vector<int> out; // children you can go to
};
vector<node> nodes; // all the nodes in arbitrary sequential order
map<string, int> dict; // map converting the names into ids (redundant and optional, useful for efficien search by name);
public:
// members to populate the structure and to acces the nodes cleanly.
};
优点:
不便之处:填充结构时有一些开销:您需要通过验证映射中的名称将每个名称转换为 ID，如果不存在，则在节点 vector 中创建一个新节点并在映射中插入名称+新 ID。
关于c++ - 将文本文件解析为 C++ 有向图或邻接表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33508609/