2019-06-11 22:17

# 求一个代码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 Enode *Edge;
typedef struct Queue *que;
typedef struct Vnode
{
struct Queue
{
};
struct Gnode
{
int nv;
int ne;
};
{
int weight;
};
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;
que q;
v = BuildLgraph();
w = v->G[0].firstedge;
if(w->next!=NULL)
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)   //把边插入
{
aj->weight = E->weight;
aj->next = G->G[E->v].firstedge;
G->G[E->v].firstedge = aj;
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));
scanf("%d",&n);
g = CreateLgraph(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) //深度遍历图
{
if(visit[i] == 0)
{
visit[i] = 1;
printf("%d  ",i);
}
for( ; w; w = w->next)
{
{
printf("\n%d  ",i);
*/
}
}

}

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->next = NULL;
q->rear = q->front;
return q;
}

int Delete(que q)
{
int y;
if(q->front->next == q->rear)
{
temp = q->front->next;
free(temp);
q->front->next = NULL;
q->rear = q->front;
return y;
}
temp = q->front->next;
q->front->next = temp->next;  //这里出错了next没加
free(temp);
return y;

}

void Inserts(que q, int 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;
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");
{
}
}
}
putchar('\n');
}
/*

0 1 5
1 2 5
0 3 5
*/

``````
点赞 评论