1.无向图

顶点度数：即依附于某个顶点的边的总数
树：一幅无环连通图
表示无向图的数据结构：

  • 邻接矩阵。V^2空间
  • 边的数组：Edge类：含有两个int类型变量表示顶点
  • 邻接表数组：以顶点为索引的列表数组

无向图API:Graph
常用图处理代码

  1. 计算v的度数

    1. public int degree(Graph G,int v){
    2.  int degree =0;
    3.  for(int w:G.adj(v)){
    4.      degree++;
    5.  }
    6.  return degree;
    7. }

  2. 计算所有顶点的最大度数

    1. public int maxDegree(Graph G,int v}{
    2.  int max =0;
    3.  for(int v=0;v<G.V();v++){
    4.      if(digree(G,v)>max){
    5.          max =digree(G,v);
    6.      }
    7.  }
    8. }

    3.计算自环的个数

    1. public int numberOfSelfLoops(Graph G){
    2.  int count=0;
    3.  for(int v=0;v<G.V();v++){
    4.      for(int w:G.adj(v)){
    5.          if (w==v) count++;
    6.      }
    7.  }
    8.  return count/2;
    9. }

    Graph数据类型：

    1. pulic class Cycle{
    2.  private boolean marked[];
    3.  private boolean hasCycle;
    4.  public Cycle(Graph G){
    5.      marked = new boolean[G.V()];
    6.      for(int v=0;v<G.V();v++){
    7.          if(!marked[v]){
    8.              dfs(G,v,v);
    9.          }
    10.      }
    11.  }
    12.  public void dfs(Graph G,int v,int u ){
    13.      mark[v] = true;
    14.      for(int w:G.adj(v)){
    15.          if(!marked[w])
    16.              dfs(G,w,v)
    17.              else if (w!=u)
    18.      }
    19.  }
    20. }

    拓扑排序：所有顶点的逆后序排列
    Leetcode:210:课程表 ```java // class Solution { // public int[] findOrder(int numCourses, int[][] prerequisites) { // if(numCourses==0) return new int [0]; // //采用判断入度数的方法BFS遍历方法 // int inDegree[] = new int [numCourses]; // for(int p[]:prerequisites){ // inDegree[p[0]]++; // } // //BFS遍历使用的队列 // LinkedList queue = new LinkedList<>(); // int count=0;//当前可以学习的科目 // int res[] = new int [numCourses];//返回学习数组 // for(int i=0;i<numCourses;i++){ // if(inDegree[i] == 0) queue.offer(i); // } // while(!queue.isEmpty()){ // int cur = queue.poll(); // res[count] = cur; // count++; // for(int p[]:prerequisites){ // if(p[1]==cur) { // inDegree[p[0]]—; // if(inDegree[p[0]]==0) queue.offer(p[0]); // } // } // } // if(res.length==count) return res; // return new int [0]; // } // } //第二种方式采用dfs方式遍历，要做有加权图的环检测

class Solution { public boolean[] marked ; public boolean[] onStack; public List> edges; public int result[]; public boolean hasCycle = false; int index; public int[] findOrder(int numCourses, int[][] prerequisites) { marked = new boolean[numCourses]; onStack = new boolean[numCourses]; edges = new ArrayList<>(); result = new int [numCourses]; index = numCourses-1;//拓扑排序是所有顶点的逆后序排列 for(int i=0;i()); } for(int p[]:prerequisites){ edges.get(p[1]).add(p[0]); } for(int v=0;v<numCourses&&!hasCycle;v++){ if(!marked[v]) dfs(v); } if(!hasCycle) return result; else return new int [0]; } public void dfs(int v){ onStack[v] = true; marked[v] = true; for(int w:edges.get(v)){ if(!marked[w]) { dfs(w); } else if(onStack[w]){ hasCycle = true; return; } } onStack[v] = false; result[index—] = v; } }

**最小生成树**：无向加权图：切分定理：一幅加权图：给定任意的切分，横切边最小的边中权重最下的边一定属于最小生成树<br />延时的prim算法：会保留失效的边<br />优先队列实现：一开始最小生成树只有一个顶点：然后需要向他添加V-1条边，每次总是将下一条连接树的顶点与不在树的顶点的且权重最小的边加入树中。<br />即时版本：采用索引优先队列实现：不会保留失效的边<br />Kruscal算法：按照边的权重顺序（从小到大）处理他们，将边权重最小的边加入到最下生成树，加入的边不会和已经加入的边构成环，知道树中有V-1条边。也就是图的最小生成树。<br />**最短路径**：加权有向图：

1. 解决边的权重非负的最短路径问题的：Dijkstra算法
1. 解决无环加权有向图最短路径快速算法：使用点的拓扑顺序进行顶点松弛
1. 适用一般情况的Bellman_ford算法

Dijstra算法：

和prim算法类似：prim算法：每次添加都是离树最近的非树顶点，dijstra算法是每次添加都是离起点最近并非树顶点 。
```java
mport java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * 索引优先队列,通过qp[]索引数组数组找到对象关联的整数，然后由这个整数取出对象
 * i--item;qp[j] = i;pq[i]=j;  items[i] =item; pq[qp[j]]=j;qp[qp[i]]=i;
 * 其他删除，上浮，下沉操作和二叉堆一样，唯独多了一个删除k对应的对象，因为这个索引优先队列
 * 这个是最小堆，如果是最大堆，把这个greater方法改成less方法，其他一样
 */
