有向图中以一个顶点为起始点的所有路径
程序员文章站
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的功能)。