有向图中以一个顶点为起始点的所有路径，有向图中所有路径存储

适用于：有向图中设定从一个顶点出发，存储该顶点的所有路径，对于有向有环图同样适用（程序中记录了经过的节点，可以避免有环图的特例）。 适用于：有向图中，从一个顶点出发，存储所有以该顶点为起始点的路径。

网上找到一些相关的，但是大都是值给出两点间所有路径，没有想要的功能。






有向图的路径发现

适用于：有向图中设定从一个顶点出发，存储该顶点的所有路径，对于有向有环图同样适用（程序中记录了经过的节点，可以避免有环图的特例）。 适用于：有向图中，从一个顶点出发，存储所有以该顶点为起始点的路径。

图： 1->2 ，1->3， 1->4， 1->8 ，2->3 ，4->5 ，5->6 ，5->7 ，8->7 ，6->1 ，7->1 设定的顶点1，得到以下结果。 [1, 2] [1, 3] [1, 4, 5, 6] [1, 8, 7]





主方法类：


package cn.com.hadoop.dfsPath;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Map.Entry;

import cn.com.hadoop.bean.Node;

public class oneTest {

	static HashMap<Integer, Node> nodes = new HashMap<Integer, Node>();
	static Set<Integer> visited = new HashSet<Integer>();
	static int count = 1;
	static ArrayList<Queue<Integer>> paths = new ArrayList<Queue<Integer>>();
	public static double relationDiscover() {

		return 0;
	}

	public static void main(String[] args) throws FileNotFoundException {
		readLittleDirectGraph();//给nodes添加小有向图
		
		Queue<Integer> tmpQ = new LinkedList<Integer>();
		//1.测试一个节点
		paths.add(tmpQ);
		tmpQ.add(7);
		visited.add(7);
		queuePaths(tmpQ);
		if(true)return;
		
		//2.遍历所有节点
		Iterator<Entry<Integer, Node>> iterator=  (Iterator<Entry<Integer, Node>>)nodes.entrySet().iterator();
		while(iterator.hasNext()){
			Entry<Integer, Node> entry = iterator.next();
			int key = entry.getKey();
			Node node = entry.getValue();
			//给定ID，求出以该点为顶点的所有路径
			paths.add(tmpQ);
			
			tmpQ.add(key);
			visited.add(key);

			queuePaths(tmpQ);
			//清除本次ID的所得路径
			paths.clear();
			visited.clear();
			tmpQ.clear();
		}
	}

