dfs算法java代码 dfs代码实现
分别用DFS和BFS算法给电脑设置AI(JAVA)
有必胜策略的吧。。状态空间的上限是3^9也就是不到20000实际上没有这么多。所以直接采用BFS标记会比较好。算法的话就是填充表,把表(九个格子)填为必胜、必败,己胜,开始的时候全部标为必败,再从胜状态开始向回BFS(或者DFS也可以),己胜状态向回标的一定是败状态,必胜状态的上一状态为必败态,必败态的上一状态可能是必败或者必胜(这就是因为这家伙走错棋了所以要输!)
创新互联公司是一家专业提供虹口企业网站建设,专注与做网站、网站制作、HTML5、小程序制作等业务。10年已为虹口众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。
我的习惯。不写代码。没有意思。
判断有向图是否连通+dfs+java
方法1:
如果存在回路,则必存在一个子图,是一个环路。环路中所有顶点的度=2。
n算法:
第一步:删除所有度=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。
第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复步骤一。
如果最后还有未删除顶点,则存在环,否则没有环。
n算法分析:
由于有m条边,n个顶点。
i)如果m=n,则根据图论知识可直接判断存在环路。(证明:如果没有环路,则该图必然是k棵树 k=1。根据树的性质,边的数目m = n-k。k=1,所以:mn)
ii)如果mn 则按照上面的算法每删除一个度为0的顶点操作一次(最多n次),或每删除一个度为1的顶点(同时删一条边)操作一次(最多m次)。这两种操作的总数不会超过m+n。由于mn,所以算法复杂度为O(n)。
关于DFS的问题
java.lang.ArrayIndexOutOfBoundsException: -1
int[][] next={{0,1},{1,0},{0,-1},{-1,0}};
int tx = 0,ty = 0;
for(int i=0;i4;i++){
tx=x+next[i][0];
ty=y+next[i][1];
if(tx1||txm||ty1||tyn){
continue;
}
}if(a[tx][ty]==0book[tx][ty]==0){ //可能会出现数组越界
java实现二进制穷举
闲着没事,给你写了一个一个DFS算法,可以枚举(a1, a2… ak),剩下的太简单,你自己写着玩吧。。。
import java.util.ArrayList;
public class DFS {
public static void main(String[] args) {
DFS dfs=new DFS();
dfs.dfs(1);
}
int sum=0;
int index=5;
ArrayListIntegerlist=new ArrayListInteger();
public void dfs(int i)
{
if(iindex)
{
sum++;
System.out.println("this is the "+sum);
for(Integer integer:this.list)
{
System.out.print(integer+" ");
}
System.out.println();
return;
}
for(int j=0;j=1;j++)
{
list.add(j);
this.dfs(i+1);
list.remove(list.size()-1);
}
}
}
求一个java的随机算法,高手来
好好的看一下就知道为什么list的长度与count 相同时,总是出现死循环 。
你在int[] a=new int[count]; 这一步操作时,数组a中的数据全部默认为0,而int rs=ran.nextInt(list.size()); 返回的值是0到list.size()-1的数。当list的长度与count 相同时,在产生最后一个随机数时,只能产生0,可是0在数组a中又存在了,所以就死循环了。
编程时,多注意边界问题。
匈牙利算法 java
#includestdio.h
#includestring.h
bool g[201][201];
int n,m,ans;
bool b[201];
int link[201];
bool init()
{
int _x,_y;
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
ans=0;
if(scanf("%d%d",n,m)==EOF)return false;
for(int i=1;i=n;i++)
{
scanf("%d",_x);
for(int j=0;j_x;j++)
{
scanf("%d",_y);
g[ i ][_y]=true;
}
}
return true;
}
bool find(int a)
{
for(int i=1;i=m;i++)
{
if(g[a][ i ]==1!b[ i ])
{
b[ i ]=true;
if(link[ i ]==0||find(link[ i ]))
{
link[ i ]=a;
return true;
}
}
}
return false;
}
int main()
{
while(init())
{
for(int i=1;i=n;i++)
{
memset(b,0,sizeof(b));
if(find(i))ans++;
}
printf("%d\n",ans);
}
}
Pascal:
Program matching;
Const
max = 1000;
Var
map : array [1..max, 1..max] of boolean; {邻接矩阵}
match: array [1..max] of integer; {记录当前连接方式}
chk : array [1..max] of boolean; {记录是否遍历过,防止死循环}
m, n, i, t1, t2, ans,k: integer;
Function dfs(p: integer): boolean;
var
i, t: integer;
begin
for i:=1 to k do
if map[p, i] and not chk[ i ] then
begin
chk[ i ] := true;
if (match[ i ] = 0) or dfs(match[ i ]) then {没有被连过 或 寻找到增广路}
begin
match[ i ] := p;
exit(true);
end;{if}
end;{for}
exit(false);
end;{function}
begin{main}
readln(n, m); {N 为二分图左侧点数 M为可连接的边总数}
fillchar(map, sizeof(map), 0);
k:=0;
for i:=1 to m do{initalize}
begin
readln(t1, t2);
map[t1, t2] := true;
if kt2 then k:=t2;
end;{for}
fillchar(match, sizeof(match), 0);
ans := 0;
for i:=1 to n do
begin
fillchar(chk, sizeof(chk), 0);
if dfs(i) then inc(ans);
end;
writeln(ans);
for i:=1 to 1000 do
if match[ i ] 0 then
writeln(match[ i ], '--', i);
end.
网站标题:dfs算法java代码 dfs代码实现
链接分享:http://pwwzsj.com/article/doohiip.html