无向图的构建

我的目标是输入顶点个数以及一系列的边来构建出无向图。
表示图的方法有邻接矩阵，邻接表，以及边的列表
设计Graph类，该类中包含V，E，以及邻接表adj。

public Graph(int V, int[][] edges) {
        // 输入参数.一个是顶点的个数，接下来是n条边
        this.V = V;
        this.adj = (ArrayList<Integer>[]) new ArrayList[this.V];
        for (int i = 0; i < this.V; i++) {
            this.adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];

            this.adj[from].add(to);
            this.adj[to].add(from);
            this.E++;
        }
    }

DFS

无向图的深度优先遍历总是递归寻找到该节点对应的链表所有可能的节点。代码如下：

  public void dfs(int v) {
        boolean[] marked = new boolean[this.V];
        int[] edgeTo=new int[this.V];
        dfs(marked,edgeTo, v);
        System.out.println(Arrays.toString(edgeTo));
    }
  private void dfs(boolean[] marked,int[] edgeTo, int v) {
        marked[v] = true;
        System.out.println("v:" + v);
        for (int i : this.adj[v]) {
            if (!marked[i]) {
                edgeTo[i]=v;
                dfs(marked,edgeTo, i);
            }
        }
    }

marked表示该节点是否被访问过，edgeTo表示从点v开始到任意一点的路径，如果要输出路径，可以通过如下途径输出（倒置）：

  int temp=v2;
  System.out.print("path: ");
  while(temp!=v1){
    System.out.print(temp+",");
    temp=edgeTo[temp];
  }
  System.out.println(v1);

BFS

广度优先遍历通过队列的方式进行（和二叉树的层次遍历相同）

    public void bfs(int v){
        boolean[] marked=new boolean[this.V];
        int[] edgeTo=new int[this.V];
        bfs(marked, edgeTo, v);
    }
    public void bfs(boolean[] marked,int[] edgeTo,int v){
        Queue<Integer> queue=new LinkedList<>();
        queue.add(v);
        marked[v]=true;
        while(!queue.isEmpty()){
            int a=queue.poll();
            System.out.println("v:"+a);
            for(int w:this.adj[a]){
                if(!marked[w]){
                    marked[w]=true;
                    edgeTo[w]=a;
                    queue.add(w);
                }
            }
        }
        System.out.println(Arrays.toString(edgeTo));
    }