[数据结构与算法]分别基于dfs和bfs判断是否存在路径

分别基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是否存在有顶点Vi到顶点Vj的路径。

dfs的：

void dfs(ALGraph A, int start, int dest, int k, int vis[],int flag) 
{
    vis[k] = true;
    if(k == dest)
    {
        flag = 1;
        return;
    }
    int x = FirstNeighbour(A, k);
    for(int i = FirstNeighbour(A, k); i >= 0; i = NextNeighbour(A,k,i))
    {
        if(!vis[i] && !flag)
        {
            dfs(A, start, dest, i, vis, flag);
            
        }
    }
}

bfs的：

void bfs(ALGraph A, int start, int dest, int vis[], int k)
{
    int i;
    for(i = 0; i < A.vexnum; i++)
    {
        vis[i] = false;
    }
    InitQueue(Q);
    EnQueue(Q, k);
    while(!IsEmpty(Q))
    {
        int x;
        DeQueue(Q, &x);
        vis[x] = 1;
        if(x == dest) return 1;      //容易漏掉
        for(i = FirstNeighbour(A,x);i>=0;i=NextNeighbour(A,x,i))
        {
            if(i == dest) return 1;
            if(!vis[i])
            {
                EnQueue(Q, i);
                vis[i] = 1;
            }
        }
    }
    return 0;
}