欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-15 18:59:12
...

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

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

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


有向图的路径发现

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

图: 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的功能)。

相关标签: 有向图 路径