湖北短视频搜索seo/网站手机优化

加权有向图

和加权无向图不同的是，加权有向图只是一个点指向另一个点，当然也可以双向指向，和加权无向图相同的是，在边中加入了另外一个属性，权重，这个权重可以是这个边的任何属性，比如长度，时间，粗细，颜色等等。正是因为假如了另外一个属性，边的实现就相对复杂了，因此将边抽象为一个类，这个类包括两个节点成员变量和一个权重成员变量，用来模拟边。
加权有向图可以真正解决最短路径问题。

java代码

package mypackage;
import java.util.Iterator;//队列类，用链表实现,后面有用
class Queue<T> implements Iterable<T>{//    节点个数，头节点，尾节点private int N;private Node head;private Node last;//节点类public class Node {public T data;public Node next;public Node(T data, Node next) {this.data = data;this.next = next;}}//构造方法，初始化public Queue() {this.N = 0;this.head = new Node(null,null);this.last = null;}//队列长度public int size(){return N;}//队列是否为空public boolean isEmpty(){return N==0;}//入队列public void enqueue(T data){
//        如果队列为空，说明尾节点为空，让新节点为尾节点，头借点指向尾节点if (isEmpty()){last=new Node(data,null);head.next=last;
//            如果队列不为空，让新节点为尾节点，老的尾节点指向新尾节点}else {Node oldlast=last;last=new Node(data,null);oldlast.next=last;}
//        最后元素+1N++;}//出队列，注意先入先出，每次出的节点就是head指向的第一个节点，然后让head只想第二个节点即可
//    且注意，如果队列为空，要将last=nullpublic T dequeue(){
//        如果为空，返回nullif (isEmpty()){return null;
//            如果不为空，让head只想第二个节点，元素-1，且如果队列为空，要将last=null}else {Node oldfirst=head.next;head.next=oldfirst.next;N--;if (isEmpty()){last=null;}
//            返回弹出的元素return oldfirst.data;}}//    遍历@Overridepublic Iterator iterator() {return new QIterator();}//    创建一个内部类实现Iterator接口public class QIterator implements Iterator {//        定义一个遍历的节点private Node n;public QIterator() {
//            初始化为0索引位置this.n = head;}//重写两个方法@Overridepublic boolean hasNext() {
//            这个方法判断是否超出最大索引，如果超出会停止遍历return n.next != null;}@Overridepublic Object next() {
//            这个方法会遍历得每个节点n = n.next;return n.data;}}
}//边类，因为加权有向图的边比较麻烦，因此专门用一个类表示边
class DirectedEdge implements Comparable<DirectedEdge>{//两个顶点，一个权重private int v;//起点private int w;//终点private double weigth;//权重public DirectedEdge(int v, int w, double weigth) {this.v = v;this.w = w;this.weigth = weigth;}//获取边的权重值public double getWeigth(){return weigth;}//获取起点public int from(){return v;}//获取终点public int end(){return w;}//重写compareTo方法，提供比较规则，以weigth比较边的大小@Overridepublic int compareTo(DirectedEdge o) {int cmp;if (this.weigth>o.weigth){cmp= 1;}else if (this.weigth==o.weigth){cmp= 0;}else {cmp= -1;}return cmp;}
}//加权有向图，注意边是单独的一个类实现的
class WeigthDirectedGraph{private int V;//顶点数private int E;//边数//adj是一个数组，数组的类型的队列，队列里面装的数据类型是DirectedEdge边类private Queue<DirectedEdge>[] adj;//邻接表，注意索引是每个顶点//构造方法，传入顶点个数，初始化边数为0，public WeigthDirectedGraph(int v) {this.V = v;this.E=0;this.adj=new Queue[v];//初始化队列数组，大小为顶点的个数for (int i = 0; i <adj.length ; i++) {adj[i]=new Queue<DirectedEdge>();//初始化数组的每个队列}}//获得顶点的个数public int getV(){return V;}//添加边，注意这里的边是单独的类实现的,传入一个边参数，让这个边在起点的邻接表中//注意是有向图，因此只在起点的邻接表中添加边//真正的边是需要实现类的public void addDirectedEdge(DirectedEdge DirectedEdge){int v=DirectedEdge.from();adj[v].enqueue(DirectedEdge);E++;//边数+1}// 获取边的个数public int getE(){return E;}//获取某个顶点相邻的所有边，返回这个队列即可public Queue<DirectedEdge> getAdj(int v){return adj[v];}//获取图的所有边public Queue<DirectedEdge> getDirectedEdges(){Queue<DirectedEdge> allDirectedEdges=new Queue<>();//用来装边for (int v = 0; v <V ; v++) {for (DirectedEdge e:adj[v]) {allDirectedEdges.enqueue(e);}}return allDirectedEdges;}
}//测试
public class MyJava {public static void main(String[] args){WeigthDirectedGraph WeigthDirectedGraph=new WeigthDirectedGraph(6);//添加边WeigthDirectedGraph.addDirectedEdge(new DirectedEdge(0,1,10));WeigthDirectedGraph.addDirectedEdge(new DirectedEdge(1,2,15));WeigthDirectedGraph.addDirectedEdge(new DirectedEdge(2,3,20));WeigthDirectedGraph.addDirectedEdge(new DirectedEdge(0,4,10));WeigthDirectedGraph.addDirectedEdge(new DirectedEdge(0,5,100));System.out.println("顶点数量："+WeigthDirectedGraph.getV());System.out.println("边的条数："+WeigthDirectedGraph.getE());System.out.println("0指向的顶点：");for (DirectedEdge x:WeigthDirectedGraph.getAdj(0)){System.out.print(x.end()+" ");}System.out.println();System.out.println("所有边(起点+终点+长度)：");for (DirectedEdge x:WeigthDirectedGraph.getDirectedEdges()){System.out.print(x.from()+"-->"+x.end()+" : "+x.getWeigth()+"  |  ");}}
}