数据结构-图

• 邻接矩阵:图的邻接矩阵是一种用于表示图的存储结构，其中矩阵的行数和列数都对应于图的顶点，矩阵的元素表示顶点之间的边。在邻接矩阵中，如果顶点i与顶点j之间存在边，则矩阵的第i行第j列（记作aij）处的元素为1（或边的权重），否则为0。
• 邻接表:邻接表是图的一种存储方式，用于表示图中的顶点之间的连接关系。在邻接表中，每个顶点都有一个列表，该列表包含了与该顶点直接相连的所有顶点。
• 十字链表:十字链表是一种存储无向图或正则图的数据结构，它将图中每个顶点的邻接顶点按照字典序排列，并存储到两个列表中，分别称为该顶点的出度和入度列表。
• 邻接多重表:邻接多重表是一种表示无向图或有权图的的数据结构。在这种数据结构中，每个顶点都有一个表，这个表记录了与该顶点相邻的所有顶点以及相邻的边。

public class GraphDemo {
    private Map<String, List<String>> graph;

    public GraphDemo() {
        graph=new HashMap<>();
    }
    //添加节点
    public void addVertices(String name){
        graph.put(name,new ArrayList<>());
    }
    //添加边
    public void addEdge(String startName,String endName){
        if (graph.containsKey(startName)&&graph.containsKey(endName)){
            graph.get(startName).add(endName);
        }else {
            throw new RuntimeException("节点不存在");
        }
    }
    //删除节点
    public void removeVertex(String name){
        if (graph.containsKey(name)){
            List<String> neighbors = graph.get(name);
            for (String neighbor : neighbors) {
                graph.get(neighbor).remove(name);
            }
            graph.remove(name);
        }
    }
    //删除边
    public void removeEdge(String startName,String endName){
        if (graph.containsKey(startName)&&graph.containsKey(endName)){
            graph.get(startName).remove(endName);
            graph.get(endName).remove(startName);
        }
    }
}

• 深度优先搜索(DFS):图的深度优先遍历（Depth-First Traversal）是一种用于遍历图的算法，它沿着一条路径尽可能深入，直到达到最深的顶点，然后回溯，再沿着另一条路径深入。这种算法适用于发现图中环、连通分量等性质,由于每个顶点和每条边都会被访问一次，所以时间复杂度是O(V+E)。。

      public void dfs(String startName){
          //创建栈
          Stack<String> stack = new Stack<>();
          stack.push(startName);
          while (!stack.isEmpty()){
              String vertex = stack.pop();
              System.out.println(vertex+" ");
              List<String> neighbors = graph.get(vertex);
              //遍历邻居节点
              for (String neighbor:neighbors){
                  if (!stack.contains(neighbor)){
                      stack.push(neighbor);
                  }
              }
          }
      }
  

• 广度优先搜索(BFS):广度优先搜索（Breadth-First Search，BFS）是一种用于图遍历或搜索的算法。与深度优先搜索（DFS）沿着一条路径尽可能深入不同，BFS采取一步一个顶点的方式进行搜索，即在每一层尽可能扩散得广,这段代码的时间复杂度是 O(V+E)，其中 V 是顶点的数量，E 是边的数量。。

      public void bfs(String statName){
          Queue<String> queue = new LinkedList<>();
          queue.offer(statName);
          while (!queue.isEmpty()){
              String vetex = queue.poll();
              System.out.println(vetex+"");
              List<String> neighbors = graph.get(vetex);
              for (String neighbor:neighbors){
                  if (!queue.contains(neighbor)){
                      queue.add(neighbor);
                  }
              }
          }
      }
  

• 深度优先搜索的主要应用场景
  • 路径寻找：DFS 可以用来寻找从一个顶点到另一个顶点的路径。
  • 连通分量：DFS 可以用来找到图中的连通分量，即无法通过任何边连接的顶点集合。
  • 环检测：DFS 可以用来检测图中是否存在环。
  • 拓扑排序：DFS 可以用来进行拓扑排序，即对有向图进行顶点排序，使得对于任何一条边 (u, v)，都满足 u 在 v 之前。
