图与树的主要区别在于：树是一对多的关系；图是多对多的关系。
若要保证有n个结点的无向图是连通的，则最少的方法就是形成一颗树，即N-1条边连接。

图的存储方式

邻接矩阵：

即使用二维数组来表示各个顶点之间的关系：若A[i][j] = 1,表示节点i 与节点j之间有边。

易知：

无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是对称的。

当图G用邻接矩阵A表示时，顶点的度可以表示为：

有权图：

即：

A[i][j] = inf ,表示i与j之间无边；

A[i][j] = w,  表示i与j之间边权重为w；

A[i][j] = 0,  表示i=j；

邻接表：

无向图的邻接表：

即将从一个点发出的所有边表示在同一个边链表之中。

边链表中的每一个点代表每一条边，存储与之相连的节点与这条边的link
即邻接表所占空间大小与顶点数和边数均有关。

有向图的邻接表：

有向图中对于每一个顶点所发出的边，分为入边表和出边表分别存储。

图的遍历：

图的遍历通常会设置辅助数组visiter[]，用来保证每个节点均访问一次。

图的遍历主要分为dfs和bfs两种。

dfs:

基本流程：

从一个初始顶点出发，访问它的任一邻接节点W1，再从W1出发，访问W1的任一邻接节点，直至到达一个顶点M，满足M的所有邻接顶尖均被访问过。

然后再回退一步，访问前一个节点中没被遍历到的邻接节点。

算法上通常采用递归实现
dfs可以用来判断图中是否有环。

非递归dfs实现：

核心思想：从起点开始，先加入所有满足条件的邻居节点入栈，再对于每一个栈首元素进行深度遍历。这种方式下，每一次的出栈操作，就实现了切换到父节点的另一子节点的操作。
同时若采用邻接矩阵存储，还需要注意应该倒着入栈，以保证与dfs相同的顺序。

void dfs(int start, int n, vector<vector<int>> &edges, vector<bool> &visited)
{
    stack<int> s;
    s.push(start);
    visited[start] = true;
    while (!s.empty())
    {
        int node = s.top();
        s.pop();
        cout << node << " ";
        for (int neighbor : edges[node])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = true;
                s.push(neighbor);
            }
        }
    }
}

bfs：

基本流程：
从起始顶点出发，依次访问起始顶点的所有邻接顶点。再从这些邻接顶点出发，各个依次再访问它们的邻接顶点。
即是一种逐层遍历，搜索的流程。
通常采用队列实现。

连通分量：

非连通图的极大连通子图叫做连通分量。
一个连通图的极小连通子图叫做生成树。在n个顶点中有n-1条边。
连通分量的个数：
一个具有n个顶点的图，最少有1个连通分量——构成完全图，最多有n个连通分量——每一个点均为孤立。
弧与路径的区别：
弧——在有向图中，从一个顶点到另一个顶点的有向边称为弧。
路径——途中顶点到另一个顶点的两桶序列，即可以分为多步迁移。

有向图中的分类：

• 强连通图与强连通分量：
  在有向图中，若对于每一对顶点i和j，都存在一条从i到j和从j到i的路径，则称此图为强连通图。非强连通图的极大强连通分量陈伟强连通分量。
• 强连通图与强连通分量：
  在有向图中，若将所有有向边视作无向边后，若得到的无向图是连通的，则称原图为弱连通图。

常见题型：

1，若已知无向图G有N个顶点，则保证图G是连通的，至少需要多少条边：
——先构成N-1完全图，将第N个顶点连接任意一条边，则即可构成最少的边数。

2，用n个顶点沿同一方向连接形成一个环时，就构成了需要边最少的强连通图。

最小生成树：

• 仅仅针对于无向图；

• 使用且仅能使用n-1条边【PS：若图中有多个最小生成树，则表示图的变数一定大于n-1】

• 包含了所有的顶点；

• 符合树的定义：连通，无环。

