回 帖 发 新 帖 刷新版面

主题:求图的深度,广度优先搜索程序

首先声明,我不是来这求作业的。以下是我自己利用上班时间写的,写得头都乱了,问题太多,是故不敢请大侠帮我看了。只是想请哪位大侠提供一个可运行的参考参考,我好改进,我的邮箱:huangyingw@gmail.com
----------------------------------------------------------------------------
// 图.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;
struct adjex
{
    int vertex;
    adjex *next;
};
struct vertex  
{
    adjex *firstedge;   
};
adjex *gadjex=NULL;
vertex gvertex[4];
int pass[100];
int top=0;
bool visit[4];
bool check[4];
//建图
void createGraph(int *data,int dim)
{
    
    for(int i=0;i<dim;i++)
    {
        gvertex[i].firstedge=NULL;
        adjex *gadjex=NULL;
        for(int j=0;j<dim;j++)
        {
            if(gvertex[i].firstedge==NULL&&data[i*dim+j]!=0)
            {
                gadjex=new adjex;
                gadjex->vertex=j;
                gvertex[i].firstedge=gadjex;
            }
            else if(data[i*dim+j]!=0)
            {
                gadjex->next=new adjex;
                gadjex->next->vertex=j;
                gadjex->next->next=NULL;
                gadjex=gadjex->next;
            }
        }
    }
}
void pringGraph()
{
    adjex *gadjex=NULL;
    for(int i=0;i<4;i++)
    {
        gadjex=gvertex[i].firstedge;
        while(gadjex!=NULL)
        {
            cout<<gadjex->vertex;
            gadjex=gadjex->next;
        }
        cout<<endl;
    }
}
void push(int data)
{
    pass[top++]=data;
}
int pop()
{
    if(top>=0)
        return pass[--top];
    else
        return -1;
}
void trerverse(int i)
{
    while(!check[i])
    {
        check[i]=true;
        visit[i]=true;
        push(i);
        gadjex=gvertex[i].firstedge;
        i=gadjex->vertex;
        while((visit[i]||check[i])&&gadjex->next!=NULL)
        {
            gadjex=gadjex->next;
            i=gadjex->vertex;
        }
    }
    if(check[i])
    {
        gadjex=gvertex[i].firstedge;
        i=gadjex->vertex;
        while((visit[i]||check[i])&&gadjex->next!=NULL)
        {
            gadjex=gadjex->next;
            i=gadjex->vertex;
        }
        gadjex=gadjex->next;
        i=gadjex->vertex;
        visit[i]=true;
        check[i]=true;
        push(i);
    }
}
void dfSearch()
{
    int i;
    for(i=0;i<4;i++)
    {
        visit[i]=false;
        check[i]=false;
    }
    i=0;
    //为每个结点增加一个标志位,记录该结点
    //是否访问过
    visit[i]=true;
    check[i]=true;
    push(i);//结点i入栈
    gadjex=gvertex[i].firstedge;
    i=gadjex->vertex;
    while(top>=0&&top<4)
    {
        trerverse(i);
        for(int k=0;k<top;k++)
            cout<<pass[k]<<",";
        cout<<endl;
        i=pop();
        visit[i]=false;
        //check[i]=false;
        gadjex=gvertex[i].firstedge;
        i=gadjex->vertex;
        while((visit[i]||check[i])&&gadjex->next!=NULL)
        {
            gadjex=gadjex->next;
            i=gadjex->vertex;
        }
        if(gadjex->next==NULL)
        {
            i=pop();
            visit[i]=false;
        }
        else
            continue;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int vertex[4][4]={{0,1,1,1},{1,0,1,1},{1,1,0,0},{1,1,0,0}};
    
    createGraph(*vertex,4);
    pringGraph();
    dfSearch();
    return 0;
}

回复列表 (共4个回复)

沙发

呵呵,我也刚写了这个..

板凳

呵,你写出了没,我还在写之中,代码上简洁了些,在搜索失败和退栈返回上处理有误。现在在上班,回去再把改进过的但还有很大问题的贴上来。
想请教一下,你的搜索结束条件是怎么设置的,贴一点相关代码交流一下吧。

3 楼

没有新的状态进队列的时候,然后队列里所有结点都经历之后,搜索就结束了。

4 楼

我刚才就深度优先和广度优先算法在网上搜了一下,发现它们不是我想要的。因为它们从当前结点寻找下一个未访问结点时,目标结点与当前结点之间并不一定是连通的。而这不是我想要的。我想写的是如下一个加强的遍历结果:1,所有结点都访问过;2,最后的结果出来,相邻结点之间是连通的。换句话说,假设按着最后的结果浏览图,应该1,不走回路,2,可以走通,3,走遍所有结点。
尽量把我的需求表述得清楚一些,只是希望大侠告诉我,有没有类似的算法,这个算法叫什么名字,然后我可以在网上搜搜,我现在自己写的的程序,感觉在结点与边的存储方式上不适合解决我的需求。
我离开学校半年了,没有数据结构的书。所以,大家就不要让我自己去翻书了吧。如果哪位有相关的电子书或者是网上资源,麻烦传给我一下,谢谢:huangyingw@gmail.com。
我在网上搜到的很多是万方或者是维普的,需要注册才能浏览。大家知道哪有免费的镜像入口吗?是不是还得从教育网里找入口?
呵,如果哪位大侠有空,麻烦把你要用到的数据类型的定义帖上来让小弟参考一下。

我来回复

您尚未登录,请登录后再回复。点此登录或注册