求无向无权图起点到终点的所有路径

求无向无权图起点到终点的所有路径


基本思路:

基于图的深度优先遍历进行修改。

0:初始栈中只有起点元素。

步骤1:如果栈为空,则返回,否则,访问栈顶节点,但先不删除栈顶元素。

步骤2:如果该元素的邻接点

(1)是终点,则打印路径。

(2)在栈中已存在,则是环路,不处理。

(2)正常,则将该邻接点入栈,继续步骤1


示例图如下:

求无向无权图起点到终点的所有路径


代码如下:

package com.collonn.algorithm.grf;

import java.util.Stack;

/**
 * 无向无权无环图<br/>
 * 寻找起点到终点的所有路径
 */
public class GrfAllEdge {
	// 图的顶点总数
	private int total;
	// 各顶点基本信息
	private String[] nodes;
	// 图的邻接矩阵
	private int[][] matirx;

	public GrfAllEdge(int total, String[] nodes) {
		this.total = total;
		this.nodes = nodes;
		this.matirx = new int[total][total];
	}

	private void printStack(Stack<Integer> stack, int k) {
		for (Integer i : stack) {
			System.out.print(this.nodes[i] + ",");
		}
		System.out.print(this.nodes[k] + ",");
	}

	/**
	 * 寻找起点到终点的所有路径
	 * 
	 * @param underTop
	 *            紧挨着栈顶的下边的元素
	 * @param goal
	 *            目标
	 * @param stack
	 */
	private void dfsStack(int underTop, int goal, Stack<Integer> stack) {
		// System.out.print("\n栈元素:");
		// this.printStack(stack);

		if (stack.isEmpty()) {
			return;
		}

		// 访问栈顶元素,但不弹出
		int k = stack.peek().intValue();
		// 紧挨着栈顶的下边的元素
		int uk = underTop;

		if (k == goal) {
			System.out.print("\n起点与终点不能相同");
			return;
		}

		// 对栈顶的邻接点依次递归调用,进行深度遍历
		for (int i = 0; i < this.total; i++) {
			// 有边,并且不在左上到右下的中心线上
			if (this.matirx[k][i] == 1 && k != i) {
				// 排除环路
				if (stack.contains(i)) {
					// 由某顶点A,深度访问其邻接点B时,由于是无向图,所以存在B到A的路径,在环路中,我们要排除这种情况
					// 严格的请,这种情况也是一个环
					if (i != uk) {
						System.out.print("\n有环:");
						this.printStack(stack, i);
					}
					continue;
				}

				// 打印路径
				if (i == goal) {
					System.out.print("\n路径:");
					this.printStack(stack, i);
					continue;
				}

				// 深度遍历
				stack.push(i);
				dfsStack(k, goal, stack);
			}
		}

		stack.pop();
	}

	private void printMatrix() {
		System.out.println("----------------- matrix -----------------");
		System.out.println("---0-1-2-3-4-5-6-7-8--");
		System.out.println("---A-B-C-D-E-F-G-H-I--");
		for (int i = 0; i < this.total; i++) {
			System.out.print(" " + this.nodes[i] + "|");
			for (int j = 0; j < this.total; j++) {
				System.out.print(this.matirx[i][j] + "-");
			}
			System.out.print("\n");
		}
		System.out.println("----------------- matrix -----------------");
	}

	// 设置[i][i]位置处的元素值为0,0表示图中的定点i未被访问,1表示图中的定点i已被访问
	private void resetVisited() {
		for (int i = 0; i < this.total; i++) {
			this.matirx[i][i] = 0;
		}
	}

	// 初始化图数据
	// 0---1---2---3---4---5---6---7---8---
	// A---B---C---D---E---F---G---H---I---
	private void initGrf() {
		// A-B, A-D, A-E
		this.matirx[0][1] = 1;
		this.matirx[1][0] = 1;
		this.matirx[0][3] = 1;
		this.matirx[3][0] = 1;
		this.matirx[0][4] = 1;
		this.matirx[4][0] = 1;
		// B-C
		this.matirx[1][2] = 1;
		this.matirx[2][1] = 1;
		// C-F
		this.matirx[2][5] = 1;
		this.matirx[5][2] = 1;
		// D-E, D-G
		this.matirx[3][4] = 1;
		this.matirx[4][3] = 1;
		this.matirx[3][6] = 1;
		this.matirx[6][3] = 1;
		// E-F, E-H
		this.matirx[4][5] = 1;
		this.matirx[5][4] = 1;
		this.matirx[4][7] = 1;
		this.matirx[7][4] = 1;
		// F-H, F-I
		this.matirx[5][7] = 1;
		this.matirx[7][5] = 1;
		this.matirx[5][8] = 1;
		this.matirx[8][5] = 1;
		// G-H
		this.matirx[6][7] = 1;
		this.matirx[7][6] = 1;
		// H-I
		this.matirx[7][8] = 1;
		this.matirx[8][7] = 1;
	}

