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)
网友评论