图论基础与拓补排序

---

图论基础

图的表示

二元组G = <V, E>, V节点集，E边集；

节点的度：与该节点相关联的边数

分为：有向图、无向图

图的存储

邻接矩阵

一个一维数组存储图中节点的信息，一个二维数组存储图中节点之间的邻接关系。

无向图：

特点：

• 无向图的邻接矩阵是对称矩阵，并且是唯一的。

• 第i行或第i列非零元素的个数正好是第i个节点的度。上图中的邻接矩阵，第3列非零元素的个数为2，说明第3个节点c的度为2。

有向图：

以尖括号<vi, vj>表示的是有序对，以圆括号(vi ,vj)表示的是无序对。

有向图的邻接矩阵不一定是对称的

特点：

• 有向图的邻接矩阵不一定是对称的。
• 第i行非零元素的个数正好是第i个节点的出度，第i列非零元素的个数正好是第i个节点的入度。上图中的邻接矩阵，第3行非零元素的个数为2，第3列非零元素的个数也为2，说明第3个节点c的出度和入度均为2。

网（带权图）：

邻接矩阵的优点：

• 快速判断在两节点之间是否有边。在图中，Edge[i][j]=1，表示有边；Edge[i][j]=0，表示无边。在网中，Edge[i][j]=∞，表示无边，否则表示有边。时间复杂度为O (1)。

• 方便计算各节点的度。在无向图中，邻接矩阵第i行元素之和就是节点i的度；在有向图中，第i行元素之和就是节点i的出度，第i列元素之和就是节点i的入度。时间复杂度为O(n)。

邻接矩阵的缺点：

• 不便于增删节点。增删节点时，需要改变邻接矩阵的大小，效率较低。

• 不便于访问所有邻接点。访问第i个节点的所有邻接点时，需要访问第i行的所有元素，时间复杂度为O(n)。访问所有节点的邻接点，时间复杂度为O(n^2)。

• 空间复杂度高，为O(n^2)。

邻接表

邻接表是图的一种链式存储方法，其数据结构包括两部分：节点和邻接点。

1. 无向图

一个节点的所有邻接点构成一个单链表。

无向图特点：

• 如果无向图有n个节点、e条边，则节点表有n个节点，邻接点表有2e个节点。

• 节点的度为该节点后面单链表中的节点数。

2. 有向图

对有向图中节点的邻接点，只看该节点的出边（出弧）。

有向图特点：

• 如果有向图有n个节点、e条边，则节点表有n个节点，邻接点表有e个节点。

• 节点的出度为该节点后面单链表中的节点数。

在有向图邻接表中很容易找到节点的出度，但是找入度很难，需要遍历所有邻接点表中的节点，查找到该节点出现了多少次，入度就是多少。

图的遍历

参考多叉树，多叉树的遍历框架如下：

/* 多叉树遍历框架 */
void traverse(TreeNode* root) {
    if (root == nullptr) return;
	for (TreeNode* child : root -> children) {
		traverse(child);
	}
}

图和多叉树最⼤的区别是，图是可能包含环的，你从图的某⼀个节点开始遍历，有可能⾛了⼀圈⼜回到这个

节点。

因此，遍历需要一个visited辅助数组，不走重复的节点。

// 记录被遍历过的节点
vector<bool> visited;
// 记录从起点到当前节点的路径
vector<bool> onPath;
/* 图遍历框架 */
void traverse(Graph graph, int s) {
	if (visited[s]) return;
    // 经过节点 s，标记为已遍历
    visited[s] = true;
    // 做选择：标记节点 s 在路径上
    onPath[s] = true;
    for (int neighbor : graph.neighbors(s)) {
        traverse(graph, neighbor);
    }
    // 撤销选择：节点 s 离开路径
    onPath[s] = false; 
}

对于图的遍历，应该把onPath的操作放到for循环外⾯，否则会漏掉记录起始点的遍历。

如果图中不含有环，可以把visited数组省略。

797.所有可能路径

题目描述：

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序） graph[i]是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

解析：

有向无环图，以0为起点开始遍历，同时记录走过的路径，当遍历到终点时将路径记录下来。

可以不使用visited数组辅助。

vector<vector<int>> res; //记录所有的路径

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    vector<int> path; //维护递归过程中经过的路径
    tranverse(graph, path, 0);
    return res;
}
//图的遍历
void tranverse(vector<vector<int>>& graph, vector<int>& path, int index) {
    //添加节点index到路径
    path.push_back(index);
    
    int n = graph.size();
    if (index == n - 1) { 
        //到达终点
        res.push_back(path);
        path.pop_back();
        return;
    }
	//递归每个相邻节点
    for (int v : graph[index]) {
        tranverse(graph, path, v);
    }
	//从路径移除节点index
    path.pop_back();
}