	// 初始化图数据
	// 0---1---2---3---4---5---6---7---8---
	// A---B---C---D---E---F---G---H---I---
	private void initGrf2() {
		// A-B, A-D, A-E
		this.matirx[0][1] = 1;
		this.matirx[1][0] = 1;
		this.matirx[0][3] = 1;
		this.matirx[3][0] = 1;
		this.matirx[0][4] = 1;
		this.matirx[4][0] = 1;
		// B-C
		this.matirx[1][2] = 1;
		this.matirx[2][1] = 1;
		// C-F
		this.matirx[2][5] = 1;
		this.matirx[5][2] = 1;
		// D-E
		this.matirx[3][4] = 1;
		this.matirx[4][3] = 1;
		// E-F, E-H
		this.matirx[4][5] = 1;
		this.matirx[5][4] = 1;
		this.matirx[4][7] = 1;
		this.matirx[7][4] = 1;
		// F-H, F-I
		this.matirx[5][7] = 1;
		this.matirx[7][5] = 1;
		this.matirx[5][8] = 1;
		this.matirx[8][5] = 1;
		// G-H
		this.matirx[6][7] = 1;
		this.matirx[7][6] = 1;
		// H-I
		this.matirx[7][8] = 1;
		this.matirx[8][7] = 1;
	}

	// 初始化图数据
	// 0---1---2---3---4---5---6---7---8---
	// A---B---C---D---E---F---G---H---I---
	private void initGrf3() {
		// A-D, A-E
		this.matirx[0][3] = 1;
		this.matirx[3][0] = 1;
		this.matirx[0][4] = 1;
		this.matirx[4][0] = 1;
		// B-C
		this.matirx[1][2] = 1;
		this.matirx[2][1] = 1;
		// C-F
		this.matirx[2][5] = 1;
		this.matirx[5][2] = 1;
		// E-H, E-I
		this.matirx[4][7] = 1;
		this.matirx[7][4] = 1;
		this.matirx[4][8] = 1;
		this.matirx[8][4] = 1;
		// F-I
		this.matirx[5][8] = 1;
		this.matirx[8][5] = 1;
		// G-H
		this.matirx[6][7] = 1;
		this.matirx[7][6] = 1;
	}

	public static void main(String[] args) {
		String[] nodes = new String[] { "A", "B", "C", "D", "E", "F", "G", "H", "I" };
		GrfAllEdge grf = new GrfAllEdge(9, nodes);
		grf.initGrf();
		grf.printMatrix();

		System.out.print("\n------ 寻找起点到终点的所有路径开始 ------");
		grf.resetVisited();
		int origin = 0;
		int goal = 8;
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(origin);
		grf.dfsStack(-1, goal, stack);
		System.out.print("\n------ 寻找起点到终点的所有路径结束 ------");
	}

}


第一个无向图的结果如下,输出环路和正确路径:

------ 寻找起点到终点的所有路径开始 ------
有环:A,B,C,F,E,A,
有环:A,B,C,F,E,D,A,
有环:A,B,C,F,E,D,G,H,E,
有环:A,B,C,F,E,D,G,H,F,
路径:A,B,C,F,E,D,G,H,I,
有环:A,B,C,F,E,H,F,
有环:A,B,C,F,E,H,G,D,A,
有环:A,B,C,F,E,H,G,D,E,
路径:A,B,C,F,E,H,I,
有环:A,B,C,F,H,E,A,
有环:A,B,C,F,H,E,D,A,
有环:A,B,C,F,H,E,D,G,H,
有环:A,B,C,F,H,E,F,
有环:A,B,C,F,H,G,D,A,
有环:A,B,C,F,H,G,D,E,A,
有环:A,B,C,F,H,G,D,E,F,
有环:A,B,C,F,H,G,D,E,H,
路径:A,B,C,F,H,I,
路径:A,B,C,F,I,
有环:A,D,E,A,
有环:A,D,E,F,C,B,A,
有环:A,D,E,F,H,E,
有环:A,D,E,F,H,G,D,
路径:A,D,E,F,H,I,
路径:A,D,E,F,I,
有环:A,D,E,H,F,C,B,A,
有环:A,D,E,H,F,E,
路径:A,D,E,H,F,I,
有环:A,D,E,H,G,D,
路径:A,D,E,H,I,
有环:A,D,G,H,E,A,
有环:A,D,G,H,E,D,
有环:A,D,G,H,E,F,C,B,A,
有环:A,D,G,H,E,F,H,
路径:A,D,G,H,E,F,I,
有环:A,D,G,H,F,C,B,A,
有环:A,D,G,H,F,E,A,
有环:A,D,G,H,F,E,D,
有环:A,D,G,H,F,E,H,
路径:A,D,G,H,F,I,
路径:A,D,G,H,I,
有环:A,E,D,A,
有环:A,E,D,G,H,E,
有环:A,E,D,G,H,F,C,B,A,
有环:A,E,D,G,H,F,E,
路径:A,E,D,G,H,F,I,
路径:A,E,D,G,H,I,
有环:A,E,F,C,B,A,
有环:A,E,F,H,E,
有环:A,E,F,H,G,D,A,
有环:A,E,F,H,G,D,E,
路径:A,E,F,H,I,
路径:A,E,F,I,
有环:A,E,H,F,C,B,A,
有环:A,E,H,F,E,
路径:A,E,H,F,I,
有环:A,E,H,G,D,A,
有环:A,E,H,G,D,E,
路径:A,E,H,I,
------ 寻找起点到终点的所有路径结束 ------


原创博文,转载请注明出处。

求无向无权图起点到终点的所有路径

上一篇:PBOC/EMV之脱机明文PIN和脱机密文PIN


下一篇:DNS域欺骗攻击详细教程之Linux篇