IT小萌新zz 2019-06-11 22:17 采纳率: 0%
浏览 1725

求一个代码c语言实现图的深度遍历(递归)、非递归算法以及实现图的广度遍历(队列)

求一个代码c语言实现图的深度遍历(递归)、非递归算法以及实现图的广度遍历(队列)

  • 写回答

1条回答 默认 最新

  • 浅草夏洛洛 2019-06-12 20:54
    关注

    邻接表实现的图,都是非递归实现的遍历。水平有限,可能存在一定问题

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX 30
    typedef struct Gnode *Lgraph;   //输入的n个结点必须
    typedef struct adjnode *ptradjlist;
    typedef struct Enode *Edge;
    typedef struct Queue *que;
    typedef struct Vnode
    {
        ptradjlist firstedge;
    }ad;
    struct Queue
    {
        ptradjlist front;
        ptradjlist rear;
    };
    struct Gnode
    {
        int nv;
        int ne;
        ad G[MAX];
    };
    struct adjnode
    {
        int adj;
        int weight;
        ptradjlist next;
    };
    struct Enode
    {
        int v,w;
        int weight;
    };
    int visit[MAX];
    
    Lgraph CreateLgraph(int n);     //初始化有n个结点的图
    void Insert(Lgraph G, Edge E);   //把边插入
    Lgraph BuildLgraph();           //完整的创建一个图
    void DFS(Lgraph v,int i); //深度遍历图
    void RESET(int nv); //重置visit的值
    que Createqueue();  //创建有头结点的队列
    int Delete(que q);
    void Inserts(que q, int x);
    void BFS(Lgraph v, int i, que q);  //广度遍历
    int Isempty(que q);
    
    int main(void)
    {
        Lgraph v;
        ptradjlist w;
        que q;
        v = BuildLgraph();
        w = v->G[0].firstedge;
        if(w->next!=NULL)
            printf("%d\n",w->next->adj);
        printf("BFS\n");
        q = Createqueue();
        BFS(v,0,q);
        printf("DFS\n");
        DFS(v,0);
        putchar('\n');
        RESET(v->nv);
        if(v->G[0].firstedge->next == NULL)
            printf("over\n");
        printf("run over\n");
        return 0;
    }
    
    Lgraph CreateLgraph(int n)     //初始化有n个结点的图
    {
        Lgraph g = (Lgraph)malloc(sizeof(struct Gnode));
        int i;
        g->nv = n;
        g->ne = 0;
        for(i = 0; i < n; i++)
            g->G[i].firstedge = NULL;
        return g;
    }
    
    void Insert(Lgraph G, Edge E)   //把边插入
    {
        ptradjlist aj;
        aj = (ptradjlist)malloc(sizeof(struct adjnode));
        aj->adj = E->w;
        aj->weight = E->weight;
        aj->next = G->G[E->v].firstedge;
        G->G[E->v].firstedge = aj;
        /*aj = (ptradjlist)malloc(sizeof(struct adjnode));
        aj->adj = E->v;
        aj->weight = E->weight;
        aj->next = G->G[E->w].firstedge;
        G->G[E->w].firstedge = aj;
        */
    }
    
    Lgraph BuildLgraph()           //完整的创建一个图
    {
        Lgraph g;
        int n, i;
        Edge e;
        e = (Edge)malloc(sizeof(struct Enode));
        printf("please input nv\n");
        scanf("%d",&n);
        g = CreateLgraph(n);
        printf("please input ne\n");
        scanf("%d",&g->ne);
        for(i = 0; i < g->ne; i++)
        {
            scanf("%d %d %d",&e->v,&e->w,&e->weight);
            Insert(g,e);
        }
        return g;
    }
    
    void DFS(Lgraph v,int i) //深度遍历图
    {
        ptradjlist w = v->G[i].firstedge;
        if(visit[i] == 0)
        {
            visit[i] = 1;
            printf("%d  ",i);
        }
        for( ; w; w = w->next)
        {
            if(visit[w->adj] == 0)
            {
                visit[w->adj] = 1;
                printf("%d  ",w->adj);
                /*if(v->G[w->adj].firstedge==NULL && w->next!=NULL && visit[w->next->adj]==0)
                    printf("\n%d  ",i);
                */
                DFS(v,w->adj);
            }
        }
    
    }
    
    void RESET(int nv) //重置visit的值
    {
        int i;
        for(i = 0; i < nv; i++)
            visit[i] = 0;
    }
    
    que Createqueue()  //创建有头结点的队列
    {
        que q = (que)malloc(sizeof(struct Queue));
        q->front = (ptradjlist)malloc(sizeof(struct adjnode));
        q->front->next = NULL;
        q->rear = q->front;
        return q;
    }
    
    int Delete(que q)
    {
        int y;
        ptradjlist temp;
        if(q->front->next == q->rear)
        {
            temp = q->front->next;
            y = temp->adj;
            free(temp);
            q->front->next = NULL;
            q->rear = q->front;
            return y;
        }
        temp = q->front->next;
        q->front->next = temp->next;  //这里出错了next没加
        y = temp->adj;
        free(temp);
        return y;
    
    }
    
    void Inserts(que q, int x)
    {
        ptradjlist temp = (ptradjlist)malloc(sizeof(struct adjnode));
        temp->adj = x;
        temp->next = NULL;
        q->rear->next = temp;
        q->rear = temp;
    }
    
    int Isempty(que q)
    {
        if(q->front == q->rear)
                return 1;
        else
            return 0;
    }
    
    void BFS(Lgraph v, int i, que q)  //广度遍历
    {
        int t;
        ptradjlist w = NULL;
        visit[i] = 1;
        Inserts(q, i);
        while(!Isempty(q))
        {
            t = Delete(q);
            printf("%d ",t);
            w = v->G[t].firstedge;
            if(w->next == NULL)
                printf("over\n");
            for(; w; w = w->next)
            {
                if(w == NULL)
                    printf("null\n");
                if(!visit[w->adj])
                {
                    visit[w->adj] = 1;
                    Inserts(q, w->adj);
                }
            }
        }
        putchar('\n');
    }
    /*
    
    0 1 5
    1 2 5
    0 3 5
    */
    
    
    
    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB yalmip 可转移负荷的简单建模出错,如何解决?
  • ¥15 数学的三元一次方程求解
  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?