• 广度优先搜索的主要应用场景
  • 寻找最短路径：BFS 可以用来寻找从源顶点到其他所有顶点的最短路径。
  • 查找特定距离的顶点：BFS 可以用来查找与源顶点距离为 k 的所有顶点。
  • 连通分量：BFS 可以用来找到图中的连通分量，与 DFS 类似，但 BFS 更适合处理较大的连通分量。
  • 网络延迟：BFS 可以用来计算网络延迟，即从源顶点到其他所有顶点的最短延迟。

• 最小生成树:最小生成树（Minimum Spanning Tree，MST）是一棵包含图所有顶点的树形结构，并且它的边权之和尽可能小。这里的边权是指图中每条边的权重，权重越小说明树的边越短，树的高度也越小，从而整个树的路径长度也越小。
  求最小生成树的问题通常可以通过以下几种算法解决：
  • 普里姆算法（Prim algorithm）:普里姆算法（Prim’s algorithm）是一种用于寻找加权无向图最小生成树的算法。最小生成树是一组边，它们连接了图中的所有顶点，且树中所有边的权值之和最小。
    以下是使用普里姆算法找到最小生成树的步骤：
    1. 创建一个包含所有顶点的集合，以及一个空的最小生成树集合。
    2. 从任意顶点开始，将其加入最小生成树集合中，并将其从所有顶点的集合中移除。
    3. 找到与当前最小生成树集合中顶点相邻的顶点中权值最小的顶点，将其加入最小生成树集合中，并将其从所有顶点的集合中移除。
    4. 重复步骤 3，直到所有顶点都被加入最小生成树集合中。
  • 克鲁斯卡尔算法（Kruskal algorithm）:克鲁斯卡尔（Kruskal）算法是一种用来寻找最小生成树的算法。最小生成树是一棵包含图中所有顶点的树形结构，并且其边的权重之和尽可能小。
    克鲁斯卡尔算法的步骤如下：
    1. 将所有顶点构成若干个互不相交的子集，即每个顶点都是一个独立的连通分量。
    2. 将所有边按权重从小到大排序。
    3. 遍历排序后的边，对于每一条边，如果这条边连接的两个顶点属于不同的连通分量，则将这条边加入到最小生成树中，然后将这两个连通分量合并。
    4. 重复步骤 3，直到所有顶点都属于同一个连通分量。
    5. 此时，图中最小的生成树已经找齐。
  • 算法比较
    普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法在实现的所不同:
    1. 普里姆算法是一种贪心算法，其基本思想是：从一个顶点开始，每次选择与当前连通分量边界上权最小的边，将其加入连通分量中，并更新边界。这个过程会一直进行，直到所有顶点都被包含在连通分量中。克鲁斯卡尔算法是一种基于排序的算法。它首先将所有边按权重从小到大排序，然后遍历排序后的边，对于每一条边，如果这条边连接的两个顶点属于不同的连通分量，则将这条边加入到最小生成树中，然后将这两个连通分量合并。这个过程会一直进行，直到所有顶点都属于同一个连通分量。
    2. 数据结构:普里姆算法使用一个优先队列（最小堆）来存储待处理的边，而克鲁斯卡尔算法使用一个已排序的边列表。
    3. 时间复杂度:普里姆算法的时间复杂度是 O(V^2)，其中 V 是顶点的数量。克鲁斯卡尔算法的时间复杂度是 O(ElogE)，其中 E 是边的数量。在边数量较多时，克鲁斯卡尔算法通常比普里姆算法更快。
    4. 空间复杂度:普里姆算法需要维护一个优先队列，因此其空间复杂度与顶点数量成正比。克鲁斯卡尔算法需要维护一个已排序的边列表，因此其空间复杂度与边数量成正比。
    5. 适用性:普里姆算法适用于稠密图，因为其时间复杂度较低。克鲁斯卡尔算法适用于稀疏图，因为其时间复杂度较高。
  • 应用场景:最小生成树（Minimum Spanning Tree，MST）在许多实际场景中都有广泛应用，以下是一些常见的应用场景：
    • 通信网络设计：在构建通信网络时，需要确保所有节点之间都能互相通信，同时 minimize 总花费（例如，购买光纤、微波塔等）。
    • 路由表优化：在路由器中，最小生成树可以用于优化路由表，从而提高数据传输效率。
    • 图像处理：在图像处理中，最小生成树可以用于图像压缩、图像分割等任务。
