graph.h

一个我的数据结构解题集合

#ifndef GRAPH_H__
#define GRAPH_H__

#include <stdexcept>
#include "Vector.h"
#include "SList.h"
#include "Stack.h"
#include "Queue.h"

template <typename T>
struct GraphNode {
	T data;
	mutable SList<int> adjvert;	// 与本结点相连的边(adjacent vertices)
	GraphNode(const T& t = T() ) : data(t) {}
};

/* 有向图，邻接表实现，实现值语义
 */
template <typename T>
class Graph {
private:
	int eCnt_;	// 边数 (顶点数由Vector保存)
	Vector<GraphNode<T> > vertices_;	// 顶点

	/* 查找顶点from, to，并返回它们的下标。
	 * 如果没找到，返回vertices_.size();
	 */
	void searchVertices(const T& from, const T& to, int& pfrom, int& pto) const {
		int vsize;
		pfrom = pto = vsize = vertices_.size();

		// 查找from和to
		int i = 0;
		while ( i < vsize && (pfrom == vsize || pto == vsize) ) {
			if (vertices_[i].data == from)
				pfrom = i;
			if (vertices_[i].data == to)
				pto = i;
			++i;
		}
	} // searchVertices(const T&, const T&, int&, int&) const

public:

	/* 构造函数，初始化一个新图
	 */
	Graph() : eCnt_(0) {}

	/* 拷贝构造函数
	 */
	Graph(const Graph& that) {
		eCnt_ = that.eCnt_;

		vertices_ = that.vertices_;
		for (int i = 0; i < vertices_.size(); ++i) {
			vertices_[i].adjvert = that.vertices_[i].adjvert.clone();	// 逐个拷贝
		}
	} // Graph(const Graph&)

	/* 赋值函数
	 */
	Graph& operator=(const Graph& that) {
		eCnt_ = that.eCnt_;

		vertices_ = that.vertices_;
		for (int i = 0; i < vertices_.size(); ++i) {
			vertices_[i].adjvert = that.vertices_[i].adjvert.clone();	// 逐个拷贝
		}	// 原先SList的析构由SList::operator=负责

		return *this;
	} // operator=(const Graph&)

	/* 插入一条由from指向to的有向边
	 * 如果顶点from或to原先不存在，则添加顶点
	 * 不允许from == to，否则抛出std::invalid_argument异常
	 * 这里没有限制平行边(2条相同指向的边)，应根据实际情况作出相应限制
	 */
	void insert(const T& from, const T& to) {
		if (from == to)
			throw std::invalid_argument(
				"Graph::insert(const T& from, const T& to) : "
				"requirement ( from != to ) violated\n"
			);

		int pfrom, pto;
		int vsize;
		pfrom = pto = vsize = vertices_.size();

		searchVertices(from, to, pfrom, pto);

		if (pfrom == vsize) {
			vertices_.pushBack(from);
		}
		if (pto == vsize) {
			vertices_.pushBack(to);
			pto = vertices_.size() - 1;	// 对于from和to同时被插入有必要
		}

		vertices_[pfrom].adjvert.insertAfter(	// 在邻接表的头上插入一条边
			vertices_[pfrom].adjvert.head(),
			pto
		);

		++eCnt_;	// 更新边数
	} // insert(const T&, const T&)

	/* 删除一条由from指向to的有向边
	 * 如果顶点from或to原先不存在（包括from == to），
	 * 抛出std::invalid_argument异常
	 */
	void remove(const T& from, const T& to) {
		int pfrom, pto;
		int vsize;
		SList<int>::Itor itor;
		pfrom = pto = vsize = vertices_.size();

		searchVertices(from, to, pfrom, pto);
		if ( (pfrom == vsize) || (pto == vsize) )
			goto throw_exception;	// 前提违反，避免goto应当写一个findEdge，且hasEdge中也可调用
									// 时间不够，goto了事

		itor = vertices_[pfrom].adjvert.head();
		while (itor != vertices_[pfrom].adjvert.tail()) {
			if (itor->next->data == pto) break;
			itor = itor->next;
		}

		if ( itor == vertices_[pfrom].adjvert.tail() )
			goto throw_exception;	// 前提违反

		vertices_[pfrom].adjvert.removeNext(itor);
		--eCnt_;	// 更新边数
		return;

	throw_exception:
		throw std::invalid_argument(
			"Graph::remove(const T& from, const T& to) : "
			"requirement hasEdge(from, to) violated\n"
		);
	} // remove(const T&, const T&)

