c - 图是否连通!福特富尔克森的C语言

Question

//我创建它作为福特 fulkersion 算法的一部分

#include<stdio.h>
#include<conio.h>

void main()
{
    int v,i,e,ch[20],sv[20],count=0,s,j;
    clrscr();
    printf("Enter No of vertices :");
    scanf("%d",&v);
    for(i=1;i<=v;i++)
    {
        printf("Enter vertices %d",i);
        scanf("%d",&sv[i]);
    }
    printf("Enter starting node : ");
    scanf("%d",&s);

//下面这个循环中出现问题(逻辑不工作)如果有人有解决方案请帮忙!

    for(i=s;i<=v-1;i++)
    {
        for(j=i+1;j<=v;j++)
        {
            printf("conn betn %d and %d",i,j);
            scanf("%d",&ch[i]);
            if(ch[i]!=1)
            {
                break;
            }
            else if(ch[i]==1)
            {
                count++;
            }
        }
    }

//-------------------------------------------------------- -------------

if(count>=v)
{
    printf("Graph is connected");
}
else
{
    printf("Graph is disconnected");
}
getch();

}

Answer 1

你的算法是错误的。您假设如果至少有 v 条边，则您的图是连通的。但是如果你有一个像这样的图，有 6 个节点和 6 个边，它仍然没有连接: