注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

有向图的实际实例。1.寻找 i--j 之间是否存在路径 2.是否存在长为len'的路径  

2014-12-06 23:27:12|  分类: 数据结构---严老 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1。我们首先谈谈第一个吧!利用深度优先收索的方法实现的


@1.struct.h 定义有向图的存贮结构的

typedef struct Arcnodde
{
int adj;
Arcnode* nextarc;
}Arcnode;
typedef struct Vnode
{
int data;
Arcnode* fistarc;
}Vnode,Adjlist[200];
typedef struct ALGraph
{
Adjlist vertices;
int vexnum;
int arcnum;
}ALGraph

@function.h 实现的函数

1.基本的初始化

int Search(ALGraph &G,int i,int j,stack<int> &s)
{
for(int v=0;v<G.vexnum;v++)
{
Visited[i]=false;
if(G.vertices[v].data==i)
i=v;
if(G.vertices[v].data=j)
j=v;
}
bool found=false;//标志变量的初始化,以及寻找我么的结点在数组中的位置。
DFSearch(G,i,j,s,found);
if(found)
return true;
return false;

}

2.基于深度优先收索的实现

void DFSearch(ALGraph G,int i,int j,stack<int> &s,bool &found)
{
Visited[i]=true;
s.push(i);
Arcnode *p;
//foud ==true 就跳出踢归了。
for(p=G.vertices[i].fistarc;p&&!found;p=p->nextarc)
{
if(p->adj==j)
{
found=true;//找到了这个结点的时候我们就要收手了涩;
}
else if(!Visited[p->adj])//没有访问过的结点才可以继续的进行下去色!
{
DFSearch(G,p->adj,j,s,found);
if(!found)
{
s.pop();
}
/*从那个位置,不断的深度收索
到达我们的无路可走的状态的时候,
我们只好把他pop掉,且,返回上一个状态。
但是此时的Vistited{],我们的并没有变为false?
因为,这里到达不了j的位置,以后的也是到达不了的!
*/
}
}

}




2.谈谈我们的第二个吧,其实和我们的第一个差不多的嘎。都是内饰的改变的情况。
//寻找 i到我们的j 之间距离为len 的结点。

1.基本的初始化


int SearchLenofDefine(ALGraph &G,int i,int j,stack<int> &s,int len)
{
for(int v=0;v<G.vexnum;v++)
{
Visited[i]=false;
if(G.vertices[v].data==i)
i=v;
if(G.vertices[v].data=j)
j=v;
}
bool found=false;//标志变量的初始化,以及寻找我么的结点在数组中的位置。
int count=0;
SearchLenofDefine(G,i,j,s,len,count,found);
if(found)
return true;
return false;

}

2.真的函数的实现形式

int SearchLenofDefine(ALGraph &G,int i,int j,stack<int> s,int len ,int count,bool found)
{
Visited[i]=true;
s.push(i);
Arcnode *p;
//找遍与我们的p相连的所有的边边色,如果都不可以就算了
for(p=G.vertices[i].fistarc;p&&!found;p=p->nextarc)
{
if(p->adj==j)
{
if(++count==len)
{
found=true;
s.push(j);
}
}
else if(count<len-1&&!Visited[p->adj])
{
SearchLenofDefine(G,p->adj,j,s,len,count++,found);
if(!found)
{
int k=s.top();
s.pop();
Visited[k]=false;
//为什么我们的这里要设置为false呢?
//如果我们找到了j的时候,但是他有小于len的路径
//那么j就不可以访问了?
//所以啊,我们就的,吧他还回来啊。
count--;
}
}
}
}

感悟:
深度优先的收索在我们的应用中,经常的用到,我们必须的拥有这样的思想,去理解,去知道该怎么去安排我们的函数形式,以及我们该怎么去实现。以及剪枝啊。
如何利用才是我们的收索!
  评论这张
 
阅读(19)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017