• 最小：使得边权相加的结果最小。

• 最小的代价是唯一固定的。

• 不一定包括全部的最小权边——避免形成环。
  最短路径树与源起点紧密相关；而最小生成树是一个全局概念，与从何处开始无关。

切割属性：

对于图集(V,  E)，将V个点分给两个非空集合，构成两个点集S，(V - S)。

切割属性的定义：

跨越连接两个点集的最小权重边必然包含于最小生成树中。

证明：
设最小生成树T不包含最小权重边S = (u, v)。取而代之的是F边。

1. 现在构造一颗新的生成树T‘：
2. 从T中移除F边；
3. 然后加入我们讨论的最小权重边S；
   现在T’的总权重 = T的总权重 - weight(F) + weight(S);
   又因为weight(S) < weight(F)。故有T’的总权重小于T的总权重。
   但我们假设的是T未最小生成树，故与题意相违背。
   接下来介绍几种查找MST的算法：

Prim算法：

核心思想：

在每一步，逐步连接当前已在MST中的顶点与尚未在MST中的顶点集合间的最小权重边，直至所有顶点都在MST中。

算法流程：

两个关键数组：

dist数组：维护每个顶点到当前MST集合的最小边权重；
(注意此点与dijkstra算法的区别，dikstra算法是维护到起点单点的最短距离，prim算法维护的是到MST集合的距离。但代码其余部分基本与dijkstra算法相似)

parent数组：记录每个新节点加入后是和哪个节点相连的；

typedef pair<int, int> PII; //(distance, node)

void prim(int start int V){
 memset(dist, int, sizeof dist);
 memset(parent, -1, sizeof parent);
 bool inMST[N];
 memset(inMST, false, sizeof inMST);
 dist[start] = 0;
 priority_queue<PII, vector<PII>, greater<PII>> pq;
 pq.push({0, start});
 while(pq.size()){
   //选取当前对MST集合距离最近的点，贪心的体现。
   int cur_node = pq.top().second;
   pq.pop();
   if(inMST[cur_node]) continue;
   inMST[cur_node] = true;
   for(auto& neighbor: graph[cur_node]){
      int v = neighbor.first;
      int weight = neighbor.second;
      //不在MST中，且找到了更小权边。
      if(!inMST[v] && weight < dist[v]){
         dist[v] = weight;
         parent[v] = u;
         pq.push({dist[v], v});
      }
   }
 }
}

时间复杂度分析：

• 初始化：O(V);

• push操作：O（VlogV）[优先队列是基于二叉堆实现的]

• pop操作：O (VlogV)

• 遍历相连边：O(E)

• push更新操作：O（ElogV)

故总复杂度为：O((V + E) logV)

Kruskal算法：

核心思想：

• 将图中的所有边按权重从小到大进行排序；

• 从权重最小的边开始，一次考虑每一条边；

• 若加入当前的环会与已选择的边之间形成环，则跳过；

• 当已选边数 = 顶点数 - 1时，停止循环。

数据结构实现基础(并查集)：

并查集用来判断两个顶点是否连通，以及用来合并两个连通分量。
主循环流程：

• 取出最小权重边；
• 检查环(使用并查集的find函数):
  • 若根节点相同，说明u与v已经连通，加入会构成环；
  • 若根节点不同，说明不在同一连通快，可以加入；
• 合并：
  • 加入MST集合；
  • 使用union操作，将u和v的集合合并。
• 结束：
  当MST集合中包含V - 1条边时，结束。
  代码实现：

struct Edge{
 int u, v, weight;
 bool operator<(const Edge& other){
   return weight < other.weight;
 }
};

int find(int x){
 if(parent[x] != x){
   parent[x] = find(parent[x]);
 }
 return parent[x];
}

void union(int x, int y){
  int rootx = find(x);
  int rooty = find(y);
  parent[rootx] = rooty;
}

