当前位置： 首页 > article >正文

图结构与高级数据结构的学习笔记一

article 2024/11/14 9:15:30

  • 学习内容:

    • 图（Graph）：
      • 图的基本概念、表示方法（邻接矩阵、邻接表）。
      • 图的遍历（深度优先搜索DFS、广度优先搜索BFS）。
    • 最短路径算法：
      • Dijkstra算法、Bellman-Ford算法的理解与实现。
    • 最小生成树（MST）：
      • Kruskal算法、Prim算法的理解与实现。

  • 实践:

    • 实现图的基本操作和遍历算法。
    • 用Dijkstra算法解决最短路径问题，理解其在现实世界中的应用。
1. 图的基本概念
  • 定义: 图由**顶点（Vertex）和边（Edge）**组成。顶点表示图中的对象，边表示对象之间的关系。
  • 分类:
    • 有向图: 边有方向性，表示从一个顶点到另一个顶点的单向连接。
    • 无向图: 边没有方向性，表示两个顶点之间的双向连接。
  • 图的度:
    • 出度（Out-degree）: 从某顶点出发的边的数量。
    • 入度（In-degree）: 指向某顶点的边的数量。
2. 图的表示方法

  • 邻接矩阵（Adjacency Matrix）:

    • 用一个二维数组表示图。如果顶点 i 到顶点 j 有边，则矩阵中的元素为 1（或边的权重），否则为 0。
    • 优点: 快速检查两个顶点是否有边。
    • 缺点: 对于稀疏图，浪费空间。

  • 邻接表（Adjacency List）:

    • 每个顶点有一个链表（或数组），链表中存储与该顶点相邻的顶点。
    • 优点: 节省空间，特别是对于稀疏图。
    • 缺点: 检查两个顶点是否有边比较慢。
3. 图的遍历

  • 深度优先搜索（DFS）:

    • 类似于树的先序遍历，沿着每个分支走到底，再回溯到上一个顶点，继续探索其他未访问的分支。
    • 实现: 使用栈（可以通过递归实现）。
    • 时间复杂度: O(V + E)，其中 V 是顶点数，E 是边数。

  • 广度优先搜索（BFS）:

    • 类似于树的层序遍历，逐层探索图中的顶点。
    • 实现: 使用队列。
    • 时间复杂度: O(V + E)。

最短路径算法

  • Dijkstra算法:

    • 解决单源最短路径问题，即从一个顶点到所有其他顶点的最短路径。
    • 特点: 适用于边权重非负的图。
    • 实现步骤:
      1. 初始化源点的距离为 0，其他顶点的距离为无穷大。
      2. 使用优先队列选择当前距离最小的顶点。
      3. 更新该顶点相邻顶点的最短距离。
      4. 重复直到所有顶点都被处理。
    • 时间复杂度: O(V^2)，使用优先队列优化可降至 O(E + V log V)。

  • Bellman-Ford算法:

    • 解决单源最短路径问题，允许边权重为负。
    • 特点: 可以检测负权重环。
    • 实现步骤:
      1. 初始化源点的距离为 0，其他顶点的距离为无穷大。
      2. 进行 V-1 轮松弛操作，更新所有边的最短路径。
      3. 第 V 轮检查是否存在负权重环。
    • 时间复杂度: O(VE)。

最小生成树（MST）算法

  • Kruskal算法:

    • 寻找加权无向图的最小生成树。
    • 特点: 基于贪心策略，每次选择权重最小的边，直到构建出最小生成树。
    • 实现步骤:
      1. 将图中的边按权重从小到大排序。
      2. 初始化一个空树，并逐一检查排序后的边，若加入边不会形成环，则将其加入生成树。
      3. 重复直到树中包含所有顶点。
    • 时间复杂度: O(E log E)。

  • Prim算法:

    • 寻找加权无向图的最小生成树。
    • 特点: 也是基于贪心策略，从任意顶点出发，每次选择权重最小的连接新顶点的边。
    • 实现步骤:
      1. 从任意顶点开始，将其加入生成树。
      2. 在所有连接生成树的边中选择权重最小的边，并将对应顶点加入生成树。
      3. 重复直到生成树包含所有顶点。
    • 时间复杂度: O(V^2)，使用优先队列优化可降至 O(E + V log V)。

实践

  1. 图的基本操作和遍历算法:

    • 实现图的邻接矩阵和邻接表表示方法。
    • 编写DFS和BFS的实现代码，测试图的遍历效果。

  2. 最短路径问题:

    • 实现Dijkstra算法，使用该算法求解实际问题，如计算城市间的最短路径。
    • 理解Bellman-Ford算法，并使用其处理可能存在负权重的路径问题。

  3. 最小生成树:

    • 使用Kruskal和Prim算法实现最小生成树，应用于网络设计、基础设施规划等实际场景中。

