BFT/DFT/拓扑图实现
BFT/DFT/拓扑图实现
提问于 2011-09-03 18:05:59
我正在努力学习图形并在代码中实现。你能检查一下我的代码并给我反馈吗？
#include <iostream>
using namespace std;
#include <list>
#include <queue>
#include <map>类边缘
class Edge
{
public:
int dest;
int weight;
Edge(int dest) : dest(dest), weight(0) {}
};类顶点
class Vertex
{
public:
int orig;
std::list<Edge> adjList;
bool visited;
int indegree;
Vertex() : orig(-1), visited(false), indegree(0) {}
Vertex(int v) : orig(v), visited(false), indegree(0) {}
friend bool operator==(const Vertex & v, int data);
friend std::ostream & operator<<(std::ostream & os, const Vertex & v);
};
bool operator==(const Vertex & v, int data)
{
if (v.orig == data) return true;
return false;
}
std::ostream & operator<<(std::ostream & os, const Vertex & v)
{
os << v.orig << ":";
std::list<Edge>::const_iterator iter = v.adjList.begin();
for(; iter != v.adjList.end(); ++iter)
{
os << " " << iter->dest;
}
return os;
}类图
class Graph
{
private:
typedef std::map<int, Vertex> VertexMap;
typedef std::map<int, Vertex>::iterator VertexIterator;
typedef std::map<int, Vertex>::const_iterator VertexConstIterator;
bool visit(int v, std::list<int> & sortedList);
VertexMap vertices;
public:
void addVertex(int v);
void addEdge(int v1, int v2);
void print();
void BreadthFirstTour(int v);
void DepthFirstTour(int v);
void TopologicalSort();
void resetStates();
};
void Graph::addVertex(int v)
{
vertices.insert( std::make_pair(v, Vertex(v)) );
}
void Graph::addEdge(int v1, int v2)
{
VertexIterator iter = vertices.find(v1);
if (iter != vertices.end())
{
Edge edge(v2);
iter->second.adjList.push_back(edge);
}
iter = vertices.find(v2);
iter->second.indegree++;
}
void Graph::print()
{
VertexConstIterator iter = vertices.begin();
for (; iter != vertices.end(); ++iter)
{
cout << iter->second << "\n";
}
}
void Graph::BreadthFirstTour(int v)
{
cout << "BFS BEGIN\n";
std::queue<int> q;
VertexConstIterator iter = vertices.find(v);
if (iter != vertices.end())
{
q.push(iter->first);
}
else
{
cout << "BFS END\n";
return;
}
VertexIterator iter1;
while (!q.empty())
{
int vtx = q.front();
q.pop();
Vertex & v = vertices[vtx];
if (v.visited == false )
{
v.visited = true;
cout << v.orig << " ";
std::list<Edge>::const_iterator iter = v.adjList.begin();
while (iter != v.adjList.end())
{
//cout << "dest " << iter->dest << endl;
VertexConstIterator citer = vertices.find(iter->dest);
if (citer != vertices.end())
{
q.push(citer->first);
//cout << "pushing " << citer->orig << endl;
}
++iter;
}
}
}
cout << "\nBFS END" << endl;
resetStates();
}
void Graph::resetStates()
{
VertexIterator iter = vertices.begin();
for (; iter != vertices.end(); ++iter)
{
iter->second.visited = false;
}
}
void Graph::DepthFirstTour(int v)
{
VertexIterator iter = vertices.find(v);
if (iter != vertices.end())
{
if (iter->second.visited == false)
{
iter->second.visited = true;
std::list<Edge>::iterator liter = iter->second.adjList.begin();
for (; liter != iter->second.adjList.end(); ++liter)
{
DepthFirstTour(liter->dest);
}
cout << iter->second.orig << " ";
}
}
}
void Graph::TopologicalSort()
{
VertexConstIterator iter = vertices.begin();
std::list<int> sortedList;
bool cycle = false;
for (; iter != vertices.end(); ++iter)
{
if (iter->second.indegree == 0)
{
if (!visit(iter->first, sortedList))
{
cycle = true;
break;
}
}
}
if (cycle || sortedList.size() != vertices.size())
{
cout << "CYCLE";
return;
}
std::list<int>::const_iterator liter = sortedList.begin();
for (; liter != sortedList.end(); ++liter)
{
cout << *liter << " ";
}
}
bool Graph::visit(int v, std::list<int> & sortedList)
{
VertexIterator iter = vertices.find(v);
if (iter != vertices.end())
{
if (iter->second.visited == false)
{
iter->second.visited = true;
std::list<Edge>::const_iterator liter = iter->second.adjList.begin();
for (; liter != iter->second.adjList.end(); ++liter)
{
if (!visit(liter->dest, sortedList))
{
return false;
}
}
sortedList.push_front(iter->first);
}
else
{
return false;
}
}
return true;
}main()
int main()
{
Graph g;
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addVertex(4);
g.addVertex(5);
g.addVertex(6);
g.addVertex(7);
g.addVertex(8);
g.addEdge(1,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.addEdge(2,5);
g.addEdge(3,6);
g.addEdge(3,7);
//g.addEdge(5,8); //disjoint node 8
//g.addEdge(6,3); //this is forming cycle
g.print();
g.BreadthFirstTour(1);
cout << "DFS START\n";
g.DepthFirstTour(1);
g.resetStates();
cout << "\nDFS END" << endl;
cout << "TOPOLOGICAL SORT START\n";
g.TopologicalSort();
g.resetStates();
cout << "\nTOPOLOGICAL SORT END\n";
return 0;
}回答 1
Code Review用户
回答已采纳
发布于 2011-09-03 18:45:50
不要使用命名空间std
在包含其他头文件之前
如果你必须这样做，那就把它放在所有的包含之后。但最好不要用它。
#include <iostream>
using namespace std;
#include <list>
#include <queue>
#include <map>你真的想让Vertix的所有成员都公开吗？
public:
int orig;
std::list<Edge> adjList;
bool visited;
int indegree;平等检验是正确的：
if (v.orig == data) return true;
return false;但是像这样写起来更容易读懂：
return v.orig == data;当您有一个操作符<<时，实现>>通常是一个好主意(从长远来看，您可能会这样做)。因此，在编写输出流时，您希望以一种轻松的方式编写输出流。因此，当类包含诸如向量之类的内容时，在它们前面加上元素计数(而不是终止标记)是有用的。此外，任何子元素都应该使用自己的流运算符<<打印，因此您可能也应该为边缘编写一个。
根据容器的迭代器。这样，如果更改容器，只需进行一次更改(而不是一连串的更改)。
typedef std::map<int, Vertex> VertexMap;
typedef std::map<int, Vertex>::iterator VertexIterator;
typedef std::map<int, Vertex>::const_iterator VertexConstIterator;可以写成：
typedef std::map<int, Vertex> VertexMap;
typedef VertexMap::iterator VertexIterator;
typedef VertexMap::const_iterator VertexConstIterator;
// ^^^^^^^^^ Use the container type we just defined.这是你们的公众成员要缠着你们的地方。
iter->second.adjList.push_back(edge);您正在将顶点的表示绑定到始终包含它在此庄园中的边缘列表。您确实应该在类上定义一个更抽象的接口，它允许您更改内部表示，而不影响图的实现。
当你把边加到图中时。
你去查查消息来源在那里。但是，您不检查是否已经创建了目标节点。我希望这个更对称。
方法'void resetStates()‘真的是公共接口的成员吗？
在图的BreadthFirstTour/DepthFirstTour遍历中。它实际上不是宽度第一/深度第一次巡演(因为这意味着宽度或深度)，而图则不太对称(特别是因为边有权且图形可能不是完全连通的)。
但是，作为实现的一部分，您实际上存储节点(顶点)是否作为顶点的成员被访问。您基本上将图形的遍历与其实现紧密耦合，这可能会限制您在以后对该图的增强(以及限制如何遍历该图)。
您可以通过使用访问者模式将图形从图形的实现中分离出来。这也符合开放/封闭原则，使您的类对扩展开放，但通过允许在图形外部指定遍历机制来关闭更改。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/4561
复制相关文章
相似问题
腾讯云开发者
