算法题1道急求

答：提问的艺术。--你究竟想做什么呢？
a,b},{b,c},{b,d},{c,d},{d,e},{g,h}}转化为{a,b,c,d,e} {a,b,d,e} {g,h}
我比较笨，没有看出“转化”的规则是什么。
请以后提问题时，描述你究竟想做什么，说得越详细越好。否则你的问题大家没有办法解决。

哦是这样的
比较2位数组中每两个子数组的前一个字符和后一个字符，如果相等就将这个链放入令一个数据结构中比如{a,b}和{b,c}比较后放入{a,b,c}， {b,c}和{c,d}比较后发现{c,d}是这个链式接着的发展趋势，于是把d再放入形成{a,b,c,d}，{c,d}和{d,e}将e放入{a,b,c,d,e}
谢谢达人求解

不好意思啊描述起来确实很费劲，呵呵而且本人描述能力也比较差呵呵
我再说具体点吧
这是我毕业设计中遇到的一道问题，我的毕业设计有关于灾害的链式管理。
这个具体意义是这样的这个2维数组中的每一个字符代表一个灾害的编号，如a。
而每一个子数组代表一个灾害之间的引发关系，如{a,b}代表着灾害a引发了灾害b。
这样在这个2维数组中就有很多灾害引发关系，如{a,b}代表灾害a引发了灾害b，{b,c}代表灾害b引发了灾害c，{c,d}代表灾害c引发了灾害d。这里明显就有着这样一个链式关系，即a引发b引发c引发d，于是将它们放入一个1维数组中（或一个其它数据结构中，如VECTOR）,形成了一个灾害链式{a,b,c,d}.谢谢各位大侠了，小弟等

答：其实就是求关系的传递闭包而已。
可用warshall算法。程序如下：
public class Warshall {// s数组表示灾害之间引发关系
static char[][] s={{'a','b'},{'b','c'},{'b','d'},{'c','d'},{'d','e'},{'g','h'}};

//pos数组表示一共有多少个不同的灾害：下标0-第一个灾害，下标1-第二个灾害
static int[] pos={'a','b','c','d','e','g','h'};

//数组b是求最终的灾害关系的传递闭包。即：所有的灾害链。此时全为false
//数组b也就是最终结果
    static boolean[][] b=new boolean[pos.length][pos.length];



    //对数组b初始化。按照数组s来进行。
    private static void init()
    {
     for(int i=0; i<s.length;i++)
     {
     b[index(s[i][0])][index(s[i][1])]=true;
     //含义：两维数组b中，若'a'与'b'有灾害关系，则b['a']['b']填true。无关是false.
     b[i][i]=true;//关系的自己性
     }//for(i)

    }

//  求关系a的传递闭包
public static void warshall(boolean[][] a)
{
for(int i=0;i<=a.length-1;i++)
{
for(int j=0;j<=a.length-1;j++)
{
if(a[j][i]==true)
{
for(int k=0;k<=a.length-1;k++)
{
a[j][k]=a[j][k] | a[i][k];
}//for(k)
}//if
}//for(j)
}//for(i)

}//warshall

//打印出最终结果
public static void print(boolean[][] a)
{
for(int i=0;i<a.length;i++)
{
System.out.print("灾害："+(char)pos[i]+" 所引发的灾害链是：{");
for(int j=0;j<a.length;j++)
{
if(a[i][j]==true){
System.out.print((char)pos[j]+" ");
}
}//for(j)
System.out.print("} \n");
}//for(i)
}

//返回字符ch在数组pos中的下标
private static int index(char ch)
{
for(int i=0;i<pos.length;i++)
{
if(pos[i]==ch)
{ return i; }
}
return -1;
}

public static void main(String[] args) {
  init();  //对数组b初始化。
      warshall(b);//求出所有的灾害链
      print(b);//打印出所求的结果
}}
程序运行的结果如下：
灾害：a 所引发的灾害链是：{a b c d e }
灾害：b 所引发的灾害链是：{b c d e }
灾害：c 所引发的灾害链是：{c d e }
灾害：d 所引发的灾害链是：{d e }
灾害：e 所引发的灾害链是：{e }
灾害：g 所引发的灾害链是：{g h }
灾害：h 所引发的灾害链是：{}

