遍历使用链表构成的图

点击打开链接

这样一张图

修改了原理的Graph类方便添加节点和权值

public class Graph { public HashMap<Integer,Node> nodes;//所有的节点，和节点编号。 public HashSet<Edge> edges;//所有的边 public Graph() { nodes = new HashMap<Integer,Node>(); edges = new HashSet<Edge>(); } public Node addNode(int Number,int value){//产生新节点 编号，value Node node = new Node(value); nodes.put(Number, node); return node; } public void addEdge(int weight, int fromn,int ton){ //通过编号取节点 Node from = nodes.get(fromn); Node to = nodes.get(ton); Edge edge = new Edge(weight,from,to); from.nexts.add(to); from.edges.add(edge); from.out++; to.in++; } }

BFS遍历

广度优先遍历，给定一个节点，然后依次遍历离他最近的节点

使用队列+set集合

每次装入队列都要装入set中防止重复

每次弹出队列，输入并把他所有的出度边都装入队列

public static void bfs(Node node) { if(node==null){ return; } Queue<Node> queue = new LinkedList<Node>(); HashSet<Node> set = new HashSet<Node>(); queue.add(node); set.add(node); while(!queue.isEmpty()){ Node cur = queue.poll(); System.out.println(cur.value); for(Node next:cur.nexts){ if(!set.contains(next)){ queue.add(next); set.add(next); } } } }

DFS遍历

广度优先遍历，给定一个节点，然后依次遍历离他最近的节点

使用栈+set集合

每次装入栈都要装入set中防止重复

每次进栈的时候输出，每次出栈都看看，有没可以进栈的出度边了，有的话把自己加上出度进栈。

没有的话，这个节点遍历结束。

public static void dfs(Node node) { if(node==null){ return; } Stack<Node> stack = new Stack<Node>(); Set<Node> set = new HashSet<Node>(); stack.add(node); set.add(node); System.out.println(node.value); while(!stack.isEmpty()){ Node cur = stack.pop(); for(Node next:cur.nexts){ if(!set.contains(next)){ stack.add(cur); stack.add(next); set.add(next); System.out.println(next.value); break; } } } }

测试代码

public static void main(String[] args) { // TODO Auto-generated method stub Graph graph = new Graph(); Node node1=graph.addNode(1,1);//编号为1，value为1的顶点 Node node2=graph.addNode(2,2); Node node3=graph.addNode(3,3); Node node4=graph.addNode(4,4); Node node5=graph.addNode(5,5); graph.addEdge(4, 1,2);//编号1顶点到编号2顶点 权值为4的边 graph.addEdge(2, 1,3); graph.addEdge(8, 1,4); graph.addEdge(8, 2,5); graph.addEdge(6, 3,5); graph.addEdge(7, 4,5); dfs(node1); }