邻接矩阵.c

#include <iostream>
#include <cassert>
#include <vector>
#include <ctime>

using namespace std;

//稠密图-邻接矩阵
class DenseGraph {
	private:
		int n,m;
		bool directed;//是否为有向图
		vector< vector<bool> > g;

	public:
		//构造方法
		DenseGraph(int n, bool directed) {
			this->n = n;
			this->directed = directed;
			this->m = 0;
			for(int i = 0; i < n; i++) {
				g.push_back(vector<bool> (n , false));
			}
		}
		~DenseGraph() {

		}
		//返回顶点个数
		int V() {
			return n;
		}
		//返回边条数
		int E() {
			return m;
		}
		//两节点添加边
		void addEdge(int v, int w) {
			if (hasEdge(v, w)) {
				return ;
			}
			g[v][w] = true;
			if (!directed) {
				g[w][v] = true;
			}
			m++;

		}
		//两节点是否有边
		bool hasEdge(int v,int w) {
			assert(v >= 0 && v < n);
			assert(w >= 0 && w < n);
			return g[v][w];
		}
		//打印图矩阵的值
		void printG() {
			for(int i = 0; i < n ; i++) {

				for(int j = 0; j < n; j++) {
					cout << g[i][j]	 << " ";
				}
				cout << endl;
			}
		}

		//自定义迭代器 进行访问
		class adjIterator {
			private:
				DenseGraph &G;
				int index;
				int v;
			public:
				adjIterator(DenseGraph &graph, int v) :G(graph) {
					this->v = v;
					this->index = -1;
				}

				int begin() {
					index = - 1;
					return next();
				}

				int next() {
					for(index += 1; index < G.V(); index++) {
						if (G.g[v][index]) {
							return index;
						}
					}
					return -1;
				}

				bool end() {
					return index >= G.V();
				}
		};

};


int main() {
	srand(time(NULL));
	int n = 10;//节点数
	int m = 66;//边条数

	DenseGraph denseGraph = DenseGraph(n, false);
	for (int i =0; i < m; i++) {
		int v = rand() % n;
		int w = rand() % n;
		denseGraph.addEdge(v, w);
	}

	cout << "以下是添加了边的关系后图中矩阵的值:" << endl;
	denseGraph.printG();

	cout << endl;
	cout << "以下是通过自定义迭代器进行访问节点0关联的边:" << endl;

	for (int i = 0; i < n; i++) {
		DenseGraph::adjIterator adj(denseGraph, i);
		cout << "节点" <<  i << ":";
		for(int w = adj.begin(); !adj.end(); w = adj.next()) {
			cout << w <<" ";

		}
		cout <<endl;
	}

	return 0;
}