图的一些基础知识

建图方式主要三种：邻接表，邻接矩阵，链式前向星

邻接矩阵(V[][])一般用于稠密图（边多），如果两个节点i，j之间有联系，V[i][j] = 1（带权就等于权重）

用的最多的是邻接表。按照一般数据结构书的讲述，通过一个指针数组可以实现，数组中每个元素代表一个节点，也作为一个链表的头节点，链表中存的是这个节点指向图中哪些节点。每个链表元素中存有这个被指向节点的编号和指向边的权重（如果带权的话）

链式前向星后续篇章讲解。

C++中，这种数据结构可以用vector<vector<pair<int,int> >>表示。把每一行的链表作为一个vector<pair<int,int> >，(没带权直接vector<vector<int>>)一般没必要真的像在C语言中那些建一个指针数组和链表。Java中可以使用ArrayList<ArrayList<int[]>>。

初级阶段，常用的函数就是加边和获取某个节点的所有邻居两个函数

void addEdge(int u,int v,vector<vector<int>>& V,int indegree[]){
        V[u].push_back(v);
        indegree[v] ++;
    }
    const vector<int>& getEdgeFrom(int u,vector<vector<int>>& V){
        return V[u];
    }

代码中的V就是图。

加边函数中，indegree存储每个节点的入度，节点i的入度数量是indegree[i]，和后续讲到的拓扑排序有关

getEdgeFrom是获取节点u指向的所有邻居。为了省空间，返回值使用引用（引用不会拷贝）。为了保证不改变图，返回值使用const。

    public void addEdge(int u, int v,ArrayList<ArrayList<int>>) {
        V.get(u).add(v);
        indegree[v]++;
    }

    // 返回不可修改的视图，避免拷贝且防止外部修改
    public List<Integer> getEdgesFrom(int u,ArrayList<ArrayList<int>>) {
        return Collections.unmodifiableList(V.get(u));
    }

 

Java中的Collections.unmodifiableList()也可以使得返回值不可变，而且避免拷贝。

拓扑排序

1. 核心概念

拓扑排序是针对有向无环图 (DAG - Directed Acyclic Graph) 的一种线性序列算法。该序列需要满足一个核心条件：

对于图中的每一条有向边 (u -> v)，在排序后的序列中，顶点 u 都必须排在顶点 v 的前面。

通俗理解：这个序列就是一种“顺序安排”，保证了所有依赖关系都被满足（如果要完成v，必须先完成u）。

2. 为什么不能有环？

因为循环依赖（A->B->C->A）无法确定谁应该排在最先。如果图中有环，则不存在满足条件的拓扑序列。

3. 主要算法

最经典和常用的算法是 Kahn 算法，基于贪心和入度 (In-degree) 策略。

下面基于模板题讲解代码

力扣模板题。

C++完整代码

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //[ai,bi] bi->ai
        int indegree[2004];
        for(int i = 0;i < 2004;i ++)indegree[i] = 0;
        vector<vector<int>> graph;
        graph.resize(numCourses);
        for(int i = 0;i < prerequisites.size();i ++){
            addEdge(prerequisites[i][1],prerequisites[i][0],graph,indegree);
        }
        //拓扑排序
        int queue[2004];
        int l = 0,r = 0;
        //加入入度为0的节点
        for(int i = 0;i < numCourses;i ++){
            if(indegree[i] == 0){
                queue[r++] = i;
            }
        }
        int cnt = 0;
        while(l < r){
            int cur = queue[l++];
            cnt ++;
            for(int next : getEdgeFrom(cur,graph)){
                if(--indegree[next] == 0)queue[r++] = next;
            }
        }
        return cnt == numCourses ? true : false; 
        
        
        
    }

    void addEdge(int u,int v,vector<vector<int>>& V,int indegree[]){
        V[u].push_back(v);
        indegree[v] ++;
    }
    const vector<int>& getEdgeFrom(int u,vector<vector<int>>& V){
        return V[u];
    }
};

分析

注意，graph.resize(numCourses); 在这段代码中是必要且关键的，如果没有resize，graph是一个空的向量，直接使用graph[u]会引发越界访问，导致未定义行为（通常程序崩溃）。

错误的方式

vector<vector<int>> graph; // 大小为0
// 直接访问graph[u]会越界
graph[0].push_back(1); // 危险！可能崩溃

正确的方式（需要先分配空间）：

// 方式1：resize（代码中的方式）
vector<vector<int>> graph;
graph.resize(numCourses);

// 方式2：构造函数初始化
vector<vector<int>> graph(numCourses);

Java完整代码:

class Solution {
   public boolean canFinish(int numCourses, int[][] prerequisites) {
        // [ai, bi] 表示 bi -> ai
        int[] indegree = new int[numCourses];
        List<List<Integer>> graph = new ArrayList<>();
        
        // 初始化图结构
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 构建图和入度数组
        for (int i = 0; i < prerequisites.length; i++) {
            int u = prerequisites[i][1];
            int v = prerequisites[i][0];
            graph.get(u).add(v);
            indegree[v]++;
        }
        
        // 使用数组实现队列
        int[] queue = new int[numCourses];
        int l = 0, r = 0;
        
        // 加入入度为0的节点
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue[r++] = i;
            }
        }
        
        int cnt = 0;
        while (l < r) {
            int cur = queue[l++];
            cnt++;
            
            // 遍历当前节点的所有邻接节点
            List<Integer> edges = graph.get(cur);
            for (int i = 0; i < edges.size(); i++) {
                int next = edges.get(i);
                if (--indegree[next] == 0) {
                    queue[r++] = next;
                }
            }
        }
        
        return cnt == numCourses;
    }
    
    private void addEdge(int u, int v, List<List<Integer>> graph, int[] indegree) {
        graph.get(u).add(v);
        indegree[v]++;
    }
    
    private List<Integer> getEdgesFrom(int u, List<List<Integer>> graph) {
        // 返回不可修改的视图，防止外部修改图结构
        return Collections.unmodifiableList(graph.get(u));
    }
}