	/**
	 * 将图数据放入hashmap中<ID,Node>
	 */
	public static void readDirectGraph() {

		File file1 = new File("initColorCite.txt");
		File file2 = new File("newCite.txt");
		FileInputStream fis;
		DataInputStream in;
		BufferedReader br;

		try {
			fis = new FileInputStream(file1);
			in = new DataInputStream(fis);
			br = new BufferedReader(new InputStreamReader(in));

			String strLine;
			while ((strLine = br.readLine()) != null) {// 此次循环，将所有node节点初始化ID及其color.
				String[] parts = strLine.split(" ");

				Node node = new Node(Integer.parseInt(parts[0]),
						Integer.parseInt(parts[1]));
				nodes.put(Integer.parseInt(parts[0]), node);
			}
		} catch (Exception e) {
			e.printStackTrace();
		}

		try {
			fis = new FileInputStream(file2);
			in = new DataInputStream(fis);
			br = new BufferedReader(new InputStreamReader(in));

			String strLine;
			ArrayList<Integer> neighbours = new ArrayList<Integer>();
			while ((strLine = br.readLine()) != null) {
				neighbours.clear();

				String[] parts = strLine.split("\t");
				Node node = nodes.get(Integer.parseInt(parts[0]));
				for (int i = 1; i < parts.length; i++) {
					if (parts[i].equals(""))
						continue;
					neighbours.add(Integer.parseInt(parts[i]));
				}
				node.setNeighbours(neighbours);
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		System.out.println("图！");

	}
	
	/**
	 * 将自定义的小图放入hashmap中<ID,Node>
	 */
	public static void readLittleDirectGraph(){
		ArrayList<Integer> neighborT = new ArrayList<Integer>();
		
		Node node1 = new Node(1, 1);
		neighborT.add(2);
		neighborT.add(3);
		neighborT.add(4);
		neighborT.add(8);
		node1.setNeighbours(neighborT);
		
		Node node2 = new Node(2, 1);
		neighborT.clear();
		neighborT.add(3);
		node2.setNeighbours(neighborT);
		
		Node node3 = new Node(3, 1);
		Node node4 = new Node(4, 1);
		neighborT.clear();
		neighborT.add(5);
		node4.setNeighbours(neighborT);
		
		Node node5 = new Node(5, 1);
		neighborT.clear();
		neighborT.add(6);
		neighborT.add(7);
		node5.setNeighbours(neighborT);
		
		Node node6 = new Node(6, 1);
		neighborT.clear();
		neighborT.add(1);
		node6.setNeighbours(neighborT);
		
		Node node7 = new Node(7, 1);
		neighborT.clear();
		neighborT.add(8);
		node7.setNeighbours(neighborT);
		
		Node node8 = new Node(8, 1);
		neighborT.clear();
		neighborT.add(7);
		node8.setNeighbours(neighborT);
		
		nodes.put(1, node1);
		nodes.put(2, node2);
		nodes.put(3, node3);
		nodes.put(4, node4);
		nodes.put(5, node5);
		nodes.put(6, node6);
		nodes.put(7, node7);
		nodes.put(8, node8);
	}
	
	/**
	 * 正确
	 * 2017.7.6
	 * 传入的是同一层的所有ID，如第一层只有1，第二层为2，3，4，8，第三层为第二层所有ID的neighbors且这些与前几层不重复。
	 * @param paraQueue
	 */
	public static void queuePaths(Queue<Integer> paraQueue ){
		System.out.println(" ~~~~~~~~~~~~~~~~~~~~~~~~   ");
			Queue<Integer> baseQueue = new LinkedList<Integer>(paraQueue);//上一级的路径，不添加本次路径。
			
			Queue<Integer> neighborQueue = new LinkedList<Integer>();
			Queue<Integer> existNeighborQueue = new LinkedList<Integer>();
			System.out.println("visit   " + visited);
			System.out.println("basen   " + baseQueue);
			//遍历队列。将第二层中的ID也加入visited
			Queue<Integer> curQueue = null;
			for (Iterator<Integer> iterator = baseQueue.iterator(); iterator.hasNext();) {
				int i = iterator.next();
				//从paths集合中找到包含i的队列
				for(Queue<Integer> q : paths){
					if(q.contains(i)){
						curQueue = q;
						break;
					}
				}
				
				int c = 0;
				ArrayList<Integer> neighbors = nodes.get(i).getNeighbours();
				Queue<Integer> curTmpQueue = new LinkedList<Integer>(curQueue);
				for(int i1 : neighbors){
					if (visited.contains(i1))
						continue;
					c++;
					if(c>1){
						visited.add(i1);
						existNeighborQueue.add(i1);
						Queue<Integer> newQueue = new LinkedList<Integer>(curTmpQueue);
						newQueue.add(i1);
						paths.add(newQueue);
					}else{
						visited.add(i1);
						existNeighborQueue.add(i1);
						curQueue.add(i1);
					}
				}
			}
			System.out.println("visit   " + visited);
			System.out.println("exist   " + existNeighborQueue);
			//遍历paths
			for (Iterator<Queue<Integer>> iterator = paths.iterator(); iterator.hasNext();) {
				Queue<Integer> q = iterator.next();
				System.out.println(q);
			}
			if (existNeighborQueue.isEmpty()) { //遍历结束，跳出，否则为死循环。
				System.out.println("—————————结束——————————");
				return;
			}
			queuePaths(existNeighborQueue);
		}
}




Node类：


package cn.com.hadoop.bean;

import java.util.ArrayList;

public class Node {
	
	private int id;
	private int color;
	private int initColor;
	private boolean isVisited = false;
	private ArrayList<Integer> neighbours;
	public Node(int id) {
		this.id = id;
	}
	public Node(int id, int initColor) {
		this.id = id;
		this.color = initColor;
		this.initColor = initColor;
		this.neighbours = new ArrayList<Integer>();
	}
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	public int getColor() {
		return color;
	}
	public void setColor(int color) {
		this.color = color;
	}
	public int getInitColor() {
		return initColor;
	}
	
	public ArrayList<Integer> getNeighbours() {
		return neighbours;
	}
	public void setNeighbours(ArrayList<Integer> neighbours) {
		for(int id : neighbours)
			this.neighbours.add(id);
	}
	public boolean getIsVisited() {
		return isVisited;
	}
	public void setIsVisited(boolean isVisited) {
		this.isVisited = isVisited;
	}
	
}



 
文中使用了广度遍历，在此基础上加入了路径添加（即paths.add(newQueue)），剔除重复点加入避免了重复路径（即visited的功能）。

备注：大一学了图后，一段时间没用就还给老师了，如今重新复习一下，理解有误的地方请指教。

有向图和无向图的定义
1）关于有向图，百科中是这样描述的：一个有向图D是指一个有序三元组(V(D)，A(D)，ψD)，其中ψD为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。

理解：如图D，如果e是D的一条边，而这时候存在这样的一个关系，ψD，有A，B两点，使得，ψD（A，B）=e（到底是怎样的关系？我觉得在应用中，需要我们自己制定，就像在预算100元的条件下，你选择怎样的交通工具快速到达目的地），通俗理解：边有方向的图。即AB ！= BA。

[外链图片转存失败(img-OHZsll7R-1567908307459)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483515239_C07BA5588B40E754EB534225BA630A0D “图片标题”)]

（2）平行边：在图中，如果起点和终点相同则称为平行边，平行边的条数则称为重数。如图：e2和e3为平行边，B和C之间的重数为2。

[外链图片转存失败(img-EMKaEUe6-1567908307460)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483671400_6DA66AE52EFE0CF2370DF02226877263 “图片标题”)]