判断图是否有环（图的遍历）

207.课程表

存在依赖问题，⾸先把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

graph[index] 是⼀个列表，存储着节点 index 所指向的节点。

先建图 + 遍历图判断是否存在环

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    bool hasCycle = 0; // 记录图中是否有环
    vector<bool> visited(numCourses, 0); //防止重复遍历同一节点
    vector<bool> path(numCourses, 0); //记录当前走过的路径
    vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
    for (int i = 0; i < numCourses; i++) {
        // 遍历图中的所有节点
        tranverse(graph, visited,path, i, hasCycle);
    }
	// 只要没有循环依赖可以完成所有课程
    return !hasCycle;
}
//建立图的邻接表
vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
    //图中共有numCourses个节点
    vector<vector<int>> graph(numCourses);
    for (auto v : prerequisites) {
        int from = v[1];
        int to  = v[0];
        // 修完课程 from 才能修课程 to
		// 在图中添加⼀条从 from 指向 to 的有向边
        graph[from].push_back(to);
    } 
    return graph;
}
// 图遍历函数
void tranverse(vector<vector<int>>& graph, vector<bool>& visited,vector<bool>& path, int index, bool& hasCycle) {
    if (path[index]) { //如果发现Path[index] 已经被标记说明出现了环
        hasCycle = true; //发现环
    }
    if (visited[index] || hasCycle) { 
        return;
    }
	//将节点index标记为已遍历
    visited[index] = true;
    //开始遍历节点index
    path[index] = true;
    for (auto v : graph[index]) {
        tranverse(graph, visited,path, v, hasCycle);
    }
    //节点index遍历完成
    path[index] = false;
}

拓补排序

210.课程表II

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

输入：numCourses = 1, prerequisites = []
输出：[0]

拓扑排序（Topological Sorting）

直观地说就是，让你把⼀幅图「拉平」，⽽且这个「拉平」的图⾥⾯，所有箭头⽅向都是⼀致的。

如果⼀幅有向图中存在环，是⽆法进⾏拓扑排序的，因为肯定做不到所有箭头⽅向⼀致；反过来，如果⼀幅图是「有向⽆环图」，那么⼀定可以进⾏拓扑排序。

将后序遍历的结果进⾏反转，就是拓扑排序的结果。

先对图进行DFS遍历，记录后序遍历结果，最后将后序遍历结果反转。

进⾏拓扑排序之前要进⾏环检测

vector<int> postorder; // 记录后序遍历结果
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    bool hasCycle = false; // 记录是否存在环
    vector<bool> visited(numCourses, 0);
    vector<bool> path(numCourses, 0);
    // 建立图
    vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
    // 遍历图
    for (int i = 0; i < numCourses; i++) {
        tranverse(graph, visited,path, i, hasCycle);
    }
    // 有环图⽆法进⾏拓扑排序
    if (hasCycle) return {};
    // 逆后序遍历结果即为拓扑排序结果
    reverse(postorder.begin(), postorder.end());

    return postorder;
}

//建立图的邻接表
vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    for (auto v : prerequisites) {
        int from = v[1];
        int to  = v[0];
        graph[from].push_back(to);
    } 
    return graph;
}
// 图遍历函数
void tranverse(vector<vector<int>>& graph, vector<bool>& visited,vector<bool>& path, int index, bool& hasCycle) {
    if (path[index]) {
        hasCycle = true;
    }
    if (visited[index] || hasCycle) {
        return;
    }
	// 前序遍历位置
    visited[index] = true;
    path[index] = true;
    for (auto v : graph[index]) {
        tranverse(graph, visited, path, v, hasCycle);
    }
    // 后序遍历位置
    postorder.push_back(index);
    path[index] = false;
}

二分图

⼆分图的顶点集可分割为两个互不相交的⼦集，图中每条边依附的两个顶点都分属于这两个⼦集，且

两个⼦集内的顶点不相邻。

给出一副图，用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同。

二分图的判定：

遍历⼀遍图，⼀边遍历⼀边染⾊，看看能不能⽤两种颜⾊给所有节点染⾊，且相邻节点的颜⾊都不相同。

图的遍历框架1：

// 记录被遍历过的节点
vector<bool> visited;
// 记录从起点到当前节点的路径
vector<bool> onPath;
/* 图遍历框架 */
void traverse(Graph graph, int s) {
	if (visited[s]) return;
    // 经过节点 s，标记为已遍历
    visited[s] = true;
    // 做选择：标记节点 s 在路径上
    onPath[s] = true;
    for (int neighbor : graph.neighbors(s)) {
        traverse(graph, neighbor);
    }
    // 撤销选择：节点 s 离开路径
    onPath[s] = false; 
}

图的遍历框架2：

