Graph-Overview

图的基本术语

  • 阶（Order）：图G中点集V的大小称作图G的阶
    • 子图（Sub-Graph）：当图，其中 ，则称作图的子图
  • 生成子图（Spanning Sub-Graph）：指满足条件V(G′) = V(G)的G的子图
  • 度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。
  • 入度（In-degree）和出度（Out-degree）：一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
  • 自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。
  • 路径（Path）：从a到b的一条路径是指一个序列a(v0),e_1,v_1,e_2,v_2,…,e(k-1),b(vk) ，其中e_i的顶点为v_i及v(i-1)，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。
  • 行迹（Trace）：如果路径P(a,b)中的边各不相同，则该路径称为a到b的一条行迹。闭的行迹称作回路（Circuit）。
  • 轨道（Track）：如果路径P(u,v)中的顶点各不相同，则该路径称为a到b的一条轨道。闭的轨道称作圈（Cycle）。
  • 桥（Bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。

行迹一定是轨道，轨道不一定是行迹

Graph Algorithm

  1. 最短路
  2. 最小生成树
  3. 二分图
  4. 拓扑排序
  5. 基环树
  6. 欧拉路径

拓扑排序

vector<int> topo_sort(int k, vector<vector<int>> &edges) {
	vector<vector<int>> g(k);
	vector<int> in_deg(k);
	for (auto &e : edges) {
		int x = e[0], y = e[1] ; // 顶点编号从 0 开始，方便计算
		g[x].push_back(y);
		++in_deg[y];
	}
	vector<int> order;
	queue<int> q;
	for (int i = 0; i < k; ++i)
		if (in_deg[i] == 0)
			q.push(i);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			order.push_back(x);
			for (int y : g[x])	
				if (--in_deg[y] == 0)
					q.push(y);
		}
	return order;
}
Table Of Contents
Graph-Overview
图的基本术语
Graph Algorithm
拓扑排序