그림의 반복과 검색
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);
}
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)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