• 最短路径:最短路径问题是指在带权重的图中寻找从起点到终点的最短路径。在这个问题中，权重通常表示两点之间的距离或花费。
  • Dijkstra 算法:Dijkstra 算法是一种用于计算图中顶点之间最短路径的算法。它不适用于有负权边的图。算法步骤如下:
    1. 初始化距离数组 dist，将起点到其他所有顶点的距离设为无穷大，将起点到自身的距离设为 0。
    2. 创建一个优先队列（最小堆），将所有顶点及其距离放入队列。
    3. 当队列不为空时，取出队列中距离起点最近的顶点，并将其从队列中移除。
    4. 遍历当前顶点的所有邻接顶点，计算从起点到邻接顶点的距离，如果该距离小于已知的最短距离，则更新最短距离，并将该邻接顶点压入队列。
    5. 重复步骤 3 和 4，直到队列为空。
  • Floyd-Warshall 算法是一种用于计算图中所有顶点之间最短路径的算法。它适用于有负权边的图。以下是 Floyd-Warshall 算法的步骤：
    1. 初始化距离矩阵 dist，将图中所有顶点之间的距离初始化为无穷大，将起点到其他所有顶点的距离设为有向边或无向边的权值,节点到自己的距离为0。
    2. 以三个顶点的有向图为例,先将V[0]作为中间结点若dist[i][j]的值大于dist[i][0]+dist[0][j]则更新dist[i][j]的值.
    3. 以此类推直到所有的节点都遍历一遍.
  • 算法比较
    • 复杂度:Dijkstra 算法的复杂度为 O(V^2)，而 Floyd-Warshall 算法的复杂度为 O(V^3)。
    • 更新最短路径的方式:在 Dijkstra 算法中，我们通过比较顶点的距离值来更新最短路径；在 Floyd-Warshall 算法中，我们通过遍历所有顶点来更新最短路径。
    • 算法实现方式:Dijkstra 算法使用优先队列（最小堆）来存储待处理的顶点，而 Floyd-Warshall 算法使用二维距离矩阵来存储顶点之间的最短距离。
    • 适用性:Dijkstra 算法不适用于有负权边的图，而 Floyd-Warshall 算法适用于有负权边的图。
  • 应用场景
    • 文件传输：在文件传输过程中，需要计算两点之间的最短路径，以便选择最优的传输路径，以提高传输速度和减少传输成本。
    • 网络通信：在网络通信中，需要计算两点之间的最短路径，以便数据包能够以最短的时间从源节点到达目标节点。
    • 算法研究：最短路径问题是一种重要的算法问题，是许多算法研究的基础。在计算机上，可以进行最短路径算法的模拟和优化研究。
    • 游戏设计：在游戏设计中，最短路径问题可以用于计算角色移动的最短路径，以便设计更合理的游戏关卡和路径。
    • 人工智能：在人工智能中，最短路径问题可以用于计算机器人移动的最短路径，以便实现机器人的自主导航和路径规划。
• 拓扑排序
  • 什么是AOV网:AOV（Activity On Vertex）网是一种用顶点表示活动，用边表示活动之间依赖关系的网络。它主要用于表示工程中的任务及其依赖关系，以便进行项目计划和进度控制。在 AOV 网中，每个顶点表示一个活动，每条边表示两个活动之间的依赖关系。例如，活动 A 在活动 B 之前完成，那么在 AOV 网中，从顶点 A 到顶点 B 有一条有向边。
  • 什么是拓扑排序:拓扑排序是对有向无环图的顶点的一种排序,他使得若只存在一条从a到b的路径,那排序中b出现在a的后面.
  • 对aov网排序的步骤
    • 初始化一个队列，用于存储待处理的顶点。
    • 遍历图中的所有顶点，将入度为0的顶点加入队列。
    • 当队列不为空时，取出队列中的顶点，并将其从图中删除。然后，遍历该顶点的所有邻接顶点，将它们的入度减1。如果减1后入度为0，则将该邻接顶点加入队列。
    • 重复步骤3，直到队列为空。
  • 应用场景:
    • 项目计划和进度控制：在项目管理中，可以使用拓扑排序来确定任务的优先级，以便按照合理的顺序完成任务。
    • 网络通信：在网络通信中，可以使用拓扑排序来确定数据包的传输顺序，以便按照合理的路径传输数据。
    • 算法研究：拓扑排序是一种重要的算法问题，是许多算法研究的基础。在计算机科学领域，可以进行拓扑排序的模拟和优化研究。
    • 游戏设计：在游戏设计中，可以使用拓扑排序来确定角色移动的顺序，以便设计更合理的游戏关卡和路径。