答：对不起。上边程序有个小BUG，更新如下：
public class Warshall {// s数组表示灾害之间引发关系
static char[][] s={{'a','b'},{'b','c'},{'b','d'},{'c','d'},{'d','e'},{'g','h'}};

//pos数组表示一共有多少个不同的灾害：下标0-第一个灾害，下标1-第二个灾害
static int[] pos={'a','b','c','d','e','g','h'};

//数组b是求最终的灾害关系的传递闭包。即：所有的灾害链。此时全为false
//数组b也就是最终结果
    static boolean[][] b=new boolean[pos.length][pos.length];



    //对数组b初始化。按照数组s来进行。
    private static void init()
    {
     for(int i=0; i<s.length;i++)
     {
     b[index(s[i][0])][index(s[i][1])]=true;
     //含义：两维数组b中，若'a'与'b'有灾害关系，则b['a']['b']填true。无关是false.
       }//for(i)
     for(int i=0;i<b.length;i++)
     {
     b[i][i]=true;//关系的自反性
     }

    }

//  求关系a的传递闭包
public static void warshall(boolean[][] a)
{
for(int i=0;i<=a.length-1;i++)
{
for(int j=0;j<=a.length-1;j++)
{
if(a[j][i]==true)
{
for(int k=0;k<=a.length-1;k++)
{
a[j][k]=a[j][k] | a[i][k];
}//for(k)
}//if
}//for(j)
}//for(i)

}//warshall

//打印出最终结果
public static void print(boolean[][] a)
{
for(int i=0;i<a.length;i++)
{
System.out.print("灾害："+(char)pos[i]+" 所引发的灾害链是：{");
for(int j=0;j<a.length;j++)
{
if(a[i][j]==true){
System.out.print((char)pos[j]+" ");
}
}//for(j)
System.out.print("} \n");
}//for(i)
}

//返回字符ch在数组pos中的下标
private static int index(char ch)
{
for(int i=0;i<pos.length;i++)
{
if(pos[i]==ch)
{ return i; }
}
return -1;
}

public static void main(String[] args) {
  init();  //对数组b初始化。
      warshall(b);//求出所有的灾害链
      print(b);//打印出所求的结果
}}
程序运行结果如下：
灾害：a 所引发的灾害链是：{a b c d e }
灾害：b 所引发的灾害链是：{b c d e }
灾害：c 所引发的灾害链是：{c d e }
灾害：d 所引发的灾害链是：{d e }
灾害：e 所引发的灾害链是：{e }
灾害：g 所引发的灾害链是：{g h }
灾害：h 所引发的灾害链是：{h }

这个写得非常好可是您看啊
我要的结果不是把所有的灾害为起点的链取出来而是将一个一个单独的不包含的链取出
比如您的结果中{a b c d e}就包含{b c d e} {c d e } {d e} { e }这5个链其实就是{a b c d e}这一个链
而您的结果中不包含我要的另一条链{a b d e}
还是非常感谢您但是这个逻辑确实不好弄您做的我都弄不好呵呵
希望您再帮我个忙
也希望大家帮忙谢谢了

楼上似乎理解错了楼主的意思了。warshall算法复杂度是n的立方，不知有没有高效点的算法。

关注！如果出现 {a,b},{b,c},{c,a} 的情况怎么办? 这种情况应不应该出现？