public class IndexPriorityQueue<Item extends Comparable<Item>>{
    //二叉堆数组：存的是对象对应的索引
    private int pq[];
    //二叉堆数组中索引对应二叉堆数组中位置
    private int qp[];
    private int N;
    //二叉堆保存的对象数组
    private Item items[];
    public IndexPriorityQueue(int maxN){
        pq= new int[maxN+1];
        qp =new int[maxN+1];
        items = (Item[]) new Comparable[maxN+1];
        Arrays.fill(qp,-1);
    }
    public void insert(int k,Item item){
        //二叉堆索引从1开始
        pq[++N]=k;
        qp[k] =N;
        items[k] =item;
        swim(N);
    }
    public boolean contains(int k){
        return qp[k] !=-1;
    }
    public boolean isEmpty(){
        return N==0;
    }
    public void change(int k,Item item){
        items[k] =item;
        //将整数k对应的位置进行上浮和下沉，有可能下沉也有可能上浮，简单起见都操作
        swim(qp[k]);
        sink(qp[k]);
    }
    //删除对象
    public void delete(int k){
        if(!contains(k))throw new NoSuchElementException("没有这个对象");
        int index = qp[k];
        swap(index,N--);
        swim(index);
        sink(index);
        items[k] =null;
        qp[k] =-1;
    }
    //返回最小元素索引
    public int minIndex(){
        return qp[1];
    }
    //删除最小元素并返回他的索引
    public int delMin(){
        if(N==0) throw new NoSuchElementException("队列为空！");
        int indexOfMin =pq[1];
        swap(1,this.N--);
        sink(1);
        items[indexOfMin] = null;
        qp[indexOfMin] =-1;
        return indexOfMin;
    }
    public Item min(){
        return items[pq[1]];
    }

    //比较
    private boolean greater(int i,int j){
        return items[pq[i]].compareTo(items[pq[j]])>0;
    }
    //交换
    private void swap(int i,int j){
        int t =pq[i];
        pq[i] = pq[j];
        pq[j] =t;
        qp[pq[i]]=i;
        qp[pq[j]]=j;
    }
    //上浮
    private void swim(int k){
        while (k>1&&greater(k/2,k))
            swap(k/2,k);
            k=k/2;
    }
    private void sink(int k){
            while (2 * k <= N) {
                int j = 2 * k;
                if (j < N && greater(j, j + 1)) j ++;
                if (!greater(k, j)) break;
                swap(k, j);
                k = j;
            }
    }

}






import java.util.Stack;

/**
 * Dijstra最短路径(单点最短路径)api:只能解决非负的加权有向图的最短路径问题
 * 涉及的数据结构：disTo[],edgeTo[];pq 索引优先队列（涉及到取最小且需要修改的队列都使用索引优先队列）
 * DijkstraShortestPath(EdgeWeightDigraph G,int s):s点是源点
 * double disto(int v) s到v的距离，如果没有则为无穷大
 * boolean hasPathTo(int v) s- v是否存在路径
 * Iterable<EdgeWeightDigraph> pathTo(int v) :s->v的路径
 */
public class DijkstraShortestPath {
    //private boolean marked[];
    private double disTo[];
    private DirectedEdge edgeTo[];
    private IndexPriorityQueue<Double>pq;
    private Queue<DirectedEdge>queue;
    public DijkstraShortestPath(EdgeWeightDigraph G,int s){
        disTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        pq = new IndexPriorityQueue<>(G.V());
        queue =new Queue<>();
        for(int v=0;v<G.V();v++){
            disTo[v] = Double.POSITIVE_INFINITY;
        }
        disTo[s]=0;
        pq.insert(s,0.0);
        while(!pq.isEmpty()){
            relax(G,pq.delMin());
        }
    }
    public void relax(EdgeWeightDigraph G,int v){
        for(DirectedEdge edge:G.adj(v)){
            int w =edge.to();
            if(disTo[w]>disTo[v]+edge.weight()){
                disTo[w] =disTo[v]+edge.weight();
                edgeTo[w] =edge;
                if(pq.contains(w))pq.change(w,disTo[w]);
                else pq.insert(w,disTo[w]);
            }
        }
    }
    public double disTo(int v){
        return disTo[v];
    }
    public boolean hasPathTo(int v){
        return disTo[v]< Double.POSITIVE_INFINITY;
    }
    public Iterable<DirectedEdge>pathTO(int v){
        if(!hasPathTo(v))return null;
        Stack<DirectedEdge> path = new Stack<>();
        for(DirectedEdge edge =edgeTo[v];edge!=null;edge=edgeTo[edge.from()])
            path.push(edge);
        return path;
    }

}

最长路径：考虑无环加权图：采用拓扑排序放松顶点，然后加原来的最短路径符号进行改变即可。
并行任务调度： 优先级限制下的并行任务调度：关键路径：创建一幅无环加权图，其中包括起点s和一个终点t，且每个任务都对应着两个顶点（起始顶点和终止顶点）。每个任务都有一个从起始点到终止点的边，边的权重代表任务所需时间。对于优先级限制：v-w，添加一个从v的结束顶点到w的开始顶点权重为0的边。还需要为每个任务添加一条从起点指向任务起点权重为0的边，以及任务终点到终点的权重为0的边，这样每个计时开始即为从起点到它起始顶点的最长距离。，将任务调度转化为一幅无环加权有向图的最长路径问题。