• 判断无环图
  • 判断无环图的过程:
    1. 从一个节点出发,遍历所有周围节点,将遍历过的节点加入visited数组和stack栈中
    2. 每次遍历都是将节点和节点的临近节点以此递归下去进行遍历,同时加入stack栈中,若栈在某次递归中包含了某个节点,说明形成了一个闭环,则直接返回false
    3. 否则当所有的临近节点都访问过后将stack栈清楚.
    4. 返回到过程a(因为可能存在其他联通分量)

           //DFS判断无环图
           public boolean dfs(String vetex,Map<String,Boolean> visited,Map<String,Boolean> stack){
               //判断是否包含在栈中
               if (stack.containsKey(vetex)){
                   return true;
               }
               //判断是否被访问过
               if (visited.containsKey(vetex)){
                   return false;
               }
       
               visited.put(vetex,true);
               stack.put(vetex,true);
               for (String neighbor:graph.get(vetex)){
                   if (dfs(neighbor,visited,stack)){
                       return true;
                   }
               }
               stack.remove(vetex);
               return false;
           }
           public boolean hasCycle(){
               //创建记录对象
               HashMap<String,Boolean> visited = new HashMap<>();
               //遍历所有节点
               for (String vetex:graph.keySet()){
                   //如果节点未被访问过
                   if (!visited.containsKey(vetex)){
                       if (dfs(vetex,visited,new HashMap<>())){
                           return true;
                       }
                   }
               }
               return false;
           }
       

   //BFS判断无环图
    public boolean bfs(String vertex,Map<String,Boolean> visites,Queue<String> queue){
        visites.put(vertex,true);
        queue.add(vertex);
        while (!queue.isEmpty()){
            String current=queue.poll();
            for (String neighbor:graph.get(current)){
                //若没访问过
                if (!visites.containsKey(neighbor)){
                    visites.put(neighbor,true);
                    queue.add(neighbor);
                //已经访问过
                }else {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean hasCycle2(){
        HashMap<String,Boolean> visited = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        for (String vertex:graph.keySet()){
            if (!visited.containsKey(vertex)){
                if (bfs(vertex,visited,queue)){
                    return true;
                }
            }
        }
        return false;
    }

• 关键路径
  • AOE网:AOE（Activity On Edge）网是一种用于表示活动及其依赖关系的图。它通过边表示活动，通过顶点表示活动之间的依赖关系。AOV网的边无权值,AOE网的边有权值.
  • 关键路径,关键活动:把具有最大路径长度的路径称为关键路径,而把关键路径上的活动称为关键活动.

• 社交网络：图可以用来表示社交网络中的用户及其之间的关系。例如，Facebook 使用图结构来存储用户及其好友之间的关系，以便快速推荐可能认识的人、找到共同好友等。
• 推荐系统：图可以用来表示用户与物品之间的交互关系，例如用户购买商品、给商品打分等。通过分析这些关系，可以构建推荐系统，为用户提供个性化的推荐。
• 地图导航：图可以用来表示地图上的道路网络，节点表示道路交叉点，边表示道路连接。通过使用图数据结构，可以实现地图导航功能，例如计算最短路径、推荐路线等。
• 知识图谱：图可以用来表示实体（如人物、地点、组织等）及其之间的关系。例如，Google 的 Knowledge Graph 就是一个大规模的知识图谱，用于提供关于实体及其关系的详细信息。
• 机器学习：图在机器学习中用于表示数据集中的对象及其之间的关系。例如，图神经网络（GNN）是一种针对图数据的深度学习模型，可以用于学习图上的特征，并用于预测和分类。