[C++] 图结构

点结构

class Node {
public:
	int val;
	int in;		// 入度： 指向此点的边个数
	int out;	// 出度： 从此点发出的边个数
	vector<Node*> nexts;		// 直接邻接点
	vector<Edge*> edges;		// 边

	Node(int val) {
		this->val = val;
		this->in = 0;
		this->out = 0;
		nexts = vector<Node>();
		edges = vector<Edge>();
	} 
};

边结构

class Edge {
public:
	int weight;		// 边权重
	Node *from;		// 起点
	Node *to;		// 终点

	Edge(int weight, Node *from, Node *to) {
		this->weight = weight;
		this->from = from;
		this->to = to;
	}
};

图结构

class Graph {
public:
	unordered_map<int, Node*> nodes;	// 点集合
	set<Edge*> edges;					// 边集合

	Graph() {
		nodes = unordered_map<int, Node*>();
		edges = set<Edge*>();
	}
};

图构建

// 入参转换器
class GraphGenerator {
public:
	// 例如 matrix是N * 3的矩阵，[weight, from, to]
	static Graph createGraph(vector<vector<int>> matrix) {
		Graph graph = Graph();
		for (int i = 0; i < matrix.size(); i++) {
			int weight = matrix[i][0];
			int from = matrix[i][1];
			int to = matrix[i][2];

			// 图中若无from点，则构建
			if (graph.nodes.find(from) == graph.nodes.end()) {
				graph.nodes[from] = new Node(from);
			}
			// 图中若无to点，则构建
			if (graph.nodes.find(to) == graph.nodes.end()) {
				graph.nodes[to] = new Node(to);
			}

			// 提取from, to点，构建边结构
			Node *fromNode = graph.nodes[from];
			Node *toNode = graph.nodes[to];
			Edge *edge = new Edge(weight, fromNode, toNode);

			// from点的邻居点集合添加to，边集合添加edge
			fromNode->nexts.push_back(toNode);
			fromNode->edges.push_back(edge);
			/* todo:根据有向/无向图情景选择toNode的边是否添加这条edge */

			// 两个相关点的出入度自增
			fromNode->out++;
			toNode->in++;

			// 图中增加此边
			graph.edges.insert(edge);
		}
		return graph;
	}
};

遍历

因为图可能有环，那么节点可能会重复放入，所以引入STL中的set做去重。避免重复放入已遍历的点。

1. 广度优先遍历：利用队列

// BFS 广度优先遍历
static void BFS(Node *node) {
	if (node == nullptr)
		return;
	queue<Node *> nqueue;
	set<Node *> nset;	// 去重, 避免重复放入已遍历的点

	nqueue.push(node);
	nset.insert(node);

	while (!nqueue.empty()) {
		Node *cur = nqueue.front();
		nqueue.pop();
		cout << cur->val << " ";
		for (Node *next : cur->nexts) {
			if (nset.find(next) == nset.end()) {
				nset.insert(next);
				nqueue.push(next);
			}
		}
	}
}

2. 深度优先遍历：利用栈

栈里保存的就是从根节点（出发节点）到此节点的路径。

// DFS
static void DFS(Node *node) {
	if (node == nullptr)
		return;
	stack<Node *> nstack;
	set<Node *> nset;

	nstack.push(node);
	nset.insert(node);
	cout << node->val << " ";

	while (!nstack.empty()) {
		Node *cur = nstack.top();
		nstack.pop();

		for (Node *next : cur->nexts) {
			if (nset.find(next) == nset.end()) {
				nstack.push(cur);
				nstack.push(next);

				nset.insert(next);

				cout << next->val << " ";
				break;		// 此时找到了一条可行路径，其他邻居就不遍历了，一条路走到黑，其他邻居等后续流程分支中进行处理
			}
		}
	}
}