data-structures - 图中任意两个节点之间的距离(基于它们之间的边)
问题描述
C++ 中的以下代码是查找图中任意两个节点之间的距离,但是我试图找到但找不到的地方存在一些逻辑错误。一切似乎都很完美,但我可以说 for 循环内部的break
内部if
条件有问题,它位于 inside while(s.!empty())
。
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int find_distance(int link[100][100],int start,int dest,int n,int e)
{
start=start-1;
dest=dest-1;
if(start==dest)return 0;
int visited[100];
int distance;
for(int i=0;i<n;i++)
{
visited[i]=0;
}
stack<int>s;
int k;s.push(start);
visited[start]=1;
bool found=false;
int count =0;
while(!s.empty())
{
k=s.top();
int i;
int check_point=1;
for(i=0;i<n;i++)
{
if(link[k][i]==1 && visited[i]!=1)
{
s.push(i);
count ++;
check_point=0;
if(i==dest)
{
cout<<"found";
found=true;
}
break;
}
}
if(check_point==1)
{
s.pop();
count--;
}
if(found)break;
}
return count;
}
int main()
{
int n,e,a,b;
int link[100][100];
cout<<"enter the number of vertices and edges";
// cin>>n>>e;
n=5;e=4;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j)
link[i][j]=0;
else
link[i][j]=INT_MAX;
cout<<link[i][j]<<" ";
}
cout<<endl;
}
int input[4][2]={{1,2},{1,3},{2,4},{2,5}};
for(int i=0;i<e;i++)
{
a=input[i][0];
b=input[i][1];
link[a-1][b-1]=1;
link[b-1][a-1]=1;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<link[i][j]<<" ";
}
cout<<endl;
}
while(true) {
cout<<endl<<"enter the starting point .. ";
int start;
cin>>start;
int dest;
cout<<endl<<"enter the destination point .. ";
cin>>dest;
int distance = find_distance(link,start,dest,n,e);
cout<<endl<<"distance is "<<distance;
}
return 0;
}
解决方案
推荐阅读
- javascript - 使用 Position Fixed 子项滚动 Div
- javascript - onClick 按钮在输入字段中添加焦点,但该输入是不可见的
- sql-server - 尝试创建 PIVOT 表时,我在 SQL 中收到无效标识符错误
- java - JNA - 如何使用 FOREIGN_THREAD_START_ROUTINE 类?
- python - 如何在图片的文件名中使用变量并循环使用 pygame 打开多张图片而不会弄乱代码
- razor - 如何在锚标签中正确使用剑道 UI 模板?
- mysql - 如何为具有相同值的最大连续 ID 编写 sql 查询
- c++ - 无法在 Visual Studio 2010 中构建 Allegro C++ 程序
- powershell - 使用 powershell 托管 WCF 服务
- javascript - websocket.js 导致 React 应用程序意外刷新