想知道是否有这样一种算发

Question

比如说我有这样的一些输入：
a->b,
a->c,
b->d,
d->a,
....等等有许多这样的输入，有没有什么算法可以找出一个循环出来的？这个例子比如说找出a->b->d->a.
谢谢

Answer 1

import java.util.ArrayList;
import java.util.List;public class Test2 {
public static void main(String[] args) {
//模拟映射关系，由每个元素的第一个到第二个，并加入数据
List<String> data = new ArrayList<String>();
data.add("ab");
data.add("ac");
data.add("bd");
data.add("dc");

System.out.println(getRetate(data));
}

public static String getRetate(List<String> data) {
//找到一个最大长度是list.size()的循环
StringBuffer sb = new StringBuffer();
String temp = data.get(0);
sb.append(temp.substring(0, 1) + "->" + temp.substring(1, 2));
for(int i=0; i<data.size(); i++) {
for(int j=0; j<data.size(); j++) {
if(data.get(i).startsWith(temp.substring(1,2))) {
temp = data.get(i);
sb.append("->" + temp.substring(1, 2));
break;
}
}
}
return sb.toString();
}
}

Answer 2

我想可能是我没说清楚，我需要从这些a->b, a->c, 等等中寻找一个回路，等于说从起点，绕了一圈又回到起点这种情况，如果没有就什么都不输出，如果有则输出这个回路。

Answer 3

import java.util.ArrayList;
import java.util.List;public class Test2 {
public static void main(String[] args) {
//模拟映射关系，由每个元素的第一个到第二个，并加入数据
List<String> data = new ArrayList<String>();
data.add("ab");
data.add("ac");
data.add("bd");
data.add("dc");
data.add("ca");
//System.out.println(data);

System.out.println(getRotate(data));
}

public static String getRotate(List<String> data) {

StringBuffer result = new StringBuffer();
boolean find = false;
//循环找出所有的环
for(int i=0; i<data.size(); i++) {
StringBuffer sb = new StringBuffer();
String temp = data.get(i);
String start = temp.substring(0, 1);
String end = temp.substring(1, 2);
sb.append(start + "->" + end);
for(int j=0; j<data.size(); j++) {
temp = data.get(j);
if(end.equals(temp.substring(0, 1))) {
end = temp.substring(1, 2);
sb.append("->" + end);
if(end.equals(start)) {
find = true;
break;
}
}
}
if(find) {
result.append(sb.toString() + ";");
find = false;
}
}
return result.toString();
}
}
这个能满足楼主的需求了，可以找出所有的环！请大家指正！

Answer 4

你好，好像是有点问题，比如说这种情况
        data.add("ab");data.add("ba");
        data.add("ac");data.add("ca");
        data.add("bc");data.add("cb");您的方法确实能搜索出一些回路，但似乎不能搜索出全部的来，如果可能的话，请你再改进一下，让我学习一下。

Answer 5

a->c
a->b
c->e
e->c
c->b
b->a大家看看这样搜可以不：
循环中先保存一个start假如是a，再在所有end中找a，再更具存在a的end知道start .....逆向查找，如果查到start是a即查到环，del这个环的第一对，继续查start是a
但这样在查start是b的情况时就要重建array

Answer 6