int kruskal(int V, vector<Edge>& edges){

  //先对边权排序

  sort(edges.begin(), edges.end());

  //初始化并查集相关数组

  for(int i = 0; i < V; ++i){

     parent[i] = i;

     rank_[i] = 0;

  }

  int mstweight = 0;

  int usededges = 0;

  for(Edge& e: edges){

     if(usededges == V - 1){

        break;

     }

     int rootU = find(e.u);

     int rootV = find(e.v);

     if(rootU != rootV){ //合并

       union(rootU, rootV);

       mstweight += e.weight;

       usededges ++;

     }

  }

  return mstweight;

}

时间复杂度分析：

由于压缩路径后的并查集操作均为反阿克曼函数，均可视为常数
故主要是排序的O(ElogV);

最短路径：

Dijkstra算法：(边权非负的单源最短路径问题)

算法步骤：

1，创建优先级队列；
2，将起点s以优先级0加入priority_queue;
​      将其他所有点以优先级inf加入priority_queue;
3，当队列不为空时，弹出顶点，并松弛从顶点出发的所有边。

核心思想：

贪心算法+松弛操作；
1，全局的最优路径可以不断地通过局部最优路径累计得到；
​    原理：当目前弹出的顶点是V1，说明V1目前是距离start最近的点。若后续操作中V1到start的距离可以被进一步更新，则说明必定存在V2到start的距离更短，前后相矛盾。
2，松弛操作：通过不断更新和改进估计的距离最优值，逼近最优策略；
​    具体：记现在的dist[now]为最佳距离，遍历当前队列弹出的顶点ver的所有边，检查是否有dist[ver] + weight[ver] [now] < dist[now]，然后用来更新dist[now]的值。
NOTICE: 我们不会再用其他顶点来松弛已访问过的顶点的，因为它的最短距离已经确定过了，无需再次更新。

代码框架实现：

typedef pair<int, int> PII;  //(distance, node)

vector<vector<PII>> graph;

bool st[N];

void dijkstra(int s, vector<int>& dist){
   int n = graph.size();
   for(int i = 0; i < n;++i){
      dist[i] = inf;
   }
   dist[s] = 0;
   priority_queue<PII, vector<PII>, greater<PII>> pq;
   pq.push({0, s});
   while(pq.size()){
     int node = pq.top().second;
     int dis = pq.top().first;
     pq.pop();
     if(st[node]) continue;
     st[node] = true;
     for(int i = 0; i < graph[node].size(); ++i){
       int cur_node = graph[node][i].second;
       int cur_weight = graph[node][i].first;
       if(dist[node] + cur_weight < dist[cur_node]){
          dist[cur_node] = dist[node] + cur_weight;
          pq.push({dist[cur_node], cur_node});
       }
     }
   }
}

时间复杂度：
由于使用了优先队列，故时间复杂度为O((V+E)logV)。

特殊情况：

当出现负权边时，该算法不成立。因为负权边的存在使得 **”““当前弹出的点的最小距离不会再次改变”“**这点不成立。因为有可能前半段距离很长，但突然经过一个负权边补偿后，举例又变小。

A*算法：

A 本质上是Dijkstra的一种启发式改进。如果说Dijkstra算法是一种从source以同心圆的形式逐步一圈圈向外扩散。那么A 算法则是给定一个大致的前进方向，大大缩减了需要遍历检查的节点数量。

核心思想：

为每一个节点计算一个代价函数F(n)，并以代价函数作为优先级来比较。
F(n) = G(n) + H(n);

• G(n)：从起始点到当前节点的准确距离；

• H(n)：从当前节点n到目标节点的预估成本。通常采用直线距离或曼哈顿距离。

• F(n)：通过节点n的路径的预估总成本。

具体代码框架：

typedef pair<double, int> PII;  //(f_score, 节点)

vector<vector<PII>> graph;

bool st[N];

int g[N];

int came_from[N];

