| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 409 人关注过本帖
标题:关于图的问题
只看楼主 加入收藏
Edwardwang03
Rank: 2
来 自:西安
等 级:论坛游民
帖 子:45
专家分:32
注 册:2012-9-18
结帖率:50%
收藏
 问题点数:0 回复次数:2 
关于图的问题
这几天一直在写图中任意两点的深度优先的递归算法但是一直有问题,还请大神赐教,我采用的是邻接矩阵存储的
首先贴上我自己写的反之被误认为不假思索求答案
程序代码:
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数组是记录每个的邻接点是否访问
2012-12-19 14:06
Edwardwang03
Rank: 2
来 自:西安
等 级:论坛游民
帖 子:45
专家分:32
注 册:2012-9-18
收藏
得分:0 
不会吧居然没人说话
2012-12-19 20:25
hit小龙
Rank: 6Rank: 6
等 级:侠之大者
帖 子:173
专家分:462
注 册:2012-12-6
收藏
得分:0 
……我也想知道
2012-12-20 18:55
快速回复:关于图的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022134 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved