图的遍历和搜索

public class GraphTraversal {
    Set<Node> visited=new HashSet<>() ;
    List<Node> list=new ArrayList<>();

    /**
     * 
     * @param node
     *            <p>
     *            Description:图的深度优先遍历，非递归
     *            </p>
     */
    public void DFSTraversal(Node node) {
        Stack<Node> stack = new Stack();
        visited= new HashSet<>();
        System.out.println(node.value);
        visited.add(node);
        stack.push(node);
        while (!stack.isEmpty()) {
            Node neighNode = getFirstUnvisitedNeighbour(stack.peek());
            if (neighNode != null) {
                System.out.println(neighNode.value);
                visited.add(neighNode);
                stack.push(neighNode);
            }

            else {
                stack.pop();
            }
        }

    }
    

    /**
     * 
     * @param node
     *<p>Description:图的深度优先，递归 </p>
     */
    
    public void DFSTraversalRecursion(Node node) {
        System.out.println(node.value);
        visited.add(node);
        Node neigh = getFirstUnvisitedNeighbour(node);
        while (neigh != null) {
            DFSTraversalRecursion(neigh);
            neigh = getFirstUnvisitedNeighbour(node);
        }
    }

    public void BFSTraversal(Node node) {
        Queue<Node> queue = new LinkedList();
        visited= new HashSet<>();
        queue.add(node);
        System.out.println(node.value);
        visited.add(node);
        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            Node neigh = getFirstUnvisitedNeighbour(currentNode);
            while (neigh != null) {
                queue.add(neigh);
                System.out.println(neigh.value);
                visited.add(neigh);
                neigh = getFirstUnvisitedNeighbour(currentNode);

            }
        }
    }

    public void WithinThreeBFSTraversal(Node node) {
        Queue<Node> queue = new LinkedList();
        visited= new HashSet<>();
        queue.add(node);
        // System.out.println(node.value);
        visited.add(node);
        Node currentNode = queue.poll();

        Node neigh = getFirstUnvisitedNeighbour(currentNode);
        while (neigh != null) {
            queue.add(neigh);
            System.out.println(neigh.value);
            visited.add(neigh);
            neigh = getFirstUnvisitedNeighbour(currentNode);

        }
        Queue<Node> queue2=new LinkedList();
        while(!queue.isEmpty()){
            Node curNode = queue.poll();

            Node neighNode = getFirstUnvisitedNeighbour(curNode);
            while (neighNode != null) {
                queue2.add(neighNode);
                System.out.println(neighNode.value);
                visited.add(neighNode);
                neighNode = getFirstUnvisitedNeighbour(curNode);

            }
        }
        
        Queue queue3=new LinkedList();
        while(!queue2.isEmpty()){
            Node curNode = queue2.poll();

            Node neighNode = getFirstUnvisitedNeighbour(curNode);
            while (neighNode != null) {
                queue3.add(neighNode);
                System.out.println(neighNode.value);
                visited.add(neighNode);
                neighNode = getFirstUnvisitedNeighbour(curNode);

            }
        }
    }
    
    /**
     * 
     * @param root
     * @param i
     * @return
     *<p>Description:图三度以内的朋友 </p>
     */
    
    public List<Node> withinThreeBFSTraversal(Node root,int i){
        visited= new HashSet<>();

        visited.add(root);
        List<Node> list=new ArrayList<Node>();
        Node neigh=getFirstUnvisitedNeighbour(root);
        while(neigh!=null){
            list.add(neigh);
            visited.add(neigh);
            neigh=getFirstUnvisitedNeighbour(root);

        }
        int j=0;
        while(j<i){
            int size=list.size();
            for(int k=0;k<size;k++){
                Node cur=getFirstUnvisitedNeighbour(list.get(k));
                if(cur!=null){
                    //System.out.println(j+","+list.get(k)+","+cur.value);

                    list.add(cur);
                    visited.add(cur);

                }
            }
            j++;
        }
        return list;
    }

    public Set<Node> getFriendsWithin(Node root,int degree,Set visited){
    
        Set<Node> set=new HashSet();
        if(degree==0){
            set.add(root);
            visited.add(root);
            return set;
        }
        
        Set<Node> friends=getFriendsWithin(root,degree-1,visited);
        Set<Node> result=new HashSet<>();
        for(Node node:friends){
            Set<Node> neighs=getNeighbours(node);
            for(Node n:neighs){
                if(!visited.contains(n)){
                    visited.add(n);
                    result.add(n);
                }

            }
            
        }
        friends.addAll(result);
        return friends;
    }
    
    public Set<Node> getFriendsOf(Node root,int degree,Set visited){
        //Set<Node> friends=getFriendsWithin(root,degree-1,visited);
        Set set=new HashSet<>();
        if(degree==0){
            visited.add(root);
            set.add(root);
            return set;
        }
        Set<Node> friends=getFriendsOf(root,degree-1,visited);
        
        Set result=new HashSet<>();
        for(Node node:friends){
            Set<Node> neighs=getNeighbours(node);
            for(Node n:neighs){
                if(!visited.contains(n)){
                    visited.add(n);
                    result.add(n);
                }
            }
        }
        return result;
    }
    public Set<Node> getNeighbours(Node node) {
        // System.out.println("neighbous"+node.value);
        Set<Node> neighbours = new HashSet<Node>();
        List<Edge> list = node.edges;
        for (int i = 0; i < list.size(); i++) {
            //System.out.println(i);
            Edge edge = list.get(i);
            if (edge.start.equals(node)) {
                if (!visited.contains(edge.end)) {
                    neighbours.add(edge.end);
                    // System.out.println("end-unvisited"+edge.end.value);
                }
            } else if (edge.end.equals(node)) {
                if (!visited.contains(edge.start)) {
                    neighbours.add(edge.start);
                    // System.out.println("start-unvisited"+edge.start.value);

                }
            }

        }
        return neighbours;
    }

    public Node getFirstUnvisitedNeighbour(Node node) {
        List<Edge> list = node.edges;
        for (int i = 0; i < list.size(); i++) {
            Edge edge = list.get(i);
            if (edge.start.equals(node)) {
                if (!visited.contains(edge.end)) {
                    return edge.end;
                }
            } else if (edge.end.equals(node)) {
                if (!visited.contains(edge.start)) {
                    return edge.start;
                }
            }

        }
        return null;
    }
    public static void main(String args[]) {
        Graph g = new Graph();
        Node node0 = g.createNode(0);

        Node node1 = g.createNode(1);
        Node node2 = g.createNode(2);
        Node node3 = g.createNode(3);
        Node node4 = g.createNode(4);
        Node node5 = g.createNode(5);
        Node node6 = g.createNode(6);
        Node node7 = g.createNode(7);

        Edge edge0 = g.insertEdge(node0, node1);
        Edge edge1 = g.insertEdge(node0, node2);
        Edge edge2 = g.insertEdge(node1, node2);
        Edge edge3 = g.insertEdge(node1, node3);
        Edge edge4 = g.insertEdge(node2, node4);

        Edge edge5 = g.insertEdge(node3, node4);
        Edge edge6 = g.insertEdge(node4, node5);
        Edge edge8 = g.insertEdge(node4, node7);

        Edge edge7 = g.insertEdge(node5, node6);

        

        GraphTraversal gt=new GraphTraversal();
         Set visited=new HashSet<>();
        // g.DFSTraversal(node0);
        // g.removeNode(node1);
        // g.getNeighbours(node0);
        // g.getNeighbours(node1);
        // g.DFSTraversalRecursion(node0);
        //g.WithinThreeBFSTraversal(node2);
//      gt.DFSTraversalRecursion(node0);
//      System.out.println("-----------");
//      gt.DFSTraversal(node0);
//      System.out.println("-----------");

        Set<Node> set=gt.getFriendsWithin(node0, 3,visited);
//      List<Node> list=gt.WithinThreeBFSTraversal(node0, 4);
        for(Node node:set){
            System.out.println(node.value);

        }

1.图的深度优先非递归实现
（1）栈S初始化；visited[n]=0；

（2）访问顶点v；visited[v]=1；顶点v入栈S

（3）while(栈S非空)

        x=栈S的顶元素(不出栈)；

        if(存在并找到未被访问的x的邻接点w)

                访问w；visited[w]=1；

                w进栈;

        else

                 x出栈；

public void DFSTraversal(Node node){
        
        System.out.println(node.value);
        visited.add(node);
        stack.push(node);
        while(!stack.isEmpty()){
            Node neighNode=getFirstNeighbour(stack.peek());
            
            if(neighNode!=null){
                    System.out.println(neighNode.value);
                    visited.add(neighNode);
                    stack.push(neighNode);
            }
            
            else{
                stack.pop();
            }
        }

递归实现

（1）访问顶点v；visited[v]=1；//算法执行前visited[n]=0

（2）w=顶点v的第一个邻接点；

（3）while（w存在）

       if（w未被访问）

               从顶点w出发递归执行该算法； 
       w=顶点v的下一个邻接点；

    public void DFSTraversalRecursion(Node node){
        System.out.println(node.value);
        visited.add(node);
        Node neigh=getFirstNeighbour(node);
        while(neigh!=null){
            DFSTraversalRecursion(neigh);
            neigh=getFirstNeighbour(node);
        }
    }

广度优先
（1）初始化队列Q；visited[n]=0；

（2）访问顶点v；visited[v]=1；顶点v入队列Q；

（3） while（队列Q非空）

          v=队列Q的对头元素出队；

          w=顶点v的第一个邻接点；

         while（w存在） 

                 如果w未访问，则访问顶点w；

                 visited[w]=1；

                 顶点w入队列Q；

                 w=顶点v的下一个邻接点。。

public void BFSTraversal(Node node){
        queue.add(node);
        System.out.println(node.value);
        visited.add(node);
        while(!queue.isEmpty()){
            Node currentNode=queue.poll();
            Node neigh=getFirstNeighbour(currentNode);
            while(neigh!=null){
                queue.add(neigh);
                System.out.println(neigh.value);
                visited.add(neigh);
                neigh=getFirstNeighbour(currentNode);

            }
        }
    }

几度以内的朋友及第几度的朋友

public Set<Node> getFriendsWithin(Node root,int degree,Set visited){
    
        Set<Node> set=new HashSet();
        if(degree==0){
            set.add(root);
            visited.add(root);
            return set;
        }
        
        Set<Node> friends=getFriendsWithin(root,degree-1,visited);
        Set<Node> result=new HashSet<>();
        //Iterator<Node> it=friends.iterator();
        for(Node node:friends){
            Set<Node> neighs=getNeighbours(node);
            for(Node n:neighs){
                if(!visited.contains(n)){
                    visited.add(n);
                    result.add(n);
                }

            }
            
        }
        friends.addAll(result);
        return friends;
    }
    
public Set<Node> getFriendsOf(Node root,int degree,Set visited){
        //Set<Node> friends=getFriendsWithin(root,degree-1,visited);
        Set set=new HashSet<>();
        if(degree==0){
            visited.add(root);
            set.add(root);
            return set;
        }
        Set<Node> friends=getFriendsOf(root,degree-1,visited);
        
        Set result=new HashSet<>();
        for(Node node:friends){
            Set<Node> neighs=getNeighbours(node);
            for(Node n:neighs){
                if(!visited.contains(n)){
                    visited.add(n);
                    result.add(n);
                }
            }
        }
        return result;
    }
    public Set<Node> getNeighbours(Node node) {
        // System.out.println("neighbous"+node.value);
        Set<Node> neighbours = new HashSet<Node>();
        List<Edge> list = node.edges;
        for (int i = 0; i < list.size(); i++) {
            //System.out.println(i);
            Edge edge = list.get(i);
            if (edge.start.equals(node)) {
                if (!visited.contains(edge.end)) {
                    neighbours.add(edge.end);
                    // System.out.println("end-unvisited"+edge.end.value);
                }
            } else if (edge.end.equals(node)) {
                if (!visited.contains(edge.start)) {
                    neighbours.add(edge.start);
                    // System.out.println("start-unvisited"+edge.start.value);

                }
            }

        }
        return neighbours;
    }
···


下图是错误的示范
  ```Java
    public Set<Node> getFriendsWithin(Node root,int degree,Set visited){
    
        Set<Node> set=new HashSet();
        if(degree==0){
            set.add(root);
            visited.add(root);
            return set;
        }
        
        Set<Node> friends=getFriendsWithin(root,degree-1,visited);
        Set<Node> result=new HashSet<>();
        //Iterator<Node> it=friends.iterator();
        for(Node node:friends){
            Set<Node> neighs=getNeighbours(node);
            for(Node n:neighs){
                if(!visited.contains(n)){
                    visited.add(n);
                    friends.add(n);
                }

            }
            
        }
        //friends.addAll(result);
        return friends;
    }

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMapHashIterator.nextNode(Unknown Source) at java.util.HashMapKeyIterator.next(Unknown Source)
at datastruct.GraphTraversal.getFriendsWithin(GraphTraversal.java:186)
at datastruct.GraphTraversal.getFriendsOfThree(GraphTraversal.java:202)
at datastruct.GraphTraversal.main(GraphTraversal.java:303)