（3）关于无向图：了解了有向图，那它就好理解了，就是有向图中去掉所有的方向，AB=BA，如图，就是去掉D中的所有箭头（此时，又称为基础图，反之给无向图添上箭头的有向图又称为定向图）。

[外链图片转存失败(img-DJM75Udh-1567908307461)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483731056_5FB56EBF13116F56F22CCFD0F068F03B “图片标题”)]

（4）出度和入度：如图D，以点A为例子，在所有与A关联的边中，以A为起点的边的条数称为出度。而入度则刚好相反，以A为终点的边的条数则称为入读。其中，入度+出度，我们称为A的度。注意特殊情况：如图：A有一个自环，起点和终点都是自己，此时出度算一度，入度也算一度。如图：A的出度为3，入度也为2，A的度的5。


（5）邻接矩阵和关联矩阵定义：设D（V,E）是有向图，其中V={v1,v2,v2…vn},E={e1,e2,e3,…em}称A(D)=(aij)nxn是D的领接矩阵，其中aij是以vi为起始点，以vj为终点的边的条数。若图D中无环，则称M(D)=（mij）nxm为关联矩阵。[i，j是下标，n是点的个数，m是边的数量注意：1.关联矩阵是针对边来说的，所以矩阵大小为n*m，它的取值如下：


例子：



（6）补充：对于无向图而言：邻接矩阵则是对称的，且只有0和1，因为没有方向的区别后，要么有边，要么没边：



从图我们可以看到，它是关于对角线对称的一个矩阵，我们在编程中，遍历和存储是只需要关注上半部分或者下半部分即可。



（7）跟邻接矩阵一样，用来存储图中信息的，还有邻接表：如果学过链表了，就很好理解了，首先在一个数组中存储各个点（对象或者成为链），而每个对象又保存着一个next引用指向连接的点在数组中的坐标，如图：A到E在数组中存储后，坐标依次排列，A连B，B的坐标为1，所以指向的地方标记为1，代表A连着B，接着，B连着E，E的坐标为4，这1的引用指向4。
从图我们就可以得出邻接表的存储方式了：即链表加数组，这存储结构比起纯粹用数组（邻接矩阵）要节约很多空间。邻接矩阵，我们需要一个n*n维的数组，复杂度为O（n^2），而邻接表是根据点和边来保存数据的，当一个起点决定后，就采用深度搜索的方法沿着边，保存连接点的信息，复杂度为O(n+m）
另外，若果是有向图，我们在保存下一个顶点时，还需要保存边的权值，看图中每个格子都分成两小格了吗，第二个小格子就是用来存储权值的。
图来自百度词条，好难画



拓扑排序
百度词条这样描述：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。

理解:（1）根据定义，我们可以知道它是针对有向图而言的.（2）它是一个包含有向图的所有点的线性序列，且满足两个条件：a.有向图的每个顶点只出现一次。b.若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 应该出现在顶点 B 的前面。
备注：图来源于百度，之前都没发现，它的786，应该是678，C0是连着C2和C6的

[外链图片转存失败(img-q5yfBWrf-1567908307464)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539485618410_F203E6F40B767104E9635E84C103CA7C “图片来源于百科”)]
（2）注意，拓扑排序并不是唯一的，它的排序方式：以上图为例子：a.首先我们从有向图图中选择一个没有前驱（即入度为0）的顶点并输出，这里我们可以选择c0或者c1。b.从图中删除输出的顶点和所有以它为起点的有向边。c.循环 a步骤 和 b步骤，终止条件为当前的有向图为空或当前图中不存在无前驱的顶点为止。备注：若当前图中不存在无前驱的顶点，说明有向图中必然存在环。

DFS大法好！

DFS作为搜索算法，最常用于图，对图的遍历，探寻路径，甚至是求一些情况下的最短路。我在这里就介绍一下dfs求两点的的所有路径，这个算法最开始在数据结构大作业里面用到了，当时费了一番劲写出来后，就想oj题里面这么变态的算法肯定不会出，后来还真的见过了。。。

哈密顿绕行世界问题 HDU - 2181 
就以这张图为介绍，v1是出发点，v3是终点：



v1开始出发，v1被标记访问过，并入栈，到v2，标记并入栈；
到v3，此时v3是终点，到达函数开始的判断条件，输入堆栈经过的路径。一条路找到（1,2,3）。此时虽然v3可以到v5，但也没有必要探寻下去：算法的角度来说如果继续探寻下去v3就会被标记，就算有路可以到，下次就不会背进入递归了；实际应用来说也没必要绕一圈再到一个地方。这算是一个剪枝吧。
v3回溯到v2，v2没有可走的路了，堆栈中的v2出栈，v2并取消标记；
v2回溯到v1，有v4可走，入栈并标记。探寻v2可走，入栈并标记。v2到v3，另一条路找到（1,4,2,3）；
从v3回溯到v4，探寻到v5可走，入栈并标记；
v5没路可走了，回溯到v4到v1，程序结束。

输入样例
5 6

1 2
2 3
3 5
1 4
4 2
4 5

1 3

输出样例
1 2 3
1 4 2 3

#include<stdio.h>
#include<math.h>
int map[100][100]={0};///map[i][j]为0表示i, j两点之间不通，为1表示有一条路
int stack[120],v[100]={0},top=0,m,n,start,end;
void dfs(int pos)//从pos点开始访问
{
	int i;
	if(pos==end){//到达终点
		for(i=0;i<top;i++)
			printf("%d ",stack[i]);
		printf("%d\n",end);	
		return;
	}
	v[pos]=1;//标记被访问过 
	stack[top++]=pos;//经过的路径加入队列
	for(i=1;i<=n;i++){
		if(!v[i]&&map[pos][i])//如果这个点没有被访问过，而且b与这个点相连，就继续搜索
			dfs(i);
	}
	v[pos]=0;//删除标记 
	top--;//队列里删除b
}

int main()
{
    int i,x,y;
    printf("分别输入顶点数n和路径数m："); 
    scanf("%d %d",&n,&m);//n是顶点数，m是边数 
    
    printf("输入m条路径："); 
    for(i=1; i<=m; i++) {
        scanf("%d %d", &x,&y);
        map[x][y] = 1;//这两点之间有路径
		//map[y][x] = 1; //无向图加上这一句即可 
    }
    
    printf("输入起始点和终点：");
    scanf("%d %d", &start,&end);
    
    printf("\n程序执行结果为：\n"); 
    dfs(start);
    return 0;
    
}

想要知道每条路径的长度也很容易，输入信息的时候加上路径长度，函数多一个参数，每次递归的时候加上这两点路径的长度，到达终点输出就行了，求最短路的话每次到终点比较一下就好了。这里我就不再多写了。

以下为原话。。。。

用数组代替堆栈了，c写堆栈不方便。数据结构大作业要用到这个算法，昨天整整一下午还有晚自习都在找这个算法，今天才发现昨天一直多输出一个东西，那是测试用的，开始写的没删掉，就一直以为错了。今天才努（tao）力（ke）写出来了，2333。

附上我的大作业：校园导航系统

JAVA代码详解： 有向图中判断欧拉路径和欧拉回路

欧拉路径是图中访问每一条边一次的路径。

欧拉回路是在同一顶点上开始和结束的欧拉路径。

有欧拉回路的图称为欧拉图。

上一篇博客讨论了无向图的欧拉回路。接下来这一篇博客讨论有向图中判断欧拉路径和欧拉回路问题。

例如，下图的欧拉循环为1、0、3、4、0、2、1




如何检查有向图是否是欧拉图？

如果以下条件为真（成立），则有向图具有欧拉回路

1）所有非零度顶点都属于单个强连通分量。

2）每个顶点的进出度相同。

在计算机科学中，Kosaraju的算法（也称为Kosaraju-Sharir算法）是线性时间的算法来找到一个有向图的强连通分量。

为了比较进度和出度，我们需要存储每个顶点的进度和出度。通过邻接表的大小，可以得到输出度。通过创建一个大小等于顶点数的数组，可以存储度数。

package com.bean.algorithm.basic;

import java.util.Iterator;
import java.util.LinkedList;

public class EulerCircuit6 {

	private int V; // 顶点数量
	private LinkedList<Integer> adj[];// 邻接表
	private int in[]; // 维护入度

	EulerCircuit6(int v) {
		V = v;
		adj = new LinkedList[v];
		in = new int[V];
		for (int i = 0; i < v; ++i) {
			adj[i] = new LinkedList();
			in[i] = 0;
		}
	}

	void addEdge(int v, int w) {
		adj[v].add(w);
		in[w]++;
	}

	void DFSUtil(int v, Boolean visited[]) {
		// 将当前节点标记为已访问
		visited[v] = true;

		int n;

		// 对与此顶点相邻的所有顶点遍历
		Iterator<Integer> i = adj[v].iterator();
		while (i.hasNext()) {
			n = i.next();
			if (!visited[n])
				DFSUtil(n, visited);
		}
	}

	// 返回此图的反转（或转置）
	EulerCircuit6 getTranspose() {
		EulerCircuit6 g = new EulerCircuit6(V);
		for (int v = 0; v < V; v++) {
			// 对与此顶点相邻的所有顶点遍历
			Iterator<Integer> i = adj[v].listIterator();
			while (i.hasNext()) {
				g.adj[i.next()].add(v);
				(g.in[v])++;
			}
		}
		return g;
	}

	// 如果图是强连接的，则返回true
	Boolean isSC() {
		// Step 1: 将所有顶点标记为未访问（对于第一个DFS）
		Boolean visited[] = new Boolean[V];
		for (int i = 0; i < V; i++)
			visited[i] = false;

		// Step 2: 从第一个顶点开始进行DFS遍历.
		DFSUtil(0, visited);

		// 如果DFS遍历没有访问所有顶点，则返回false.
		for (int i = 0; i < V; i++)
			if (visited[i] == false)
				return false;

		// Step 3: 创建一个反转图
		EulerCircuit6 gr = getTranspose();

		// Step 4: 将所有顶点标记为未访问（对于第二个DFS）
		for (int i = 0; i < V; i++)
			visited[i] = false;

		// Step 5: 从第一个顶点开始对反转图执行DFS.
		// 起始顶点必须与第一个DFS的起始点相同
		gr.DFSUtil(0, visited);

		// 如果在第二个DFS中未访问所有顶点，则返回false
		for (int i = 0; i < V; i++)
			if (visited[i] == false)
				return false;

		return true;
	}

	/*
	 * 如果有向图有欧拉回路，则此函数返回true； 否则返回false
	 */
	Boolean isEulerianCycle() {
		// 检查是否连接了所有非零度顶点
		if (isSC() == false)
			return false;

		// 检查每个顶点的进出度是否相同
		for (int i = 0; i < V; i++)
			if (adj[i].size() != in[i])
				return false;

		return true;
	}

	public static void main(String[] args) throws java.lang.Exception {
		EulerCircuit6 g = new EulerCircuit6(5);
		g.addEdge(1, 0);
		g.addEdge(0, 2);
		g.addEdge(2, 1);
		g.addEdge(0, 3);
		g.addEdge(3, 4);
		g.addEdge(4, 0);

		if (g.isEulerianCycle())
			System.out.println("给定的有向图中 存在 欧拉回路 eulerian ");
		else
			System.out.println("给定的有向图中 不存在 欧拉回路 eulerian ");
	}

}


程序运行结果：

给定的有向图中 存在 欧拉回路 eulerian