贴上我的程序，能够输出楼主要的结果，仅供参考。
import java.util.ArrayList;
import java.util.Iterator;public class Pizza {
String[][]sr;
ArrayList<ArrayList> rvList=new ArrayList<ArrayList>();

public  void  reverseArray(String[][]sr){
this.sr=sr;

for(int i=0;i<sr.length;i++){
if(isHead(i)){
ArrayList<String> list=new ArrayList<String>();
reverseloop(i,list);
}
}
}
private  void reverseloop(int index,ArrayList<String> alist){

if(alist.size()==0){
alist.add(sr[index][0]);
}

alist.add(sr[index][1]);

if(isTail(index)){
rvList.add(alist);
return ;
}

for(int i=0;i<sr.length;i++){
if(i!=index){
if(sr[i][0].equals(sr[index][1]) ){
ArrayList<String> a=new ArrayList<String>();
a.addAll(alist);
reverseloop(i,a);
}
}
}

}
private  boolean isHead(int index){
for(int i=0;i<sr.length;i++){
if(i!=index){
if(sr[i][1].equals(sr[index][0])){
return false;
}
}
}
return true;
}
private  boolean isTail(int index){
for(int i=0;i<sr.length;i++){
if(i!=index){
if(sr[i][0].equals(sr[index][1])){
return false;
}
}
}
return true;
}
public static void main(String[] args) {
//String[][] ss={{"b","d"},{"c","d"},{"d","e"},{"g","h"},{"a","b"},{"b","c"}};
String[][] ss={{"001","002"},{"001","003"},{"002","003"},{"004","005"}} ;

Pizza s=new Pizza();
s.reverseArray(ss);
for (Iterator iter = s.rvList.iterator(); iter.hasNext();) {
ArrayList<String> element = (ArrayList<String>) iter.next();

for (Iterator iterator = element.iterator(); iterator.hasNext();) {
String element1 = (String) iterator.next();
System.out.print(element1+"   " );
}
System.out.println();
}
System.out.println(s.rvList.size());
}
}

答：对不起。看来是我理解错误。
到现在，我还是不明白：将{{a,b},{b,c},{b,d},{c,d},{d,e},{g,h}}转化为{a,b,c,d,e} {a,b,d,e} {g,h} 中的{a,b,d,e}是怎么转化出来的？
看为我比较笨。
楼上javaflee说他的程序达到你的要求。你多看看吧。因为我看不懂。转换规则我还是不大明白。

晕，才看懂.它其实是一种因果关系，没什么数学联系。
{{a,b},{b,c},{b,d},{c,d},{d,e},{g,h}}转化为{a,b,c,d,e}  {a,b,d,e}  {g,h}
分解为：
{{a,b},{b,c},                        转化为{a,b,c}
{{a,b},{b,c},{b,d},                  转化为{a,b,c}  {a,b,d}
{{a,b},{b,c},{b,d},{c,d},            转化为{a,b,c,d}  {a,b,d}
{{a,b},{b,c},{b,d},{c,d},{d,e}       转化为{a,b,c,d,e}  {a,b,d,e}
{{a,b},{b,c},{b,d},{c,d},{d,e},{g,h}}转化为{a,b,c,d,e}  {a,b,d,e}  {g,h} 同理{{"001","002"},{"001","003"},{"002","003"},{"004","005"}} 转化为 {"001","002","003"} {"001","003"} {"004","005"}

答：谢谢 nothing123 的解释。现在才算明白了。那就是 javaflee 的程序是正解了。

感觉符合二叉树的定义
解决步骤分析如下：1 ，根据关联关系可以将所给集合划分为若干个子集合，这些子集合之间没有关联关系。
2 ，在每个集合中找到可以做为根节点的元素（也就是第一个元素按照字母表最靠前的，可能有不止一个），以此元素做为
根节点建立二叉树（如 jayflee 所说，可能存在循环）。
3 ，结果就是所有二叉树的所有分支的集合。个人观点，仅供参考

jayflee正解非常感谢大家的帮助，结帖了，呵呵。

nothing 看的对啊呵呵猛

调试易

算法题1道急求

解决方案 »

算法题1道 急求

解决方案 »

算法题1道急求