先建立图模型，然后用解决路径回路的办法来解决。下面代码供参考：
public class MyNode {
    private boolean visit;    private boolean localVist;    private String value;    private List<MyNode> neighbors;    MyNode(String value) {
        this.value = value;
        neighbors = new LinkedList<MyNode>();
    }    public String getValue() {
        return this.value;
    }    public List<MyNode> getNeighbors() {
        return neighbors;
    }    public boolean isVisit() {
        return visit;
    }    public void setVisit(boolean visit) {
        this.visit = visit;
    }    public boolean isLocalVist() {
        return localVist;
    }    public void setLocalVist(boolean localVist) {
        this.localVist = localVist;
    }
}
public class Graph {    private List<MyNode> graph;    private HashMap<String, MyNode> hash;    Graph() {
        graph = new ArrayList<MyNode>();
        hash = new HashMap<String, MyNode>();
    }    public void AddNode(String value) {
        MyNode node = new MyNode(value);
        graph.add(node);
        hash.put(value, node);
    }    public void AddEdge(String from, String to) {
        MyNode add = null;
        if (hash.get(to) != null)
            add = hash.get(to);
        else {
            add = new MyNode(to);
            graph.add(add);
            hash.put(to, add);
        }
        hash.get(from).getNeighbors().add(add);
    }    void FindAllLoop() {
        for (int i = 0; i < graph.size(); ++i) {
            List<MyNode> loop = new ArrayList<MyNode>(); //每个回路中所包含的结点
            loop.add(graph.get(i));
            graph.get(i).setVisit(true);
            graph.get(i).setLocalVist(true);
            AssistantFind(graph.get(i).getNeighbors().iterator(), graph.get(i),
                    loop);
            graph.get(i).setLocalVist(false);
        }
    }    void AssistantFind(Iterator<MyNode> iterator, MyNode previous,
            List<MyNode> loop) {
        while (iterator.hasNext()) {
            MyNode temp = iterator.next();
            if (temp == previous) {
                if (loop.size() <= 2)
                    continue;
                for (int i = 0; i < loop.size(); i++)
                    System.out.print(loop.get(i).getValue() + "->");
                System.out.println(temp.getValue());
            } else {
                if (temp.isLocalVist() || temp.isVisit())
                    continue;
                else
                    loop.add(temp);
                temp.setLocalVist(true);
                AssistantFind(temp.getNeighbors().iterator(), previous, loop);
            }
        }
        loop.get(loop.size() - 1).setLocalVist(false);
        loop.remove(loop.size() - 1);
    }    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.AddNode("a");
        graph.AddNode("b");
        graph.AddNode("c");
        graph.AddNode("d");
        graph.AddNode("e");
        graph.AddNode("f");
        graph.AddEdge("a", "b");
        graph.AddEdge("a", "d");
        graph.AddEdge("b", "c");
        graph.AddEdge("c", "f");
        graph.AddEdge("c", "a");
        graph.AddEdge("d", "f");
        graph.AddEdge("d", "c");
        graph.AddEdge("e", "d");
        graph.AddEdge("f", "e");
        graph.AddEdge("f", "a");
        graph.FindAllLoop();
    }
}

Answer 7

我也来凑个热闹//假设->左边和右边都只有一个字母。任意输入，每行输入四个字符，如a->b
package demo;import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;public class LoopDetect { public static void main(String[] args) throws Exception{
ArrayList<String> paths = new ArrayList<String>();
BufferedReader input = new BufferedReader(
new InputStreamReader(System.in));
String resultPath = null;
while( resultPath==null){
String aline = input.readLine();
if (aline.length()==0) break;
String p = Character.toString(aline.charAt(0));
String q = Character.toString(aline.charAt(3));
boolean sticked = false; //是否和已有路径连通
int size = paths.size();
for (int i=0; i<size; i++){
String current = paths.get(i);
if (current.contains(p)){
String frontPath = current.substring(0, current.indexOf(p)+1);
sticked=true;
//Loop detecting begin
if(frontPath.contains(q)){
resultPath = frontPath.substring(frontPath.indexOf(q)).concat(q);
break;
}
//Loop detecting end
if (frontPath.length()==current.length())
paths.set(i, current.concat(q));
//原路径增长
else {
String newPath  = frontPath.concat(q);
if (!paths.contains(newPath))
paths.add(newPath);
//路径分支
}
}
}
if(!sticked){
paths.add(p+q);
}
for (String i: paths){ //调试用代码
System.out.println( i);
}
}
if (resultPath==null) System.out.println("No loop found");
else System.out.println("Loop found: " + resultPath);
}}大家帮我测试一下，看看是不是覆盖完毕了各种情形。没有用递归。

Answer 8

不太明白你的程序在做什么，当我输入 a->b时，一回车就输出了ab.
比如说我有如下的路径
a->b
b->a
a->c
c->a
b->c
c->b
我需要找出全部的回路

Answer 9

你的这个算法，似乎不太完全，如果我用如下例子
a->b,b->a,
b->c,c->b,
a->c,c->a你的算法只能找出 a->b->c->a 和 a->c->b->a. 而还有好多其他的回路啊，比如 a->b->a, a->c->a, b->c->b等等

Answer 10

