图结构

• 有向图，无向图
  • 边上有方向
  • 边上无方向
• 有权图，无权图
  • 有权图，边上有值。
  • 无权图，边上无值。

• 判断图之间是否连通
• 连通分量

• 自环边
• 平行边
  

package graphic;
    /**
     * 密集矩阵用邻接矩阵
     * @author 59842
     *
     */
    public class DenseGraph {
        //有多少个定点
        private int n;
        //有多少个边
        private int m;
        //是否有向//true表示有向图
        private boolean directed;
        //存储图的有向结构
        private boolean[][] g;

        public DenseGraph(int n, boolean directed) {
            this.n=n;
            this.m=0;
            this.directed=directed;
            g=new boolean [n][n];
        }
        public void addEdge(int v,int w) {
            if(0<=v&&v<n||0<=w&&w<n)
                throw new IllegalArgumentException("边超出了范围");
            if(hasEdge(v,w))
                return ;
            g[v][w]=true;

            if(!directed)
                //不是有向图
                g[w][v]=true;
            m++;
        }

        private boolean hasEdge(int v, int w) {
            if(0<=v&&v<n||0<=w&&w<n)
                throw new IllegalArgumentException("边超出了范围");
            return g[w][v]=false;
        }
        public int getV() {
            return n;
        }

        public int getE() {
            return m;
        }

    }

• 适用的场景，每个电影的相似程度。有权图
  邻接表适合表示稀疏图，邻接矩阵适合表示稠密图