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

java数据结构----图

news 2024/11/18 7:31:40

图的存储结构:

代码实现

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;}}}
}