你好，我是这么输入的
输入：a->b
返回：ab
输入：b->c
返回：abc
输入：c->a
返回：abc
loop found:abca就退出程序了，不让我继续加其它路径了，有什么解决办法吗？请指教

Answer 11

凑个热闹import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;class Node {
private String id;
private Set<Node> sibling; public String getId() {
return id;
} public Set<Node> getSibling() {
return new HashSet<Node>(sibling);
} public Node(String id) {
this.id = id;
sibling = new HashSet<Node>();
} public boolean addSinbling(Node n) {
return sibling.add(n);
}
}class Path {
private List<Node> nodes;
private String delimiter; public Path(String delimiter) {
this.delimiter = delimiter;
nodes = new ArrayList<Node>();
} public boolean append(Node n) {
return nodes.add(n);
} public boolean removeLast() {
return nodes.remove(nodes.size() - 1) != null;
} public boolean hasLoop() {
for (Node n : nodes) {
if (nodes.indexOf(n) != nodes.lastIndexOf(n)) {
return true;
}
}
return false;
} public boolean isLoop() {
int size = nodes.size();
if (size < 2)
return false;
return nodes.get(0) == nodes.get(nodes.size() - 1);
} public String toString() {
StringBuilder sb = new StringBuilder();
boolean bFirst = true;
for (Node n : nodes) {
if (bFirst) {
bFirst = false;
} else {
sb.append(delimiter);
}
sb.append(n.getId());
}
return sb.toString();
}
}public class Graph {
private Set<Node> nodes;
private String delimiter; public Graph(String delimiter) {
this.delimiter = delimiter;
nodes = new HashSet<Node>();
} public Node getNode(String id) {
for (Node n : nodes) {
if (n.getId().equals(id)) {
return n;
}
}
return null;
} public boolean addEdge(String str) {
String[] arr = str.split(delimiter);
if (arr.length != 2)
return false;
String pid = arr[0];
String id = arr[1];
Node p = getNode(pid);
if (p == null) {
p = new Node(pid);
nodes.add(p);
}
Node n = getNode(id);
if (n == null) {
n = new Node(id);
nodes.add(n);
}
return p.addSinbling(n);
} public void checkLoop() {
Path p = new Path(delimiter);
for (Node n : nodes) {
checkLoop(p, n);
}
} public void checkLoop(Path p, Node n) {
p.append(n);
if (p.hasLoop()) {
if (p.isLoop())
System.out.println(p);
} else {
for (Node s : n.getSibling()) {
checkLoop(p, s);
}
}
p.removeLast();
} public static void main(String[] args) {
Graph g = new Graph("->");
g.addEdge("a->b");
g.addEdge("a->c");
g.addEdge("b->d");
g.addEdge("d->a");
g.addEdge("b->c");
g.addEdge("c->b");
g.checkLoop();
}
}

Answer 12

对不起，搞错了，
但我把你的程序稍微改一下
public static void main(String[] args) {
  Graph graph = new Graph();
  graph.AddNode("a");
  graph.AddNode("b");
  graph.AddNode("c");  graph.AddEdge("a", "b");
  graph.AddEdge("a", "c");
  graph.AddEdge("b", "c");
  graph.AddEdge("b", "a");
  graph.AddEdge("c", "a");
  graph.AddEdge("c", "b");  graph.FindAllLoop();
  }它只能找出a->b->c->a和a->c->b->a
这两个回路，但还有其它回路啊,如a->b->a, 等

Answer 13

a->b->这个还算回路啊，我把它过滤了。需要的我可以改下代码

Answer 14

你把这条语句注释掉就行：         if (loop.size() <= 2)
                                   continue;

Answer 15

谢谢你，在注释掉这两句后，出了几个其它循环，但还是不全，
比如说 b->a->b, c->a->c, c->b->c等等都没有包含，是应为
b->a->b和a->b->a是一样的就没有算进去的原因吗
麻烦你了

Answer 16

对不起，还得再麻烦一次，
在这种情况下：
  graph.AddNode("a");
  graph.AddNode("b");
  graph.AddNode("c");  graph.AddEdge("a", "b");
  graph.AddEdge("a", "c");
  graph.AddEdge("b", "c");
  graph.AddEdge("b", "a");
  graph.AddEdge("c", "a");
  graph.AddEdge("c", "b");还是有一种情况漏掉了，
