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

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

1个回答

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

#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
*/


Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问