要求
Implement and test a FriendshipGraph class that represents friendships in a social network and can compute the distance between two people in the graph. An auxiliary class Person is also required to be
implemented. You should model the social network as an undirected graph where each person is connected to zero or more people, but your underlying graph implementation should be directed. Your solution must work with the following client implementation.
- FriendshipGraph graph = new FriendshipGraph();
- Person rachel = new Person(“Rachel”);
- Person ross = new Person(“Ross”); Lab Manuals for Software Construction Lab-1 Fundamental Java Programming and Testing 6
- Person ben = new Person(“Ben”);
- Person kramer = new Person(“Kramer”);
- graph.addVertex(rachel);
- graph.addVertex(ross);
- graph.addVertex(ben);
- graph.addVertex(kramer);
- graph.addEdge(rachel, ross);
- graph.addEdge(ross, rachel);
- graph.addEdge(ross, ben);
- graph.addEdge(ben, ross);
- out.println(graph.getDistance(rachel, ross));//should print
- System.out.println(graph.getDistance(rachel, ben));//should print 2
- System.out.println(graph.getDistance(rachel, rachel));//should print 0
- System.out.println(graph.getDistance(rachel, kramer));//should print -1
Your solution should work with the client code above. The getDistance method should take two people (as Person) as arguments and return the shortest distance (an int) between the people, or -1 if the two people
are not connected (or in other words, there are no any paths that could reach the second people from the first one). Your graph implementation should be reasonably scalable. We will test your graph with several hundred or thousand vertices and edges. Use proper access modifiers (public, private, etc.) for your fields and methods. If a field/method can be private, it should be private. Do not use static fields or methods except for the main method(s) and constant Follow the Java code conventions, especially for naming and commenting. Hint: use Ctrl + Shift + F to auto-format your code! Add short descriptive
comments () to all public methods. Additional hints/assumptions For your implementation of getDistance, you may want to review breadth-first search. You may use the standard Java libraries, including classes from java.util, but no third-party libraries. You may assume that each person has a unique name. Lab Manuals for Software Construction Lab-1 Fundamental Java Programming and Testing 7 You may handle incorrect inputs however you want (printing to standard out/error, silently failing, crashing, throwing a special exception, etc.) You should write additional samples to test your graph, similar to our main method. To print something to standard out, use System.out.println. For example: System.out.println(“DON’T PANIC”); You should also write JUnit test code to test the methods addVertex(), addEdge(), and getDistance() of the class FriendshipGraph. All the test cases should be included in FriendshipGraphTest.java in the directory \test\P3. Test cases should be sufficient enough.
設計/實作FriendshipGraph類
存儲結構：
private Set<Person> persons = new HashSet<Person>();
用來存儲人
private Set<String> names = new HashSet<String>();
用來存儲人名，以此檢查是否出現人名重複的情況
人際關系在Person類中實作（為了實作有向圖）
public boolean addVertex(Person person)
将person這個節點添加到persons中，同時判斷是否存在重名的問題，如果有，直接傳回false，如果沒有，就将其名字加入names中，傳回true。
public boolean addEdge(Person per1, Person per2)
兩次調用Person類中的addFriend函數即可，同時注意判斷兩個人是否是同一個人，并傳回對應結果
getDistance(Person per1, Person per2)
使用廣度優先搜尋
Map<String, Boolean> visited = new HashMap<>();
Map<String, Integer> dis = new HashMap<>();
用兩個圖來存儲一個點是否被通路和對應的距離
Queue<Person> temp
建一個隊列來存儲正在和将要通路的節點
流程
- 初始化visited中的每個點的vis屬性為false，dis中的為0
- 将per1加入隊列temp，并visited.put(src.getName(), true)
-
檢查隊列是否為空
若是，結束循環，傳回-1
若否，取出隊首節點存入vertex，重複第3、4、5步操作
-
搜尋per1的friends set（在Person類中實作）中未通路過的節點
如果有子節點等于per2，即找到一條最短路，結束搜尋，傳回目前的路徑長度
否則，将滿足要求的子節點依次加入隊列，将其visited對應值置為true
- 所有滿足條件的子節點掃描完之後，對應節點的dis ++；
設計/實作Person類
存儲結構
private String name;
用來存儲名字
public Queue<Person> friends = new LinkedBlockingQueue<Person>();
用來存儲朋友（以此實作單邊的關系）
其它函數就不再贅述，見代碼
Person類
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
public class Person {
private String name;
public Queue<Person> friends = new LinkedBlockingQueue<Person>();
public Person() { System.out.println("PleaseGiveMeaName!"); }
public Person(String name) { this.name = name; }
public void setName(String name) { this.name = name; }
public String getName() { return name; }
public boolean hasFriend(Person friend) { return friends.contains(friend); }
public boolean hasFriends() { return friends.isEmpty(); }
public boolean addFriend(Person friend) {
if(friends.contains(friend)) return false;
else {
friends.add(friend);
return true;
}
}
public boolean deleteFriend(Person friend) {
if(friends.contains(friend)) {
friends.remove(friend);
return true;
} else return true;
}
}
FriendshipGraph類
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
import P3.Person;
public class FriendshipGraph {
private Set<Person> persons = new HashSet<Person>();
private Set<String> names = new HashSet<String>();
public boolean addVertex(Person person) {
if(persons.contains(person) || names.contains(person.getName()))
return false;
else {
persons.add(person);
names.add(person.getName());
return true;
}
}
public boolean addEdge(Person per1, Person per2) {
boolean flag = false;
if(per1 == per2) return false;
for(Person person : persons)
if(person.getName() == per1.getName()) {
per1 = person;
persons.remove(person);
per1.addFriend(per2);
persons.add(per1);
flag = true;
break;
}
return flag;
}
public int getDistance(Person src, Person dest){
if (src.getName().equals(dest.getName()))
return 0;
Map<String, Boolean> visited = new HashMap<>();
Map<String, Integer> dis = new HashMap<>();
for (Person person: persons) {
visited.put(person.getName(), false);
dis.put(person.getName(), 0);
}
visited.put(src.getName(), true);
Queue<Person> queue = new LinkedBlockingQueue<>();
queue.add(src);
while (!queue.isEmpty()){
Person vertex = queue.poll();
Queue<Person> temp = vertex.friends;
while (!temp.isEmpty()){
if(visited.get(temp.peek().getName())) {
temp.poll();
continue;
}
if (temp.peek().getName().equals(dest.getName()))
return dis.get(vertex.getName()) + 1;
else{
visited.put(temp.peek().getName(), true);
dis.put(temp.peek().getName(), dis.get(vertex.friends.peek().getName()) + 1);
queue.add(temp.poll());
}
}
}
return -1;
}
public static void main(String args[]) {
FriendshipGraph graph = new FriendshipGraph();
Person rachel = new Person("Rachel");
Person ross = new Person("Ross");
Person ben = new Person("Ben");
Person kramer = new Person("Kramer");
graph.addVertex(rachel);
graph.addVertex(ross);
graph.addVertex(ben);
graph.addVertex(kramer);
graph.addEdge(rachel, ross);
graph.addEdge(ross, rachel);
graph.addEdge(ross, ben);
graph.addEdge(ben, ross);
System.out.println(graph.getDistance(rachel, ross));
System.out.println(graph.getDistance(rachel, ben));
System.out.println(graph.getDistance(rachel, rachel));
System.out.println(graph.getDistance(rachel, kramer));
}
}
警告
未來的學習學妹們，這是我自己的一個記錄，也是給你們的參考
請一定要自己完成，你會有很大收獲的
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)