比如a->b->c->b->a,a->c->b->c->a, b->c->a->c->b,等能麻烦你修改一下吗
非常感谢

Answer 17

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;class Node {
private String id; public String getId() {
return id;
} public Node(String id) {
this.id = id;
} public boolean equals(Object o) {
if (!(o.getClass() == Node.class)) {
return false;
}
Node n = (Node) o;
return id.equals(n.getId());
} public String toString() {
return id;
}
}class Edge {
private Node start;
private Node end;

private String delimiter; public Edge(Node start, Node end, String delimiter) {
super();
this.start = start;
this.end = end;
this.delimiter = delimiter;
} public Node getStart() {
return start;
} public Node getEnd() {
return end;
} public boolean equals(Object o) {
if (!(o.getClass() == Edge.class)) {
return false;
}
Edge e = (Edge) o;
return start.equals(e.start) && end.equals(e.end);
}

public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(start).append(delimiter).append(end);
return sb.toString();
}
}class Path {
private LinkedList<Edge> edges;
private String delimiter; public Path(String delimiter) {
this.delimiter = delimiter;
edges = new LinkedList<Edge>();
} public boolean add(Edge e) {
if (edges.size() == 0 || edges.getLast().getEnd() == e.getStart()) {
edges.add(e);
return true;
}
return false;
} public boolean removeLast() {
return edges.removeLast() != null;
} public boolean isSimple() {
for (Edge e : edges) {
if (edges.indexOf(e) != edges.lastIndexOf(e)) {
return false;
}
}
return true;
} public boolean isLoop() {
return edges.getFirst().getStart().equals(edges.getLast().getEnd());
} public String toString() {
StringBuilder sb = new StringBuilder();
boolean bFirst = true;
for (Edge edge : edges) {
if (bFirst) {
sb.append(edge.getStart());
bFirst = false;
}
sb.append(delimiter).append(edge.getEnd()); }
return sb.toString();
}
}public class Graph {
private Set<Node> nodes;
private Set<Edge> edges;
private String delimiter; public Graph(String delimiter) {
this.delimiter = delimiter;
nodes = new HashSet<Node>();
edges = new HashSet<Edge>();
} public Node getNode(String id) {
for (Node n : nodes) {
if (n.getId().equals(id)) {
return n;
}
}
return null;
} public Edge getEdge(String s, String e) {
Node start = getNode(s);
if (start == null) {
return null;
}
Node end = getNode(e);
if (end == null) {
return null;
}
for (Edge edge : edges) {
if (edge.getStart().equals(start) && edge.getEnd().equals(end)) {
return edge;
}
}
return null;
} public boolean addNode(String id) {
Node node = getNode(id);
if (node != null) {
return false;
}
return nodes.add(new Node(id));
} public boolean addEdge(String s, String e) {
Edge edge = getEdge(s, e);
if (edge != null) {
return false;
}
Node start = getNode(s);
if (start == null) {
addNode(s);
start = getNode(s);
}
Node end = getNode(e);
if (end == null) {
addNode(e);
end = getNode(e);
}
return edges.add(new Edge(start, end, delimiter));
} public boolean removeNode(String id) {
Node node = getNode(id);
if (node == null) {
return false;
}
Set<Edge> temp = new HashSet<Edge>();
for (Edge edge : edges) {
if (edge.getStart().equals(node) || edge.getEnd().equals(node)) {
temp.add(edge);
}
}
edges.removeAll(temp);
return nodes.remove(id);
} public boolean removeEdge(String s, String e) {
Edge edge = getEdge(s, e);
if (edge == null) {
return false;
}
return edges.remove(edge);
} public String getLoops() {
StringBuilder sb = new StringBuilder("Loops: ");
Path p = new Path(delimiter);
for (Edge e : edges) {
getLoops(p, e, sb);
}
return sb.toString();
} private void getLoops(Path path, Edge edge, StringBuilder sb) {
if (!path.add(edge)) {
return;
}
if (path.isSimple()) {
if (path.isLoop()) {
sb.append('\n').append(path);
} else {
for (Edge e : edges) {
getLoops(path, e, sb);
}
}
}
path.removeLast();
} public String toString() {
StringBuilder sbNodes = new StringBuilder("Nodes: ");
StringBuilder sbEdges = new StringBuilder("Edges: ");
boolean bNodeFirst = true;
boolean bEdgeFirst = true;
for (Node node : nodes) {
if (bNodeFirst) {
bNodeFirst = false;
} else {
sbNodes.append(", ");
}
sbNodes.append(node.getId());
}
for (Edge edge : edges) {
if (bEdgeFirst) {
bEdgeFirst = false;
} else {
sbEdges.append(", ");
}
sbEdges.append(edge);
}
return sbNodes.append('\n').append(sbEdges).toString();
} public static void main(String[] args) {
Graph g = new Graph("->");
g.addEdge("a", "b");
g.addEdge("a", "c");
g.addEdge("b", "c");
g.addEdge("b", "a");
g.addEdge("c", "a");
g.addEdge("c", "b");
g.addEdge("d", "a");
g.addEdge("d", "b");
g.addEdge("d", "c");
g.addEdge("a", "d");
g.addEdge("b", "d");
g.addEdge("c", "d");
//g.removeEdge("a", "d");
g.removeNode("d");
System.out.println(g);
System.out.println(g.getLoops());
}
}再凑一次热闹

