public class EdgeNode {     //定义邻接表中的边结点类型
         int adjvex;             //邻接点域
         int weight;             //边的权值域，假定为整型，对于无权图，边的权值为1
         EdgeNode next;          //指向下一个边结点的链接域
         public EdgeNode(int adj, EdgeNode nt) 
         {     //对无权图中的边结点进行初始化
             adjvex=adj; next=nt; weight=1;
         }
         public EdgeNode(int adj, int wgt, EdgeNode nt) 
         {     //对有权图中的边结点进行初始化
             adjvex=adj; next=nt; weight=wgt;
         }
     }

public interface Graph
     {
         boolean createGraph(EdgeElement[]d);  //根据边集数组参数d建立一个图
         int graphType();                   //返回图的类型
         int vertices();                    //返回图中的顶点数
         int edges();                       //返回图中的边数
         boolean find(int i, int j);        //从图中查找一条边(i,j)是否存在
         boolean putEdge(EdgeElement theEdge); //向图中插入一条边theEdge
         boolean removeEdge(int i, int j);     //从图中删除一条边(i,j)
         int degree(int i);                 //返回顶点i的度
         int inDegree(int i);               //返回顶点i的入度
         int outDegree(int i);              //返回顶点i的出度
         void output();                     //以图的顶点集和边集的形式输出一个图
         void depthFirstSearch(int v);      //从顶点v开始深度优先搜索遍历图
         void breadthFirstSearch(int v);    //从顶点v开始广度优先搜索遍历图
         void clearGraph();                 //清除图中的所有内容
     }

    private void dfs(int i, boolean[] visited) {
        System.out.printl(i + " ");
        visited[i] = true;
        EdgeNode p = a[i];
        while(p != null) {
            int j = p.adjvex;
            if(!visited[j]) {
                dfs(j, visited);
            }
            p = p.next;
        }
    }

 private void bfs(int i, boolean[] visited) {
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.print(i + " ");
        visited[i] = true;
        queue.offer(i);
        while(!queue.isEmpty()) {
            int k = queue.poll();
            EdgeNode p = a[k];

            while(p != null) {
                int j = p.adjvex;
                 if(!visited[j]) {
                     System.out.print(j + " ");
                     visited[j] = true;
                     queue.offer(j);
                 }
                 p = p.next;
            }
        }
    }

    public int binarySearch(int[] arr, int target) {
        if (arr == null || arr.length <= 1) {
            return -1;
        }

        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (arr[mid] > target) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }