**

***在这个程序中，你将为代表友谊的图形（例如facebook）实现一些有用的算法。友谊图是边上没有任何权值的无向图。它是一个简单的图，因为没有自循环（自循环是从顶点到自身的边）或多条边（多条边意味着一对顶点之间的边更多）。

本作业图表中的顶点代表两种人：学生和非学生。每个顶点将存储人的名字。如果此人是学生，学校的名称也将被存储。下面是一个友谊图示例：***

**

public static ArrayList<String> shortestChain(Graph g, String p1, String p2) {

            /**COMPLETE THIS METHOD**/

            // FOLLOWING LINE IS A PLACEHOLDER TO MAKE COMPILER HAPPY
            // CHANGE AS REQUIRED FOR YOUR IMPLEMENTATION

            int indexP1=g.map.get(p1);
            int indexP2=g.map.get(p2);

            Person perSon1=g.members[indexP1];
            Person perSon2=g.members[indexP2];

            /*System.out.println("Edge Point ="+perSon1.first.next);
            System.out.println("Edge Point"+ perSon2.name+"="+perSon2.first.fnum);
            System.out.println("Edge Point"+ perSon2.name+"="+perSon2.first.next.fnum);
            System.out.println("Edge Point"+ perSon2.name+"="+perSon2.first.next.next.fnum);
            */
            int count =0;
            Friend ptr=perSon1.first;
            while(ptr!=null){
                //System.out.println("Next Element="+ptr.fnum);

                Person per=g.members[ptr.fnum];
                System.out.println("Connection Friend="+per.name);

                /*if(per.name.equalsIgnoreCase(perSon2.name)){
                    System.out.println("Found data-path="+perSon1.name+"--"+per.name);
                }else{
                    System.out.println("Not Single Edge path");
                }*/

                Queue<Person> queue=new Queue<>();
                queue.enqueue(per);

                ptr=ptr.next;

                count=count+1;
            }
            System.out.println("Total Connections="+count);

            return null;
        }

        /**
         * Finds all cliques of students in a given school.
         * 
         * Returns an array list of array lists - each constituent array list contains
         * the names of all students in a clique.
         * 
         * @param g Graph for which cliques are to be found.
         * @param school Name of school
         * @return Array list of clique array lists. Null if there is no student in the
         *         given school
         */
        public static ArrayList<ArrayList<String>> cliques(Graph g, String school) {

            /**COMPLETE THIS METHOD**/

            // FOLLOWING LINE IS A PLACEHOLDER TO MAKE COMPILER HAPPY
            // CHANGE AS REQUIRED FOR YOUR IMPLEMENTATION
            return null;

        }

        /**
         * Finds and returns all connectors in the graph.
         * 
         * @param g Graph for which connectors needs to be found.
         * @return Names of all connectors. Null if there are no connectors.
         */
        public static ArrayList<String> connectors(Graph g) {

            /**COMPLETE THIS METHOD**/

            // FOLLOWING LINE IS A PLACEHOLDER TO MAKE COMPILER HAPPY
            // CHANGE AS REQUIRED FOR YOUR IMPLEMENTATION
            return null;

        }
    }

我得到的电流

graph ={ming=8, rich=13, michele=2, sergei=3, samir=6, heather=11, aparna=7, kaitlin=5, nick=9, tom=14, bob=10, rachel=12, ricardo=4, sam=0, jane=1}
Person Name=sam, isStudent=true,school=rutgers,first=1
Person Name=jane, isStudent=true,school=rutgers,first=5
Person Name=michele, isStudent=true,school=cornell,first=14
Person Name=sergei, isStudent=true,school=rutgers,first=7
Person Name=ricardo, isStudent=true,school=penn state,first=9
Person Name=kaitlin, isStudent=true,school=rutgers,first=9
Person Name=samir, isStudent=false,school=null,first=7
Person Name=aparna, isStudent=true,school=rutgers,first=4
Person Name=ming, isStudent=true,school=penn state,first=9
Person Name=nick, isStudent=true,school=penn state,first=11
Person Name=bob, isStudent=true,school=rutgers,first=6
Person Name=heather, isStudent=true,school=penn state,first=9
Person Name=rachel, isStudent=false,school=null,first=2
Person Name=rich, isStudent=true,school=ucla,first=14
Person Name=tom, isStudent=true,school=ucla,first=13
15
Edge Point =friends.Friend@5a42bbf4
Edge Point aparna=4
Edge Point aparna=6
Edge Point aparna=3
Connection Friend=heather
Not Single Edge path
Connection Friend=ming
Not Single Edge path
Connection Friend=ricardo
Not Single Edge path
Connection Friend=kaitlin
Not Single Edge path
Total Connections=4