图的邻接链表实现下的搜索两点之间所有路径的算法

发布于:2021-12-02 08:34:33

算法用C++实现


为什么要写这个算法呢?苦于在网上查找只有邻接矩阵的实现,所以自己弄了一个邻接链表的实现,可以提高速率


实现方式是使用三个栈 其中一个栈用来遍历所有顶点,第二个栈用于记录第一个栈的父母结点,第三个栈用来记录正在遍历的其中一条路径


需要三个路径的原因是:每次将一个结点加入进第三个栈时,需要确定第三个栈顶元素是加入元素的父母结点


还需要一个数组用来记录结点是否被访问过





template
bool Picture::findway()
{
cout<<"Input:";
T first,second;
cin>>first>>second;
cout<<"Output:"< int n0,n1;
n0=getVerticePos(first);
n1=getVerticePos(second);
if(n0==-1||n1==-1) //不存在的结点
return false;
bool *judge=new bool[numVertices]; //判断结点是否走过
for(int i=0;i judge[i]=false;
Edge *loc;
stack s; //遍历各结点
stack parent; //记录前一结点
stack q; //记录其中一条
s.push(n0);
parent.push(-1);
int i,j,length;
int path[50];
while(!s.empty())
{
i=s.top();
s.pop();
j=parent.top();
parent.pop();
judge[i]=true;
if(q.empty())
q.push(i);
else
{
while(q.top()!=j)
{
judge[q.top()]=false;
q.pop();
}
q.push(i);
}
if(i==n1) //找到终点
{
length=0;
while(!q.empty())
{
path[length++]=q.top();
q.pop();
}
for(int i=length;i>0;i--)
{
cout< q.push(path[i-1]);
}
cout< continue; //不再将邻接结点加入栈s
}

loc=NodeTable[i].adj;
while(loc!=NULL)
{
if(judge[loc->dest]==false) //结点此路径没有被访问过
{
s.push(loc->dest);
parent.push(i);
}
loc=loc->link;
}
}
return true;
}

template
int Picture::getVerticePos(const T vertex)
{
for(int i=0;i if(NodeTable[i].data==vertex)
return i; //找到返回下标
cout< return -1; //未找到返回-1
}



图的构建就不写上来了


测试数据如图







相关推荐

最新更新

猜你喜欢