注册 登录
编程论坛 数据结构与算法

关于图的问题

Edwardwang03 发布于 2012-12-19 14:06, 409 次点击
这几天一直在写图中任意两点的深度优先的递归算法但是一直有问题,还请大神赐教,我采用的是邻接矩阵存储的
首先贴上我自己写的反之被误认为不假思索求答案
程序代码:
int nextadj(AdjMatrix G, int u, int v,int *pre)
{
    int i;
    for (i = v; i < G.vexnum; i++)
        if(G.arcs[u][i].adj != 0 && pre[i] == -1)
            return i;
    return -2;
}

int firstadj(AdjMatrix G, int u, int *pre)
{
    int i;
    for (i = 0; i < G.vexnum; i++)
        if(G.arcs[u][i].adj != 0 && pre[i] == -1)
            return i;
    return -2;
}

void DFS_path(AdjMatrix G, int u, int v, int * pre)
{
    int j;
    for(j = firstadj(G, u, pre); j >= 0; j = nextadj(G, u, j, pre))
        if(pre[j] == -1 )
        {
            if(j == v)   
            {
                print_path(v, pre);
                pre[v] = -1;
                //return ;
            }
            else {DFS_path(G, j, v, pre);}
        }
}

void all_path(AdjMatrix G, int u, int v)
{
    //寻找两点之间所有路径
    int *pre;
    int i;

    pre = (int *)malloc(sizeof(int));
    for (i = 0; i < G.vexnum; i++)
        pre[i] = -1;
    pre[u] = u;
    DFS_path(G, u, v, pre);
    free(pre);
}
void print_path(int v, int *pre)
{
    int i, j;

    for(j = 0; j < 11; j++)
    printf("  %d  ",pre[j]);
    getch();
    printf("\n");
    for(i = v; pre[i] != i; i = pre[i])
        printf("%d<--",i);
    printf("%d\n", pre[i]);
    printf("\n路线相反\n");
}

我的递归有问题还请指教,或者按照void DFS_path(AdjMatrix G, int u, int v, int * pre)写一个,其中u,v分别代表起点终点的编号,pre数组是记录每个的邻接点是否访问
2 回复
#2
Edwardwang032012-12-19 20:25
不会吧居然没人说话
#3
hit小龙2012-12-20 18:55
……我也想知道
1