数据结构算法问题
目前有两个List
其中一个内容是 1,2,3,4,5,6,7,8,8,9,4,4,10
另一个内容是 2,3,4,5,6,7,8,9,15,8,16,3,11
其中第一个list是起点 第二个list是终点 比如起点是1 终点是2 ， 启动2终点是3 ，起点是3 终点是4 ， 启动时4 终点是5， 启点是5 终点是6 ， 。。。。。。。。。。
我想通过这两个list查询出以下链路
链路1:1-2-3-4-5-6-7-8-9
链路2:1-2-3-4-16
链路3:1-2-3-4-5-6-7-8-15
链路4:10-11
请问大家有没有好的算法 请提供以下 最好能附上代码。
[最优解释]
其实这是一个图的另一种邻接点的存储方式，可以使用图的深度优先搜索遍历。
package com.tur.demo;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Route {
public static List<String> paths = new ArrayList<String>();
/**
* 查找元素在数组中的下标，如果找不到，返回-1
* @param array
* @param number
* @param startIndex
* @return
*/
public static int indexInArray(int[] array, int number, int startIndex) {
for (int i = startIndex; i < array.length; ++i) {
if (array[i] == number) {
return i;
}
}
return -1;
}
/**
* 把List使用String形式表示
* @param list
* @param delimeter
* @return
*/
public static String listToString(List<Integer> list, String delimeter) {
StringBuilder sb = new StringBuilder();
for (int n : list) {
sb.append(delimeter);
sb.append(n);
}
return (sb.length() > 0 ? sb.substring(delimeter.length()) : "");
}
/**
* 把路径加到入路径列表，并去掉重复的路径
* @param path
*/
public static void addPath(String path) {
boolean included = false;
for (int i = 0; i < paths.size(); ++i) {
String str = paths.get(i);
if (path.contains(str)) {
paths.set(i, path);
included = true;
break;
} else if (str.contains(path)) {
included = true;
break;
}
}
if (!included) {
paths.add(path);
}
}
public static void main(String[] args) {
int[] startPoints = {1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 4, 4,10};
int[] endPoints = {2, 3, 4, 5, 6, 7, 8, 9, 15, 8, 16, 3, 11};
List<Integer> path = new LinkedList<Integer>();
for (int i = 0; i < startPoints.length; ++i) {
path.add(startPoints[i]);
travel(startPoints, endPoints, i, path);
path.remove(new Integer(startPoints[i]));
}
for (String str : paths) {
System.out.println(str);
}
}
/**
* 深度优先搜索路径
*
* @param startPoints
* @param endPoints
* @param startIndex
* @param path
*/
public static void travel(int[] startPoints, int[] endPoints, int startIndex, List<Integer> path) {
if (startIndex == -1) { return; }
int end = endPoints[startIndex];
path.add(end);
for (int i = startIndex; i < (startPoints.length) && startIndex != -1; ++i) {
startIndex = indexInArray(startPoints, end, i + 1);
travel(startPoints, endPoints, startIndex, path); // 深度搜索邻接点
}
addPath(listToString(path, "-"));
path.remove(path.size() - 1);
}
}
/**
*
*/
package qian.iteye;
import java.util.ArrayList;
import java.util.List;
/**
* <p>Objective: </p>
* <p>Description: </p>
* <p>Company: 天津正欣信息技术有限公司 </p>
* <p>Copyright: Copyright (c) 2010-2012</p>
* @version 1.0
* @date: 2012-11-28 下午1:23:24
* @author Administrator
* @project Test1
* @file_name ItEyeQues.java
* @type_name ItEyeQues
* @tags
*/
public class ItEyeQues
{
private int[] int1 = {1,2,3,4,5,6,7,8,8,9,4,4,10};
private int[] int2 = {2,3,4,5,6,7,8,9,15,8,16,3,11};
/**
* 传入一个终点，返回他对应的起点坐标
* @param i
* @return
*/
public List<Integer> getIndex(int i) {
List<Integer> index = new ArrayList<Integer>();
for(int j = 0; j < int1.length; j++) {
if(int1[j] == i) {
index.add(j);
}
}
return index;
}
/**
* 启动程序，初始化值
*/
public void getPath() {
for(int i = 0 ; i < int1.length; i++) {
int startIndex = i;
StringBuffer path = new StringBuffer();
buildPath(startIndex, path);
}
}
/**
* 防止回路 如 1-2-3-4-5-6-7-8-9-8
* @param end
* @param sb
* @return
*/
public boolean check(int end, StringBuffer sb) {
String[] str = sb.toString().split("-");
for(int i =0; i < str.length; i++) {
if(!"".equals(str[i])) {
if(Integer.parseInt(str[i]) == end) {
return false;
}
}
}
return true;
}
/**
* 递归算法
* @param startIndex
* @param sb
*/
public void buildPath(int startIndex,StringBuffer sb) {
int start = int1[startIndex];
int end = int2[startIndex];
if(check(end,sb) == false) {
System.out.println(sb.toString());
return;
}
if(sb.length() == 0) {
sb.append(start + "-" + end);
} else {
sb.append("-" + end);
}
List<Integer> list = getIndex(end);
if(list.size() == 0) {
System.out.println(sb.toString());
return;
}
for(int n = 0; n < list.size(); n++) {
int startindex = list.get(n);
buildPath(startindex, new StringBuffer(sb.toString()));
}
}
/**
* test
* @param args
*/
public static void main(String[] args) {
ItEyeQues it = new ItEyeQues();
it.getPath();
}
}
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
*
* @date 28/11/2012
*/
public class LinkCheck {
public static void main(String[] args) {
List<Integer> starts = Arrays.asList(1,2,3,4,5,6,7,8,8,9,4,4,10);
List<Integer> ends = Arrays.asList(2,3,4,5,6,7,8,9,15,8,16,3,11);
int len = Math.min(starts.size(), ends.size());
Set<Link> links = new HashSet<Link>(len);
for(int i=0; i<len; i++)
links.add(new Link(starts.get(i), ends.get(i)));
int[][] lists = new int[][] {
{1, 2, 3, 4, 5, 6, 7, 8, 9},
{1, 2, 3, 4, 16},
{1, 2, 3, 4, 5, 6, 7, 8, 15},
{10, 11}
};
for(int[] list : lists) {
boolean valid = true;
for(int i=1; valid && i<list.length; i++) {
if( !links.contains(new Link(list[i-1], list[i])) )
valid = false;
}
System.out.println(valid);
}
}
}
class Link {
private final int start;
private final int end;
Link(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int hashCode() {
return (start << 5) - start + end;
}
@Override
public boolean equals(Object o) {
if( o instanceof Link ) {
Link t = (Link)o;
return t.start == this.start && t.end == this.end;
}
else {
return false;
}
}
}
1-2-3-4-5-6-7-8-9-8
1-2-3-4-5-6-7-8-15
1-2-3-4-16
1-2-3-4-3
10-11
Integer[] startPoints1 = {1,2, 3, 4, 5, 6, 7, 8, 8, 9, 4, 10,11,11,2,13,12,13,6,14,8,8};
Integer[] endPoints1 = {2, 3, 4, 5, 6, 7, 8, 9, 15, 8, 3, 11, 3,12,12,12,13,5,14,8,14,15};
打印的链路如下
1-2-3-4-5-6-7-8-9-8-14
1-2-3-4-5-6-7-8-9-8-15
1-2-3-4-5-6-7-8-15
1-2-3-4-5-6-7-8-14
1-2-3-4-5-6-14-8-14
1-2-3-4-5-6-14-8-15
1-2-3-4-3
1-2-12-13-5
10-11-3
10-11-12-13-5
13-12-13-5
打印以上链路不太对 没有满足下面两个条件
第一 13不是链路的第一个节点 所以应存在13-12-13-5这条链路也就是链路的开始节点只能是1或者10
第二 1-2-3-4-3 这条链路有点问题 应该仅仅是1-2-3-4 就可以了 不应该再打印3了 应该已经重复了。
[其他解释]
第二 1-2-3-4-3 这条链路有点问题 应该仅仅是1-2-3-4 就可以了 不应该再打印3了 应该已经重复了。
这个是一个回路，例如可以从4很方便的走回3，不需要可以在path.add(end);这里判断end节点是否已经在path里了，如果在，就直接返回
[其他解释]
兄弟 上面那两个逻辑好处理 修改修改就ok了 但是这个深度查询方法 应该不支持这种情况吧 比如下面这两个list
[234=1001, 234=1, 91=1, 150=1, 316=1]
[150=1, 316=1, 270=1, 234=1, 91=1]
用你的代码打印出3条链路如下
第一条:234=1001-150=1-234=1
第二条:234=1-316=1-91=1
第三条:91=1-270=1
但是很明显 这种情况 只能有一条链路啊 234=1001-150=1-234=1-316=1-91=1-270=1
[其他解释]
int[] startPoints = {1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 4, 10, 11, 11, 2, 13, 12, 13, 6, 14, 8, 8};
int[] endPoints = {2, 3, 4, 5, 6, 7, 8, 9, 15, 8, 3, 11, 3, 12, 12, 12, 13, 5, 14, 8, 14, 15};
第一 13不是链路的第一个节点 所以应存在13-12-13-5这条链路也就是链路的开始节点只能是1或者10
与13对应的是12，13应该是开始结点
[其他解释]
