常用的图的存储结构主要有以下二种：邻接矩阵和邻接表邻接矩阵与邻接表的对比：1、当图中结点数目较小且边较多时，采用邻接矩阵效率更高。

2、当节点数目远大且边的数目远小于相同结点的完全图的边数时，采用邻接表存储结构更有效率。

有向图稀疏邻接矩阵结构深度优先搜索DFS寻找环路Java实现1.import java.util.*;2.import ng.StringUtils;3.public class DFSSparseCycle {4./** 点数 */5.private int vertexCount;6./** 有向图的稀疏邻接矩阵 */7.private int[][] sparseAdjacencyMatrix;8./** 点访问状态, 0未访问 1已访问 */9.private int[] vertexAccessStatus;10./** 追踪栈 */11.private List<Integer> traceStack = new ArrayList<Integer>();12./** 追踪过的点 */13.private List<Integer> tracedVertexs = new ArrayList<Integer>();14./** 环列表 */15.private List<List<Integer>> cycles = newArrayList<List<Integer>>();16.public DFSSparseCycle(int[][] sparseAdjacencyMatrix) {17.this.sparseAdjacencyMatrix = sparseAdjacencyMatrix;18.this.vertexCount = sparseAdjacencyMatrix.length;19.vertexAccessStatus = new int[vertexCount];20.Arrays.fill(vertexAccessStatus, 0);21.}22.public void findCycle() {23.for (int i = 0; i < vertexCount; i++) {24.if (!tracedVertexs.contains(i)) findCycle(i);25.}26.}27.public void findCycle(int vertex) {28.if (vertexAccessStatus[vertex] == 1) {29.int j = 0;30.if ((j = traceStack.indexOf(vertex)) != -1) {31.List<Integer> cycle = newArrayList<Integer>();32.while (j < traceStack.size()) {33.cycle.add(traceStack.get(j));34.j++;35.}36.cycles.add(cycle);37.return;38.}39.return;40.}41.vertexAccessStatus[vertex] = 1;42.traceStack.add(vertex);43.for (int i = 0; i < vertexCount; i++) {44.if (sparseAdjacencyMatrix[vertex][i] == 1) {45.findCycle(i);46.tracedVertexs.add(i);47.}48.}49.traceStack.remove(traceStack.size() - 1);50.}51.public boolean hasCycle() {52.return cycles.size() > 0;53.}54.public List<List<Integer>> getCycles() {55.return this.cycles;56.}57.public static void main(String[] args) {58.// 有向图的稀疏邻接矩阵59.int[][] adjacencyMatrix = { { 0, 1, 1, 0, 0, 0, 0 },60.{ 0, 0, 0, 1, 0, 0, 0 },61.{ 0, 0, 1, 0, 0, 1, 0 },62.{ 0, 0, 0, 0, 1, 0, 0 },63.{ 0, 0, 1, 0, 0, 0, 0 },64.{ 0, 0, 0, 0, 1, 0, 1 },65.{ 1, 0, 1, 1, 0, 0, 1 }66.};67.DFSSparseCycle dfsCycle = newDFSSparseCycle(adjacencyMatrix);68.dfsCycle.findCycle();69.if (!dfsCycle.hasCycle()) {70.System.out.println("No Cycle.");71.} else {72.List<List<Integer>> cycleList =dfsCycle.getCycles();73.for (int i = 0, len = cycleList.size(); i < len; i++) {System.err.println(StringUtils.join(cycleList.get(i), "#"));74.}75.}76.}77.}有向图稠密邻接表结构深度优先搜索DFS寻找环路Java实现1.import ng.StringUtils;2.import java.util.*;3.public class DFSDenseCycle {4./** 有向图的稠密邻接表 */5.private Map<Integer, Set<Integer>> denseAdjacencyMatrix;6./** 点访问状态 */7.private Set<Integer> vertexAccessStatus = newHashSet<Integer>();8./** 追踪栈 */9.private List<Integer> traceStack = new ArrayList<Integer>();10./** 追踪过的点 */11.private List<Integer> tracedVertexs = new ArrayList<Integer>();12./** 环列表 */13.private List<List<Integer>> cycles = newArrayList<List<Integer>>();14.public DFSDenseCycle(Map<Integer, Set<Integer>>denseAdjacencyMatrix) {15.this.denseAdjacencyMatrix = denseAdjacencyMatrix;16.}17.public void findCycle() {18.for (Map.Entry<Integer, Set<Integer>> entry :denseAdjacencyMatrix.entrySet()) {19.int vertex = entry.getKey();20.if (!tracedVertexs.contains(vertex))findCycle(vertex);21.}22.}23.public void findCycle(int vertex) {24.if (vertexAccessStatus.contains(vertex)) {25.int j = 0;26.if ((j = traceStack.indexOf(vertex)) != -1) {27.List<Integer> cycle = newArrayList<Integer>();28.while (j < traceStack.size()) {29.cycle.add(traceStack.get(j));30.j++;31.}32.cycles.add(cycle);33.return;34.}35.return;36.}37.vertexAccessStatus.add(vertex);38.traceStack.add(vertex);39.Set<Integer> vertexs = denseAdjacencyMatrix.get(vertex);40.for (int v : vertexs) {41.if (denseAdjacencyMatrix.containsKey(v)) {42.findCycle(v);43.tracedVertexs.add(v);44.}45.}46.traceStack.remove(traceStack.size() - 1);47.}48.public boolean hasCycle() {49.return cycles.size() > 0;50.}51.public List<List<Integer>> getCycles() {52.return this.cycles;53.}54.public static void main(String[] args) {55.Map<Integer, Set<Integer>> adjacencyMatrix = newHashMap<Integer, Set<Integer>>();56.adjacencyMatrix.put(0, new HashSet(Arrays.asList(1,2)));57.adjacencyMatrix.put(1, new HashSet(Arrays.asList(2,3)));58.adjacencyMatrix.put(2, new HashSet(Arrays.asList(0,3)));59.DFSDenseCycle dfsCycle = newDFSDenseCycle(adjacencyMatrix);60.dfsCycle.findCycle();61.if (!dfsCycle.hasCycle()) {62.System.out.println("No Cycle.");63.} else {64.List<List<Integer>> cycleList =dfsCycle.getCycles();65.for (int i = 0, len = cycleList.size(); i < len;i++) {System.err.println(StringUtils.join(cycleList.get(i), "#"));66.}67.}68.}69.}。