vector<bool> visited;
void traverse(Graph graph, int v) {
	// 前序遍历位置，标记节点 v 已访问
    visited[s] = true;
   
    for (int neighbor : graph.neighbors(v)) {
        if (!visited[neighbor]) {
            // 只遍历没标记过的相邻节点
            traverse(graph, neighbor);
        }  
    }
}

这种写法把对 visited 的判断放到递归调⽤之前，和之前的写法唯⼀的不同就是，你需要保证调⽤

traverse(v) 的时候，visited[v] == false。

785.判断⼆分图

输⼊⼀个 邻接表 表示⼀幅⽆向图，请你判断这幅图是否是⼆分图。

解析：

遍历图，相邻节点涂不同颜色，额外使用一个color数组记录每个节点的颜色。

bool ok = true; // 记录图是否符合⼆分图性质
vector<bool> color; // 记录图中节点的颜⾊，false 和 true 代表两种不同颜⾊
vector<bool> visited; // 记录图中节点是否被访问过

// 主函数，输⼊邻接表，判断是否是⼆分图
bool isBipartite(vector<vector<int>>& graph) {
	int n = graph.size();
    color.resize(n, 0);
    visited.resize(n, 0);
    // 因为图不⼀定是联通的，可能存在多个⼦图
 	// 所以要把每个节点都作为起点进⾏⼀次遍历
 	// 如果发现任何⼀个⼦图不是⼆分图，整幅图都不算⼆分图
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            tranverse(graph, i);
        }
    }
    return ok;
}

// DFS 遍历框架
void tranverse(vector<vector<int>>& graph, int v) {
    // 如果已经确定不是⼆分图了，就不⽤浪费时间再递归遍历了
 	if (!ok) return;
    
    visited[v] = true;
    for (auto s : graph[v]) {
        if (!visited[s]) {
            // 相邻节点 s 没有被访问过
 			// 那么应该给节点 s 涂上和节点 v 不同的颜⾊
 			color[s] = !color[v];
            // 继续遍历 s
            tranverse(graph, s);
            //bfs(graph, s);
        } else {
            // 相邻节点 s 已经被访问过
 			// 根据 v 和 s 的颜⾊判断是否是⼆分图
            if (color[s] == color[v]) {
                // 若相同，则此图不是⼆分图
                ok = false;
            }
        }
    }
}

//BFS遍历
// 从 start 节点开始进⾏ BFS 遍历
void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty() && ok) {
        int v = q.front();
        q.pop();
        for (auto w : graph[v]) {
            if (!visited[w]) {
                color[w] = !color[v];
                visited[w] = true;
                q.push(w);
            } else {
                if (color[w] == color[v]) {
                    // 若相同，则此图不是⼆分图
                    ok = false;
                }
            }
        }
    }
}

886. 可能的二分法

给定一组 n 人（编号为 1, 2, …, n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。

给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]

输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false

输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false

二分图的判定，每个人看作节点，相互关系看作边，双色图，按照颜色分成两组。

bool ok = true; // 记录图是否符合⼆分图性质
vector<bool> color; // 记录图中节点的颜⾊，false 和 true 代表两种不同颜⾊
vector<bool> visited; // 记录图中节点是否被访问过

bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
	// 图节点编号从 1 开始
    color.resize(n + 1, 0);
    visited.resize(n + 1, 0);
    // 转化成邻接表表示图结构
    vector<vector<int>> graph = buildGraph(n, dislikes);
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            tranverse(graph, n);
        }
    }
    return ok;
}

// 建图函数
vector<vector<int>> buildGraph(int n, vector<vector<int>>& dislikes) {
    // 图节点编号为 1...n
    vector<vector<int>> graph(n + 1);
    for (auto edge : dislikes) {
        int from = edge[1];
        int to = edge[0];
        // 「⽆向图」相当于「双向图」
        graph[from].push_back(to);
        graph[to].push_back(from);
    }
    return graph;
}

// DFS 遍历框架
void tranverse(vector<vector<int>>& graph, int v) {
    // 如果已经确定不是⼆分图了，就不⽤浪费时间再递归遍历了
 	if (!ok) return;
    
    visited[v] = true;
    for (auto s : graph[v]) {
        if (!visited[s]) {
            // 相邻节点 s 没有被访问过
 			// 那么应该给节点 s 涂上和节点 v 不同的颜⾊
 			color[s] = !color[v];
            // 继续遍历 s
            tranverse(graph, s);
            //bfs(graph, s);
        } else {
            // 相邻节点 s 已经被访问过
 			// 根据 v 和 s 的颜⾊判断是否是⼆分图
            if (color[s] == color[v]) {
                // 若相同，则此图不是⼆分图
                ok = false;
            }
        }
    }
}