double get_dist(int a, int b){

  return num ;  //结合具体计算直线距离...

}

void A_star(int start, int goal, vector<int>& path){

    int n = graph.size();

    memset(g, inf, sizeof g);

    memset(came_from, -1, sizeof came_from);

    g[start] = 0;

    double f_score = g[start] + get_dist(start, goal);

    priority_queue<PII, vector<PII>, greater<PII>> pq;

    pq.push({f_score, start});

    while(pq.size()){

       double current_f = pq.top().first;

       int node = pq.top().second;

       pq.pop();

       if(st[node]) continue;

       st[node] = true;

       //记录路径

       if(node == goal){

          path.clear();

          for(int node = goal; node != -1; node = came_from[node]){

             path.push_back(node);

          }

          reverse(path.begin(), path.end());

          return;

       }

       for(int i = 0; i < graph[node].size(); ++i){

          int edge_weight = graph[node][i].first;

          int neighbor = graph[node][i].second;

          if(st[neighbor]) continue;

          if(g[node] + edge_weight < g[neighbor]){

             g[neighbor] = g[node] + edge_Weight;

             double f_score = g[neighbor] + get_dist(neighbor, goal);

             pq.push({f_score, neighbor});

          }

       }

    }

    path.clear();

}

注意：A*算法同样无法处理负权边的图。

拓扑排序：

假设有一系列的任务，某些任务必须在某个任务完成后才能进行，怎样对这些任务的执行进行排序？

将这些任务视为一个图，每个节点代表一个任务，V ---> W表示任务V必须在W前完成。则问题转换为找到这张图的拓扑排序：
拓扑排序只有对于有向，无环的图有效。称有向无环图为DAG，或者称为AOV网络；

如何对AOV网络进行拓扑序列化：

对于任何拓扑排序，都可以将图线性化。
上述 DAG 的拓扑排序必须以 D 或 E 开头，并且必须以 F 或 C 结尾。因此，D 和 E 称为源，F 和 C 称为汇。

基本步骤：

1. 输入网络，令n为顶点个数
2. 在网络中选出一个没有直接前驱的顶点，并输出
3. 删去该节点，并删去其发出的所有边
4. 重复2，3步骤，直到：
   • 全部顶点均已输出；
   • 图中还有顶点剩余，但循环已结束，则说明存在有向环

计算拓扑排序的算法：

拓扑排序的算法求解一般为O(N + E),

基于DFS：

基于DFS的拓扑算法实际上是逆后序遍历。
树的逆后序遍历恰好是：根节点排在两个子节点的后面，故翻转过来即符合拓扑排序的要求。

基于BFS：

int h[N], e[N], ne[N], idx;
int in[N]; //存储各节点的入度
int cnt; //存储队列中的元素个数
int top[N]; //存储队列中的元素

void add(int a, int b){ //添加a -> b的边
  e[idx] = b;
  ne[idx] = h[a];
  h[a] = idx++;
}

