首页 > 代码库 > 图的表示与遍历
图的表示与遍历
图的表示：连接矩阵，连接链表。
图的遍历：dfs(递归、非递归)，bfs.
连接矩阵下各种遍历：
import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;import java.util.Stack;public class Graph { int v; int e; int[][] mat; public Graph(int v) { this.v = v; this.e = 0; mat = new int[v][v]; } public void addEdge(int a, int b) { if (mat[a][b] == 0) e++; mat[a][b] = 1; mat[b][a] = 1; } public Iterable<Integer> adj(int a) { List<Integer> res = new ArrayList<Integer>(); for (int i = 0; i < v; i++) { if (mat[a][i] != 0) { res.add(i); } } return res; } public void dfsNonRecur() { boolean[] vis = new boolean[v]; for (int i = 0; i < v; i++) { if (!vis[i]) { dfsNonRecur(i, vis); } } System.out.println(); } public void dfs() { boolean[] vis = new boolean[v]; for (int i = 0; i < v; i++) { if (!vis[i]) { dfs(i, vis); } } System.out.println(); } private void dfs(int i, boolean[] vis) { vis[i] = true; System.out.print(i + " "); for (Integer each : adj(i)) { if (!vis[each]) dfs(each, vis); } } private void dfsNonRecur(int i, boolean[] vis) { Stack<Integer> stack = new Stack<Integer>(); vis[i] = true; stack.push(i); System.out.print(i + " "); while (!stack.isEmpty()) { Integer top = stack.peek(); boolean finished = true; for (Integer each : adj(top)) { if (!vis[each]) { System.out.print(each + " "); vis[each] = true; stack.push(each); finished = false; break; } } if (finished) { if (!stack.isEmpty()) stack.pop(); } } } public void bfs() { boolean[] vis = new boolean[v]; for (int i = 0; i < v; i++) { if (!vis[i]) { bfs(i, vis); } } System.out.println(); } public void bfs(int start, boolean[] vis) { Queue<Integer> queue = new LinkedList<Integer>(); queue.add(start); vis[start] = true; System.out.print(start + " "); while (!queue.isEmpty()) { Integer out = queue.remove(); for (Integer each : adj(out)) { if (!vis[each]) { vis[each] = true; queue.add(each); System.out.print(each + " "); } } } } public static void main(String[] args) { Graph g = new Graph(5); g.addEdge(0, 1); g.addEdge(0, 3); g.addEdge(1, 2); g.addEdge(3, 4); g.dfs(); g.dfsNonRecur(); g.bfs(); }}
参考资料：
http://algs4.cs.princeton.edu/41undirected/AdjMatrixGraph.java.html
http://algs4.cs.princeton.edu/41undirected/Graph.java.html
http://blog.csdn.net/lalor/article/details/6845788
图的表示与遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。