	/* 返回倒转后的有向图(到转有向图的每条边)
	 * 保证原来的vertices()[i]等于倒转后的vertices()[i]
	 */
	Graph<T> reverse() const {
		Graph<T> r;
		r.vertices_.enlarge(vertices_.size());
		int i;
		for (i = 0; i < vertices_.size(); ++i) {
			r.vertices_[i].data = vertices_[i].data;
		}

		for (i = 0; i < vertices_.size(); ++i) {
			for ( SList<int>::Itor itor = vertices_[i].adjvert.begin();
				  itor != vertices_[i].adjvert.end();
				  itor = itor->next ) {
				r.insert(vertices_[itor->data].data, vertices_[i].data);
			}
		}
		return r;
	} // reverse()

	/* 深度优先的遍历 */
	template <typename Func>
	void depthFirstTraverse(Func visit) {
		Stack<SList<int>::Itor> sitor;
		Stack<int> si;
		Vector<bool> is_visited;

		is_visited.enlarge(vertices_.size());
		int i;
		for (i = 0; i < is_visited.size(); ++i)
			is_visited[i] = false;

		for (i = 0; i < vertices_.size(); ++i) {
			if (is_visited[i]) continue;
			visit(vertices_[i].data);
			is_visited[i] = true;
			SList<int>::Itor itor = vertices_[i].adjvert.begin();

			while (true) {
				while ( itor != vertices_[i].adjvert.end() ) {
					if ( !is_visited[itor->data] ) {
						visit( vertices_[itor->data].data );
						is_visited[itor->data] = true;
						si.push(i);
						sitor.push(itor);
						i = itor->data;
						itor = vertices_[i].adjvert.begin();
					} else {
						itor = itor->next;
					}
				}
				
				// 回溯
				if ( sitor.isEmpty() ) break;

				i = si.top();		si.pop();
				itor = sitor.top();	sitor.pop();
				itor = itor->next;
			}
		}

	} // depthFirstTraverse(Func)

	/* 广度优先的遍历 */
	template <typename Func>
	void breadthFirstTraverse(Func visit) {
		Queue<int> queue; 
		Vector<bool> is_visited;

		is_visited.enlarge(vertices_.size());
		int i;
		for (i = 0; i < is_visited.size(); ++i)
			is_visited[i] = false;

		for (i = 0; i < vertices_.size(); ++i) {
			if (is_visited[i]) continue;
			visit(vertices_[i].data);
			is_visited[i] = true;
			queue.push(i);

			while ( !queue.isEmpty() ) {
				int j = queue.front(); queue.pop();
				SList<int>::Itor itor = vertices_[j].adjvert.begin();

				while ( itor != vertices_[j].adjvert.end() ) {
					if ( !is_visited[itor->data] ) {
						visit( vertices_[itor->data].data );
						is_visited[itor->data] = true;
						queue.push(itor->data);
					}
					itor = itor->next;
				}
			}
		}

	} // breadthFirstTraverse(Func)

	/* 查询邻接表实体
	 * 违反封装性，应该写iterator代替
	 */
	Vector<GraphNode<T> >& vertices() {
		return vertices_;
	} // vertices()

	const Vector<GraphNode<T> >& vertices() const {
		return vertices_;
	} // vertices() const

	/* 查询顶点数 */
	int vertexCount() const { return vertices_.size(); }

	/* 查询边数 */
	int edgeCount() const { return eCnt_; }
	
	/* 查询是否存在从from到to的边, from == to返回false */
	bool hasEdge(const T& from, const T& to) const {
		int pfrom, pto;
		int vsize;
		pfrom = pto = vsize = vertices_.size();

		searchVertices(from, to, pfrom, pto);
		if ( (pfrom == vsize) || (pto == vsize) )
			return false;

		SList<int>::Itor itor = vertices_[pfrom].adjvert.begin();
		itor = vertices_[pfrom].adjvert.search(itor, pto);

		return itor != vertices_[pfrom].adjvert.end();
	} // hadEdge(const T&, const T&) const

};


#endif // GRAPH_H__