bool topsort(){
  queue<int> q{
  for(int i = 1; i <= n; ++i){
     if(!in[i]) q.push(i);  //先将入度为0的点加入队列中。
  }
  while(q.size()){
     auto t = q.front(); //先一个个以从源点开始
     top[++cnt] = t;
     q.pop();
     for(int i = h[t]; i != -1; i = ne[i]){
        int j = e[i];

        in[j] --;  //这条边标记一次，直至其入度为0时，入队
        if(!in[j]) q.push(j);

     }
  }
  return cnt == n;  //可以判断该图是否为DAG
}

基于拓扑排序的寻找带负权边的DAG最短路：

一般Dijkstra算法无法解决负权边问题在于，提前已经假设好了某一点的最短路径，不容许改变。而拓扑排序则保证了在遍历到节点V之前，若路径上含有负权边，则一定被提前考虑过了。
其余则按照拓扑顺序逐条松弛出边即可：

vector<int> shorestPath(int source){
  vector<int> tpOrder = tpsort();//拓扑顺序
  vector<int> dist(V, INF);
  dist[source] = 0;
  
  for(int u: tpOrder){
    if(dist[u] != INF){
       for(auto &edge: adj[u]){
         int v = edge.first;
         int weight = edge.second;
         if(dist[v] > dist[u] + weight){
           dist[v] = dist[u] +weight;
         }
       }
    }
  
  return dist;
}

时间复杂度：
由于普通排序代替为拓扑排序——O(V+E)。
故DAG中的最短路径算法时间复杂度为O(V+E)。

DAG上的最长路径：

即将DAG的边权重全部取为负数。再运行一次上述的最短路算法，将结果取负即可。

拓扑的实际应用题解：

图的排序：

进行图的排序，需要考虑三点：

• 当排序相矛盾时，即图有环。即部分点的入度永不为0，永远不会入队，即拓扑遍历到的点小于总点数N；

• 当排序不唯一时，即每一次入度为0，入队的点数不唯一；

• 余下状况即为正常情况。

• 注意，状况的判断也有顺序：最好避免中途退出，在结尾处统一判断成环，多解，唯一解的状况。

int topsort(){
      int in_test[N] = {0};  
memset(top, 0, sizeof top);  
memcpy(in_test, in, sizeof in);  
queue q;  
bool multiple = false;     //设置多解的状态

      for (int i = 1; i <= n; ++i){  
if(!in_test[i]) q.push(i);  
}

      if(q.size() > 1) multiple = true;  
int cnt = 0;  
while(q.size()){  
  auto t = q.front();  
  top[++cnt] = t;  
  q.pop();  
  int temp = 0;  
  for (int i = h[t]; i != -1; i = ne[i]){  
    int j = e[i];  
    in_test[j]--;  
    if(!in_test[j]){  
      q.push(j);  
       temp++;  
     }  
  }

      if(temp > 1) multiple = true;    //每次入队都要判断。  
}

      if(cnt < kind_cnt)  // 有环  
        return -1;
      if(multiple)    // 多解  
        return 0;  
return 1;   // 唯一解  
}

拓扑建图的层次分解：

在利用拓扑排序将平面图线性化的过程中，根据比较关系，往往可以将各个点分为若干类别。也可以理解为正是不同类别中的点互相连接才构成了对应的拓扑图。

相较于标准拓扑关注节点的排序，此类问题还关注层次深度。
具体应用主要见于火车停靠站等级划分问题：求出最长等级链。

那么我们应该如何分解出对应的层次划分呢？这里介绍对于点，边的分解方法：

基本思路：

• 分析题意的依赖关系，建图；

• 记录下每一轮中没有”前置依赖“(入度归0)的节点;

• 删除这个节点与对应的边关系;

• 层级计数器加1；

对于火车停靠站等级划分问题的示例：

规则：

• 有n个火车站，m条火车线路

• 每条线路停靠部分站点

• 规则：如果某站点在线路中停靠，而另一站点不停靠，则停靠站等级高于非停靠站

• 目标：找出最严格的等级划分，即最长等级链

void topu(){

    int top = 0, tt[N] = {0};
    int bo[N] = {0};
    memset(bo, 0, sizeof bo);
    memset(tt, 0, sizeof tt);
    do{
        top = 0;

        for (int i = 1; i <= n; ++i){
            if(!in[i] && !bo[i]){
                tt[++top] = i;
                bo[i] = 1;  //避免对于一个节点重复拆解
            }
        }
        for (int i = 1; i <= top; ++i){

            int t = tt[i];

            for (int j = 1; j <= n; ++j){

                if(tuopu[t][j]){
                
                    tuopu[t][j] = 0;

                    in[j]--;
                    
                }

            }
            
        }

        ans++;

    } while (top);

}
```c++
int main(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int s;
        cin >> s;
        int st[N] = {0};
        int is_stop[N];
        memset(is_stop, 0, sizeof is_stop);
        for (int i = 1; i <= s; ++i){
            cin >> st[i];
            is_stop[st[i]] = 1;
        }
        //建立 非停靠站 -> 停靠站 之间的关系。 非停站一定小于停靠站。【注意范围是始发与终点站之间的节点】
        for (int j = st[1]; j <= st[s]; ++j){
            if(!is_stop[j]){
                for (int k = 1; k <= s; ++k){
                    if(!tuopu[j][st[k]]){  // 还未建立关系。[tuopu[i][j]--> j的等级 > i的等级]
                        tuopu[j][st[k]] = 1;
                        in[st[k]]++;
                    }
                }
            }
        }
    }
    topu();
    cout << ans - 1<< endl;
    return 0;

}

关键路径：

基本背景：

在无有向环的带权有向图中，用有向边表示一个活动，用边上权值表示活动的持续时间，顶点表示事件。则这样的网络，称为AOE网络。
从源点到汇点的有向路径有多条，只有完成所有路径上的活动才能完成整个工程。

故完成整个工程所需要的时间取决于从源点到汇点的最长路径长度。这条路径长度最长的路径称作关键路径。

解决思路：

要找到关键路径，就需要找到关键活动——不按期完成就会影响整个工程完成的活动。
关键路径上的所有活动都是关键活动。
变量设置如下：

• 事件的最早开始时间ee(i)——从源点到顶点的最长路径长度；
• 事件的最迟允许开始时间le(i)——在保证在ee[n-1]时刻完成的前提下，le[i] = ee[n] - 顶点i到顶点n的最长路径长度。
• 活动的最早可能开始时间e[k]——假设活动在边<, >上，则就有e[i] = ee[j]。
• 活动的最迟允许开始时间l[i]——l[i] = le[k] - cost<i, j>。
• 时间余量——即活动的最早开始时间和最迟允许开始时间。

关键活动即是：l[i] = e[i]的活动。
时间余量含义：
1，若关键活动拖延时间，则整体工程也需要拖延时间。
2，l[i] - e[i]即是在不增加工程总时间的前提下，该活动可以拖延的时间
3，若l[i] - e[i] > 0，即使提前完成的时间小于等于l[i] - e[i]，也不能加快整体进程。
在执行时，所有顶点都是按照拓扑排序编号的。

算法实现如下：

void criticalPath(Graph <Type> &G){
   int i, j, k;
   float e, l, w;
   int n = G.NumberOfVertices();
   float *ee = new float[n];
   float *le = new float[n];
   for(i = 0; i < n; ++i) ee[i] = 0;
  // 1. 正向计算最早时间 ee （按拓扑序）
   for (i = 0; i < n; i++) {
       int u = topoOrder[i]; // 按拓扑序取出顶点
       for (每个从u出发的邻接点v) {
           w = weight<u, v>;
           if (ee[u] + w > ee[v]) {
               ee[v] = ee[u] + w; // 更新ee[v]为最大值
           }
       }
   }
   // 2. 初始化并逆向计算最晚时间 le （逆拓扑序）
   for (i = 0; i < n; i++) le[i] = ee[汇点]; // 全部初始化为项目总工期
   for (i = n-2; i >= 0; i--) { // 逆拓扑序循环
    int u = topoOrder[i];
    for (每个从u出发的邻接点v) {
        w = weight<u, v>;
        if (le[v] - w < le[u]) {
            le[u] = le[v] - w; // 更新le[u]为最小值
        }
    }
  }
   // 3. 遍历所有边，识别关键活动
   for (每条边<u, v>， 权重为w) {
       e = ee[u];          // 活动<u,v>的最早开始时间
       l = le[v] - w;      // 活动<u,v>的最晚开始时间
       if (e == l) {       // 时差为0，是关键活动
           cout << u << ", " << v << " 是关键活动" << endl;
       }
   }
}