그림의 반복과 검색

14489 단어


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

    /**
     * 
     * @param node
     *            

* Description: , *

*/ public void DFSTraversal(Node node) { Stack 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 *

Description: ,

*/ 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 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 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 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 *

Description:

*/ public List withinThreeBFSTraversal(Node root,int i){ visited= new HashSet<>(); visited.add(root); List list=new ArrayList(); Node neigh=getFirstUnvisitedNeighbour(root); while(neigh!=null){ list.add(neigh); visited.add(neigh); neigh=getFirstUnvisitedNeighbour(root); } int j=0; while(j getFriendsWithin(Node root,int degree,Set visited){ Set set=new HashSet(); if(degree==0){ set.add(root); visited.add(root); return set; } Set friends=getFriendsWithin(root,degree-1,visited); Set result=new HashSet<>(); for(Node node:friends){ Set neighs=getNeighbours(node); for(Node n:neighs){ if(!visited.contains(n)){ visited.add(n); result.add(n); } } } friends.addAll(result); return friends; } public Set getFriendsOf(Node root,int degree,Set visited){ //Set friends=getFriendsWithin(root,degree-1,visited); Set set=new HashSet<>(); if(degree==0){ visited.add(root); set.add(root); return set; } Set friends=getFriendsOf(root,degree-1,visited); Set result=new HashSet<>(); for(Node node:friends){ Set neighs=getNeighbours(node); for(Node n:neighs){ if(!visited.contains(n)){ visited.add(n); result.add(n); } } } return result; } public Set getNeighbours(Node node) { // System.out.println("neighbous"+node.value); Set neighbours = new HashSet(); List 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 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 set=gt.getFriendsWithin(node0, 3,visited); // List 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 getFriendsWithin(Node root,int degree,Set visited){
    
        Set set=new HashSet();
        if(degree==0){
            set.add(root);
            visited.add(root);
            return set;
        }
        
        Set friends=getFriendsWithin(root,degree-1,visited);
        Set result=new HashSet<>();
        //Iterator it=friends.iterator();
        for(Node node:friends){
            Set neighs=getNeighbours(node);
            for(Node n:neighs){
                if(!visited.contains(n)){
                    visited.add(n);
                    result.add(n);
                }

            }
            
        }
        friends.addAll(result);
        return friends;
    }
    
public Set getFriendsOf(Node root,int degree,Set visited){
        //Set friends=getFriendsWithin(root,degree-1,visited);
        Set set=new HashSet<>();
        if(degree==0){
            visited.add(root);
            set.add(root);
            return set;
        }
        Set friends=getFriendsOf(root,degree-1,visited);
        
        Set result=new HashSet<>();
        for(Node node:friends){
            Set neighs=getNeighbours(node);
            for(Node n:neighs){
                if(!visited.contains(n)){
                    visited.add(n);
                    result.add(n);
                }
            }
        }
        return result;
    }
    public Set getNeighbours(Node node) {
        // System.out.println("neighbous"+node.value);
        Set neighbours = new HashSet();
        List 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 getFriendsWithin(Node root,int degree,Set visited){
    
        Set set=new HashSet();
        if(degree==0){
            set.add(root);
            visited.add(root);
            return set;
        }
        
        Set friends=getFriendsWithin(root,degree-1,visited);
        Set result=new HashSet<>();
        //Iterator it=friends.iterator();
        for(Node node:friends){
            Set 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)

좋은 웹페이지 즐겨찾기