术语

  • 完全图
    任何 两个顶点都有边

  • 数量关系
    n表示顶点数量，e表示边的数量，
    无向图中的e为[0, n(n-1)/2]
    有向图中的e为[0, n    (n-1)/2]
    图中所有的顶点度数之和(出度+入度)为2*e

  • 简单路径、简单回路
    一条路径中，除了起点和终点外，若其余顶点各不相同，则称改路径为简单路径；由简单路径构成的回路成为简单回路

  • 连通图、强连通图
    无向图中，如果任意两个顶点都可以互相到达，则称为连通，图中的任意两点都连通为连通图，其极大连通子图成为连通分量
    有向图中，如果任意两个顶点都有路径，则称为强连通，图中任意两个点都强连通则为强连通图，其极大连通子图成为强连通分量

  • 生成树
    一个含有n个顶点的的连通图的生成树是一个极小连通子图，它含有图中的全部顶点，，但有且只有足以构成一棵树的n-1条边
    生成树上添加1条边必定构成一个环
    有n-1条边的不一定是生成树
    一个图的生成树不唯一

  • AOV网：结点表示活动的网；

  • AOE网：边表示活动的持续时间的网；

图的表示

  • 邻接矩阵
    无向图一定是对称的，有向图不一定对称
    int [][]二维数组
  • 邻接表

List<List<Node>>

图的遍历

  • DFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    DFS(u){//访问顶点u
      vis[u] = true;
      for(u能到达的所有顶点v){
        if(vis[v] == false){
          DFS[v];
        }
      }
    }
    DFSTrave(G){//遍历图G
      for(G的所有顶点u){
        if(vis[u] == false){
          DFS(u);
        }
      }
    }

  • BFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    BFS(u){
      while(q 不为空){//q为队列,LinkedList
        u = q.remove();//取出头结点
        for(u出发可以到达的所有顶点v){
          if(inq(v) == false){//没有入过队列
            q.add(v);//v入队
            inq[v] = true;//已经入队列
          }
        }
      }
    }
    BFSTrave(G){
      for(G的所有顶点u){
        if(inq[u] == false){
          Queue<> q = new LinkedList<>();//产生队列
          BFS(u);//访问
          inq[u] = true;//标记进队
        }
      }
    }

最短路径

  • 单源最短路径Dij
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //d为源点到每个点的最短距离记录，s为起点
    //pre为最短路径的记录顺序,pre[v] = u表示v的前驱结点是u
    Dij(G, d[], s,pre[]){
      初始化;
      for(循环n次){
        u= 使得d[u]最小且没有被访问的节点;//这里可以用priorityQueue等
        标记u访问过;
        for(u 能到达的所有点v){
          if(v未访问 && 以u为中介点使得s到v的距离更短){
            优化d[v];
            pre[v] = u;//记录最短路径
          }
          /*
          else(距离相等){
            其他标尺
          }
          */
        }
      }
    }

Dij+DFS：很可能在求最短路径的时候不止有一条，因此最短路径得到顺序pre后，还可以用dfs得到权值最小的路径

  • 全源最短路径Floyd
    3层遍历,枚举节点k
    1
    2
    3
    4
    5
    6
    7
    8
    9
    for(int k = 0; k < n; k++){
      for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
          if(d[i][k] + d[k][j] < d[i][j]){
            d[i][j] = d[i][k] + d[k][j];
          }
        }
      }
    }

最小生成树MST

  • 性质
    1.只在无向图中有
    2.最小生成树是树，边数 = 点数 - 1,且一定无环
    3.最小生成树不一定唯一，但是其边权之和一定唯一

  • Prim
    算法思想和Dij相似，但是Prim是一个集合的最小距离，而Dij到一个点的最小距离

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //d为源点到每个点的最短距离记录，s为起点
    //pre为最短路径的记录顺序,pre[v] = u表示v的前驱结点是u
    int Prim(G, d[], s){
      int ans = 0;//初始化
      for(循环n次){
        u= 使得d[u]最小且没有被访问的节点;//这里可以用priorityQueue等
        标记u访问过;
        ans += d[u];
        for(u 能到达的所有点v){
          if(v未访问 && 以u为中介点使得已选中的集合到v的距离更短){
            优化d[v];
          }
        }
      }
      return ans;
    }

  • Kruskal
    对边排序，然后选择最小的，合并到一起
    使用了并查集和排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    public class Kruskal {
        //点数
        int numv = 100;
        ArrayList<Edge> edges = new ArrayList<>();
        int father[] = new int[numv];
        //并查集
        public int findfather(int x){
            int a = x;
            while(x != father[x]){
                x = father[x];
            }
            //路径压缩,放置树太高，影响查找效率
            while(a != father[a]){
                int z = a;
                a = father[a];
                father[z] = a;
            }
            return x;
        }
        public int Kru(int v, int e){
            //最小生成树的权值
            int ans = 0;
            //生成树的边数
            int vis = 0;
            //初始化并查集
            for (int i = 0; i < v; i++) {
                father[i] = i;
            }
            //对边的权值进行排序
            Collections.sort(edges);
            for(int i = 0; i < e; i++){
                int uu = edges.get(i).u;
                int vv = edges.get(i).v;
                //查看vv和uu是不是在同一个集合中
                int fau = findfather(uu);
                int fav = findfather(vv);
                if(fau != fav){
                    //加入到集合中去
                    father[fau] = fav;
                    //生成树权值增加
                    ans += edges.get(i).cost;
                    //生成树边数增加
                    vis++;
                    //生成树的边数为n-1，结束生成树查找
                    if(vis == v - 1){
                        break;
                    }
                }
            }
            if(vis == v - 1){
                //返回生成树权值
                return ans;
            }else{
                //不能生成生成树
                return -1;
            }
        }
    }
    class Edge implements Comparable<Edge>{
        int u,v;
        int cost;
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(o.cost, this.cost);
        }
    }

拓扑序列

判断一个图是不是有向无环图
准备所有顶点的入度数组
1、定义一个队列，把所有入度为0的点加入队列中
2、取出队首，对其所有相邻的边进行操作：将该边到达的点的入度减1，如果该点的入度为0，则加入到队列，删除这条边
3、重复执行2直到队列为空，判断遍历过的点的数目是不是等于该图的节点数