有向图求环
在一个有1万顶点的有向图中，如何求环？如果使用邻接表的话，内存不够，不能处理一个1万的二维数组，该如何办？
谢谢了，急。。。。。。。。 --------------------编程问答-------------------- 首先你这个有向图本身使用什么数据结构存储的？可以不用邻接表，用实时递归计算也可以，就是慢，时间复杂度要到O(n*n)。算法不是牺牲时间复杂度就是牺牲空间复杂度，没有能够两全齐美的。
--------------------编程问答-------------------- 例如，你可以从一个点开始，然后进行深度优先搜索，直到你的深度优先搜索找到这个点自身位置，就是一个环。等所有的点都搜索完了，你就可以找到所有的环了。 --------------------编程问答-------------------- 本身这些数据存储在text文本里面，想使用arraylist来存储，但是很复杂去找出index --------------------编程问答-------------------- 如果使用邻接表的话，内存不够，不能处理一个1万的二维数组，该如何办？
为什么不换种存储结构？ --------------------编程问答-------------------- 小弟经验不足，别的存储结构还不是很明白，希望大虾能够给一个指示，谢谢 --------------------编程问答-------------------- 如果使用邻接表的话，内存不够，不能处理一个1万的二维数组，该如何办？
开始只看到了1万个二维数组，这种结构使用的是邻接矩阵，不是邻接表。
如果使用邻接表来存储，1万个点，没有任何问题，因为使用的是堆内存。
找本数据结构的书，再看看开始部分讲图的存储结构，就知道怎么做了。 --------------------编程问答-------------------- 换种数据结构 树形结构或者其他， --------------------编程问答-------------------- 能不能给一个例子？看看如何构建能够存储大数据的数据结构？ --------------------编程问答-------------------- 数据结构的知识了。
不用换数据结构，这就是一个图，换成树还要去生成树，多麻烦，也不需要。
图的存储主要是邻接矩阵和邻接表。
1万个结点的，如果用邻接矩阵会比较浪费和耗费空间，所有用邻接表没有问题。
楼主可以找数据结构的书来看，书上都有写。 --------------------编程问答-------------------- 写了一个程序求环，但是发现还是有错误，第一个是不断地循环，第二个还是memory不够，希望高手帮忙看看。
[code=Java]
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.lang.*;
public class test {
static Hashtable visited = new Hashtable();
static Hashtable nodestart = new Hashtable();
static Hashtable nodefinish = new Hashtable();
static Hashtable nodeexist = new Hashtable();
final private static int N = 10000;
static ArrayList<String> trace=new ArrayList<String>();
static boolean hasCycle=false;
public static void main(String[] args) throws IOException {
int p = 0;
for (int i = 0;i <= N;i ++){
visited.put("" + i, "0");
}
BufferedReader in = new BufferedReader(
new InputStreamReader(new FileInputStream("3.txt"), "UTF-8"));
String str = in.readLine();
StringBuffer buffer = new StringBuffer();
do{
buffer.append(str);
buffer.append(" ");
String[] s = buffer.toString().split(" ");
buffer.delete(0, buffer.length());
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
nodestart.put("" + p, "" + a);
nodefinish.put("" + p, "" + b);
nodeexist.put("" + p, "1");
str = in.readLine();
p++;
}while(str!=null);
in.close();
findCycle("0");
if(!hasCycle)
System.out.println("No Cycle.");
}
static void findCycle(String v)
{
if((String)visited.get(""+v) == "1")
{
int j;
if((j=trace.indexOf(v))!=-1)
{
hasCycle=true;
System.out.print("Cycle:");
while(j<trace.size())
{
System.out.print(trace.get(j)+" ");
j++;
}
System.out.print("\n");
return;
}
return;
}
visited.put("" + v, "1");
trace.add(v);
String q;
for(int k = 0; k < 5; k++)
{
if((String) nodeexist.get("" + k) == "1"){
q = (String) nodefinish.get("" + k);
findCycle(q);
}
}
trace.remove(trace.size()-1);
}
}
[code]
text文本用来表示有向图，（部分数据，不是10000行）
第一个表示出发点，第二个是结束点，表明之间有联系，并且第一个指向第二个。
1 2
2 3
3 4
4 1
1 3
结果
Cycle:2
Cycle:2 3
Cycle:3
Cycle:2 3 4
Cycle:3 4
Cycle:4
Cycle:2 3 4 1
Cycle:3 4 1
Cycle:4 1
Cycle:1
Cycle:3 4 1
Cycle:3 4
Cycle:3
不知道什么问题。。。。。
急啊啊啊啊啊啊。。。。。 --------------------编程问答--------------------
这里输出的一段cycle是什么意思？
我理解求环就是先遍历整个图（不管什么方式），访问过的节点记录在一个集合中，然后拿后访问到的节点去这个集合中比对有没有重复的，有重复就是有环。
--------------------编程问答-------------------- 没有人能够回答吗？
补充：Java , Java相关