实践代码

1. 图的基本操作和遍历算法
邻接矩阵和邻接表的表示

邻接矩阵表示:

class GraphMatrix {
    private int[][] adjMatrix;
    private int numVertices;

    public GraphMatrix(int numVertices) {
        this.numVertices = numVertices;
        adjMatrix = new int[numVertices][numVertices];
    }

    public void addEdge(int src, int dest) {
        adjMatrix[src][dest] = 1;
        adjMatrix[dest][src] = 1;  // 如果是有向图，这一行可以去掉
    }

    public void printMatrix() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

邻接表表示:

import java.util.LinkedList;

class GraphList {
    private LinkedList<Integer>[] adjList;
    private int numVertices;

    public GraphList(int numVertices) {
        this.numVertices = numVertices;
        adjList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int src, int dest) {
        adjList[src].add(dest);
        adjList[dest].add(src);  // 如果是有向图，这一行可以去掉
    }

    public void printList() {
        for (int i = 0; i < numVertices; i++) {
            System.out.print("Vertex " + i + ":");
            for (Integer node : adjList[i]) {
                System.out.print(" -> " + node);
            }
            System.out.println();
        }
    }
}
DFS 和 BFS 的实现

DFS 实现:

import java.util.*;

class DFS {
    private boolean[] visited;

    public DFS(int numVertices) {
        visited = new boolean[numVertices];
    }

    public void dfs(int vertex, LinkedList<Integer>[] adjList) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (int adjVertex : adjList[vertex]) {
            if (!visited[adjVertex]) {
                dfs(adjVertex, adjList);
            }
        }
    }
}

BFS 实现:

import java.util.*;

class BFS {
    private boolean[] visited;

    public BFS(int numVertices) {
        visited = new boolean[numVertices];
    }

    public void bfs(int startVertex, LinkedList<Integer>[] adjList) {
        Queue<Integer> queue = new LinkedList<>();
        visited[startVertex] = true;
        queue.add(startVertex);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");

            for (int adjVertex : adjList[vertex]) {
                if (!visited[adjVertex]) {
                    visited[adjVertex] = true;
                    queue.add(adjVertex);
                }
            }
        }
    }
}
测试图的遍历效果
public class Main {
    public static void main(String[] args) {
        // 使用邻接表表示图
        GraphList graph = new GraphList(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 4);

        System.out.println("邻接表表示:");
        graph.printList();

        DFS dfsTraversal = new DFS(5);
        System.out.print("\nDFS Traversal: ");
        dfsTraversal.dfs(0, graph.adjList);

        BFS bfsTraversal = new BFS(5);
        System.out.print("\nBFS Traversal: ");
        bfsTraversal.bfs(0, graph.adjList);
    }
}
2. 最短路径算法
Dijkstra算法实现
import java.util.*;

class Dijkstra {
    private int[] dist;
    private boolean[] visited;
    private int numVertices;

    public Dijkstra(int numVertices) {
        this.numVertices = numVertices;
        dist = new int[numVertices];
        visited = new boolean[numVertices];
        Arrays.fill(dist, Integer.MAX_VALUE);
    }

    public void dijkstra(int[][] graph, int startVertex) {
        dist[startVertex] = 0;

        for (int i = 0; i < numVertices; i++) {
            int u = selectMinVertex();
            visited[u] = true;

            for (int v = 0; v < numVertices; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        printSolution();
    }

    private int selectMinVertex() {
        int minDist = Integer.MAX_VALUE;
        int vertex = -1;

        for (int i = 0; i < numVertices; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                vertex = i;
            }
        }

        return vertex;
    }

    private void printSolution() {
        System.out.println("Vertex\tDistance from Source");
        for (int i = 0; i < numVertices; i++) {
            System.out.println(i + "\t\t" + dist[i]);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[][] graph = {
            {0, 10, 0, 5, 0},
            {0, 0, 1, 2, 0},
            {0, 0, 0, 0, 4},
            {0, 3, 9, 0, 2},
            {7, 0, 6, 0, 0}
        };

        Dijkstra dijkstra = new Dijkstra(5);
        dijkstra.dijkstra(graph, 0); // 从顶点0开始
    }
}
Bellman-Ford算法实现
class BellmanFord {
    private int[] dist;
    private int numVertices;

    public BellmanFord(int numVertices) {
        this.numVertices = numVertices;
        dist = new int[numVertices];
        Arrays.fill(dist, Integer.MAX_VALUE);
    }

    public void bellmanFord(int[][] edges, int startVertex) {
        dist[startVertex] = 0;

        for (int i = 0; i < numVertices - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0];
                int v = edge[1];
                int weight = edge[2];

                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];

            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                System.out.println("图中包含负权重环");
                return;
            }
        }