Answer 18

改进了一下public class MyNode {
    private boolean visit;    private String value;    private List<MyNode> neighbors;    MyNode(String value) {
        this.value = value;
        neighbors = new LinkedList<MyNode>();
    }    public String getValue() {
        return this.value;
    }    public List<MyNode> getNeighbors() {
        return neighbors;
    }    public boolean isVisit() {
        return visit;
    }    public void setVisit(boolean visit) {
        this.visit = visit;
    }
public class Graph {    private List<MyNode> graph;    private Map<String, MyNode> hash;    Graph() {
        graph = new ArrayList<MyNode>();
        hash = new HashMap<String, MyNode>();
    }    public void AddNode(String value) {
        MyNode node = new MyNode(value);
        graph.add(node);
        hash.put(value, node);
    }    public void AddEdge(String from, String to) {
        MyNode add = null;
        if (hash.get(to) != null)
            add = hash.get(to);
        else {
            add = new MyNode(to);
            graph.add(add);
            hash.put(to, add);
        }
        hash.get(from).getNeighbors().add(add);
    }    void FindAllLoop() {
        for (int i = 0; i < graph.size(); ++i) {
            List<MyNode> loop = new ArrayList<MyNode>(); //每个回路中所包含的结点
            Map<MyNode, MyNode> edges = new HashMap<MyNode, MyNode>();//已经走过的边
            loop.add(graph.get(i));
            graph.get(i).setVisit(true);
            AssistantFind(graph.get(i).getNeighbors().iterator(), graph.get(i),
                    loop, graph.get(i), edges);
        }
    }    void AssistantFind(Iterator<MyNode> iterator, MyNode start,
            List<MyNode> loop, MyNode previous, Map<MyNode, MyNode> edges) {
        while (iterator.hasNext()) {
            MyNode temp = iterator.next();
            if (temp == start) {
                for (int i = 0; i < loop.size(); i++)
                    System.out.print(loop.get(i).getValue() + "->");
                System.out.println(temp.getValue());
            } else {
                if (temp.isVisit() || temp == edges.get(previous))
                    continue;
                else {
                    loop.add(temp);
                    edges.put(previous, temp);
                }
                AssistantFind(temp.getNeighbors().iterator(), start, loop,
                        temp, edges);
            }
        }
        edges.remove(previous);
        loop.remove(loop.size() - 1);
    }    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.AddNode("a");
        graph.AddNode("b");
        graph.AddNode("c");
        graph.AddNode("d");
        graph.AddNode("e");
        graph.AddNode("f");
        graph.AddEdge("a", "b");
        graph.AddEdge("a", "c");
        graph.AddEdge("b", "c");
        graph.AddEdge("b", "a");
        graph.AddEdge("c", "a");
        graph.AddEdge("c", "b");
        graph.FindAllLoop();
    }
}
}

Answer 19

第一眼看上去有些像人工智能里的内容，机器推理什么的。以前上过课，现在都还了，只有些印象了。还有一个lisp语言，楼主也可以看看。