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

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

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

有向图的路径发现

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

图： 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的功能）。

 有向图:   

:  

找出 途中 从 A  到  F  一共有多少中走法,  包含的闭环 有哪些   

构思:   

遍历前  先准备一个 list 用来存放当前路径,

从A开始  先找到B  ,B找到D, D 到F,   此时  F为所找目标节点,  此时算是找到一条路径,     此时路径为    A ,B,D,F

接下来  从 F 返回上一层   D   再找D 的另一个节点  C   ,C有两个子节点, 随便选一个  B,  此时 当前路径中存在一个B,重复了, 所以此处是一个环,  然后返回上一级C   再从C到 E   E到F ,   此时路径为   A ,B,D,C,E,F 

再依次返回, 每上一层 都遍历找没有被访问过的子节点,    直到访问结束.

(如果看不明白的童鞋还是多跑几次代码 ,然后找规律吧.这个确实不太好解释哈)

其中用到递归

上代码:     

/**
 * @Annotion:   节点实体,一个实体对应的是一条线,链接两个节点
 * @ClassName: Node
 * @Author:
 * @Date: 2019/9/29  10:11
 * @Version: 1.0
 */
public class Node {
    /**上游节点*/
    private String source;
    /**下游节点*/
    private String target;

    public Node(String source, String target) {
        this.source = source;
        this.target = target;
    }

    public String getSource() {
        return source;
    }

    public void setSource(String source) {
        this.source = source;
    }

    public String getTarget() {
        return target;
    }

    public void setTarget(String target) {
        this.target = target;
    }
}

/**
 * @Annotion: 从  一个点  到另一个点所有路径走法 ,并输出环
 * @ClassName: TwoPointsPath
 * @Author: 
 * @Date: 2019/9/29  9:54
 * @Version: 1.0
 */
public class PointsPath {
    /**当前路径*/
    private static List<String> nowPath = new ArrayList<>();

    /**
     *
     * @param nodeList
     * @param source 起始节点
     * @param target 目标节点
     */
    public static void findAllPath(List<Node> nodeList,String source,String target){
        if(nowPath.contains(source)){
            System.out.println("这是一个环:"+nowPath);
            nowPath.remove(nowPath.size()-1);
            return;
        }
        for(int i = 0 ;i<nodeList.size();i++){
            Node node = nodeList.get(i);
            if(node.getSource().equals(source)){
                nowPath.add(node.getSource());
                if(node.getTarget().equals(target)){
                    nowPath.add(node.getTarget());
                    System.out.println("这是一条路径:"+nowPath);
                    /*因为添加了终点路径,所以要返回两次*/
                    nowPath.remove(nowPath.size()-1);
                    nowPath.remove(nowPath.size()-1);
                    /*已经找到路径,返回上层找其他路径*/
                    continue;
                }
                findAllPath(nodeList,node.getTarget(),target );
            }
        }
        /*如果找不到下个节点,返回上层*/
        if(nowPath.size()>0){
            nowPath.remove(nowPath.size()-1);
        }

    }

    /**
     * 测试
     */
    public static void main(String[] args){
        List<Node> list = new ArrayList<>();
        list.add(new Node("A", "B"));
        list.add(new Node("A", "C"));
        list.add(new Node("B", "D"));
        list.add(new Node("D", "F"));
        list.add(new Node("D", "C"));
        list.add(new Node("C", "B"));
        list.add(new Node("C", "E"));
        list.add(new Node("E", "F"));

        findAllPath(list,"A","F");
    }

}

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

有向图和无向图的定义

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步骤，终止条件为当前的有向图为空或当前图中不存在无前驱的顶点为止。备注：若当前图中不存在无前驱的顶点，说明有向图中必然存在环。