        printSolution();
    }

    private void printSolution() {
        System.out.println("Vertex\tDistance from Source");
        for (int i = 0; i < numVertices; i++) {
            System.out.println(i + "\t\t" + dist[i]);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[][] edges = {
            {0, 1, -1}, {0, 2, 4},
            {1, 2, 3}, {1, 3, 2},
            {1, 4, 2}, {3, 2, 5},
            {3, 1, 1}, {4, 3, -3}
        };

        BellmanFord bellmanFord = new BellmanFord(5);
        bellmanFord.bellmanFord(edges, 0); // 从顶点0开始
    }
}
3. 最小生成树
Kruskal算法实现
import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

class Kruskal {
    private int[] parent;
    private int numVertices;

    public Kruskal(int numVertices) {
        this.numVertices = numVertices;
        parent = new int[numVertices];
        for (int i = 0; i < numVertices; i++) {
            parent[i] = i;
        }
    }

    public void kruskal(List<Edge> edges) {
        Collections.sort(edges);

        List<Edge> mst = new ArrayList<>();
        for (Edge edge : edges) {
            int srcParent = find(edge.src);
            int destParent = find(edge.dest);

            if (srcParent

 != destParent) {
                mst.add(edge);
                parent[srcParent] = destParent;
            }
        }

        printSolution(mst);
    }

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

    private void printSolution(List<Edge> mst) {
        System.out.println("Edge\tWeight");
        for (Edge edge : mst) {
            System.out.println(edge.src + " - " + edge.dest + "\t" + edge.weight);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));

        Kruskal kruskal = new Kruskal(4);
        kruskal.kruskal(edges);
    }
}
Prim算法实现
import java.util.*;

class Prim {
    private int[] key;
    private boolean[] mstSet;
    private int[] parent;
    private int numVertices;

    public Prim(int numVertices) {
        this.numVertices = numVertices;
        key = new int[numVertices];
        mstSet = new boolean[numVertices];
        parent = new int[numVertices];
        Arrays.fill(key, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);
    }

    public void prim(int[][] graph) {
        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < numVertices - 1; count++) {
            int u = selectMinKeyVertex();
            mstSet[u] = true;

            for (int v = 0; v < numVertices; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        printSolution();
    }

    private int selectMinKeyVertex() {
        int minKey = Integer.MAX_VALUE;
        int vertex = -1;

        for (int v = 0; v < numVertices; v++) {
            if (!mstSet[v] && key[v] < minKey) {
                minKey = key[v];
                vertex = v;
            }
        }

        return vertex;
    }

    private void printSolution() {
        System.out.println("Edge\tWeight");
        for (int i = 1; i < numVertices; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + key[i]);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0}
        };

        Prim prim = new Prim(5);
        prim.prim(graph);
    }
}

总结

以上Java代码分别实现了图的邻接矩阵和邻接表表示、DFS和BFS遍历算法、Dijkstra和Bellman-Ford最短路径算法，以及Kruskal和Prim最小生成树算法。


http://www.kler.cn/a/283292.html

相关文章：

  • 《情商》提升：增强自我意识，学会与情绪共处
  • Linux 进程线程间通信总结
  • 监控录音如何消除杂音？降低录音噪音的五个技巧
  • 实战指南：理解 ThreadLocal 原理并用于Java 多线程上下文管理
  • 无插件H5播放器EasyPlayer.js网页web无插件播放器vue和react详细介绍
  • redis实现消息队列的几种方式
  • 语言的数据访问
  • 高性能4G灯杆网关,未来智慧城市的神经中枢
  • 【LeetCode面试150】——54螺旋矩阵
  • React Hooks 的高级用法
  • LuaJit分析（八）LuaJit预编译库函数加载过程
  • 【秋招笔试】8.21华为秋招-三语言题解
  • 算法训练营|图论第4天 110.字符串接龙 105.有向图的完全可达性 106.岛屿的周长
  • 网络原理 TCP与UDP协议
  • 本地构建spotbugs，替换gradle的默认仓库地址。
  • chapter08-面向对象编程——（Object类详解）——day09
  • 【C++ Primer Plus习题】7.5
  • Docker方式部署K8s集群
  • 灵神算法题单——不定长滑动窗口（求最长最大）
  • C#入门（13）if语句
  • HTML简单了解和基础知识记录
  • 《机器学习》 基于GANs构建数字图像生成器 探索深度学习世界
  • 群晖（Docker Compose）配置 frp 服务
  • 移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——8.stackqueuepriority_queue(模拟实现）
  • zset使用lua实现取最高分数中的随机成员
  • 使用notepad++将shell脚本转为UNIX格式方法（主要差别在换行符）