Я хочу, чтобы преобразовать матрицу смежности в список adjanceny настоящим Кодексом БФС, спасибо :)
// Implementing BFS Algorithm import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; public class BFS { private Queue<Node> queue; // Queue that will contain some of Nodes static ArrayList<Node> nodes=new ArrayList<Node>(); static class Node { int data; boolean visited; Node(int data) { this.data=data; } } public BFS() { queue = new LinkedList<Node>(); // Initialization of Queue } // find neighbors of node using adjacency matrix // if adjacency_list[i][j]==1, then nodes at index i and index j are connected public ArrayList<Node> findNeighbours(int adjacency_list[][],Node x) { int nodeIndex=-1; ArrayList<Node> neighbours=new ArrayList<Node>(); for (int i = 0; i < nodes.size(); i++) { if(nodes.get(i).equals(x)) { nodeIndex=i; break; } } if(nodeIndex!=-1) { for (int j = 0; j < adjacency_list[nodeIndex].length; j++) { if(adjacency_list[nodeIndex][j]==1) { neighbours.add(nodes.get(j)); } } } return neighbours; } //Push Node in the Queue then remove it [FIFO] //Get Neighbours from the brevious function findNeighbours and add to Queue Nodes that only not visited //Printing Nodes Visited at each step and The Number of Vertex visited at each step public void bfs(int adjacency_list[][], Node node) { queue.add(node); node.visited=true; while (!queue.isEmpty()) { Node element=queue.remove(); System.out.print("\n " + element.data + "\t\t "); ArrayList<Node> neighbours=findNeighbours(adjacency_list,element); int C=0; // Count for (int i = 0; i < neighbours.size(); i++) { Node n=neighbours.get(i); if(n!=null && !n.visited) { C++; System.out.print(n.data + " "); queue.add(n); n.visited=true; } } System.out.print("\t\t\t\t" + C); } } public static void main(String arg[]) { //Graph that you want Doing BFS on it //Adding Nodes Node node1 =new Node(1); Node node2 =new Node(2); Node node3 =new Node(3); Node node4 =new Node(4); Node node5 =new Node(5); Node node6 =new Node(6); Node node7 =new Node(7); Node node8 =new Node(8); nodes.add(node1); nodes.add(node2); nodes.add(node3); nodes.add(node4); nodes.add(node5); nodes.add(node6); nodes.add(node7); nodes.add(node8); //AdjacencyList that compines adjacencyMatrix with edge lists int adjacency_list[][] = { {0,1,1,0,0,0,0,0}, // Node 1: 1 {1,0,1,1,1,0,0,0}, // Node 2 :2 {1,1,0,0,1,0,1,1}, // Node 3: 3 {0,1,0,0,1,0,0,0}, // Node 4: 4 {0,1,1,1,0,1,0,0}, // Node 5: 5 {0,0,0,0,1,0,0,0}, // Node 6: 6 {0,0,1,0,0,0,0,1}, // Node 7: 7 {0,0,1,0,0,0,1,0}, // Node 8: 8 }; System.out.println("The BFS traversal of This Graph is :- "); System.out.print("Traversal Visited Number of Vertex visited at each step"); BFS bfsExample = new BFS(); bfsExample.bfs(adjacency_list, node1); //Calling to bfs function with root vertex System.out.println(); } }
Что я уже пробовал:
I want convert adjacency matrix to adjanceny list in this BFS code, thanks :)
Richard MacCutchan
В чем проблема?