java数据结构----图
图的存储结构:
代码实现
public class Graph {// 标记顶点数目private int V;// 标记边数目private int E;// 邻接表private Queue<Integer>[] adj;public Graph(int v) {V = v;this.E = 0;this.adj = new Queue[v];for (int i = 0; i < adj.length; i++) {adj[i] = new Queue<Integer>();}}public int getV(){return V;}public int getE(){return E;}// 将v和w顶点相连public void addEdge(int v, int w){// 无向图中adj[v].enqueue(w);adj[w].enqueue(v);E++;}// 获取v点相连的点public Queue<Integer> adj(int v){return adj[v];}
}图的搜索
深度优先搜索
广度优先搜索
路径查找
有向图
拓扑排序
检测有向图中的环
顶点排序
加权无向图
public class EdgeWeightedGraph {private final int V;private int E;private Queue<Edge>[] adj;public EdgeWeightedGraph(int v) {V = v;E = 0;adj = new Queue[v];for (int i = 0; i < adj.length; i++) {adj[i] = new Queue<>();}}public int getV(){return V;}public int getE(){return E;}public void addEdge(Edge edge){int v = edge.either();int w = edge.other(v);adj[v].enqueue(edge);adj[w].enqueue(edge);E++;}public Queue<Edge> adj(int v){return adj[v];}public Queue<Edge> edges() throws InterruptedException {Queue<Edge> res = new Queue<>();for (int i = 0; i < adj.length; i++) {while (!adj[i].isEmpty()){Edge edge = adj[i].dequeue();int other = edge.other(i);if (other > i){res.enqueue(edge);}}}return res;}class Edge implements Comparable<Edge>{private int v;private int w;private double weight;public Edge(int v, int w, double weight) {this.v = v;this.w = w;this.weight = weight;}public double getWeight(){return weight;}public int either(){return v;}public int other(int a){return a == v ? w : v;}@Overridepublic int compareTo(Edge o) {double cmp = this.weight - o.weight;if (cmp > 0){return 1;}else if (cmp< 0){return -1;}else {return 0;}}}
}
最小生成树
贪心算法
prim算法
kruskal算法
加权有向图
加权有向边
加权有向图
最短路径树
内容来源于184_最短路径_Dijkstra算法实现1_哔哩哔哩_bilibili