图的dfs递归(非递归)遍历和bfs遍历(邻接表)

el/2024/3/2 12:07:15

1.深度优先遍历是连通图的一种遍历策略.其基本思想如下:

设x是当前被访问的顶点,在对x做过访问的标记之后,选择一条从x出发的未检测过的边(x,y),若发现顶点y已经访问过了,则重新选择另一条从x出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过,然后从y开始搜索,直到搜索完从y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯到顶点x,并且再选择一条从x出发的未检测的边,直到从x出发的所有的边都已经检测过为止;

2.广度优先搜索:广度优先搜索是一种遍历策略;从一个顶点出发,辐射状地优先遍历其周围较广的区域,例如,从图的某个顶点vo出发,并访问此节点.然后依次访问v0的各个未曾访问的邻接点w1,w2,w3...,然后依次从w1,w2..出发访问各自未被访问的邻接点.重复此步骤,直到所有的顶点都被访问.

上面是两种遍历图的基本思想,用我写的代码来看具体的过程中:如图:

http://www.ystruct.com/wp-content/uploads/2015/11/tu.png 如上图:节点ABCDEFG,我们就给每个顶点依次编号1,2,3,4,5,6;(在这里,我们就以无向图来说)

首先,我们输入节点个数和关系的个数,然后依次ABCDEFG,并用相应的的结构存储它,然后输入每个节点之间的关系:AB,AC,AD,DF,DG,BE,EG,FG,CF,BD;用邻接表存储它;存储后的示意图:

1   A:2,3,4 ;          2   B:1,4,5 ;      3  C:1,6 ;          4   E:2,7;             5  F:3,4,7;               6 G:4,5,6

下面是我实现的图的建立,dfs递归和非递归,以及bfs遍历:

*************************************************************************> File Name: linjiebiao.c> Author:yang > Mail:yanglongfei@xiyoulinux.org> Created Time: 2015年11月26日 星期四 22时38分28秒************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
typedef struct Stack
{
int data;
struct Stack next;
}LinkStack;
typedef struct Queue
{
int data;
struct Queue next;
}LNode;
typedef struct
{
LNode front;
LNode rear;
}LinkQueue;
typedef struct ArcNode
{
int adjvex;
struct ArcNode next;
}ArcNode;
typedef struct VertexNode
{
char vexdata;
ArcNode head;
}VertexNode;
typedef struct
{
VertexNode vertex[MAXVEX];
int vexnum; //顶点数 
int arcnum; //边数
}AdjList;
/栈的操作
****/
LinkStack *Init_LinkStack(LinkStack *T)
{
T=(LinkStack *)malloc(sizeof(LinkStack));
T->next=NULL;
return T;
}
int IsEmpty_LinkStack(LinkStack T)
{
if(T->next!=NULL){
return 0;
}
return 1;
}
LinkStack
Push_LinkStack(LinkStack *T,int t)
{
LinkStack s=(LinkStack )malloc(sizeof(LinkStack));
if(sNULL){
return NULL;
}
s->data=t;
s->next=T->next;
T->next=s;
}
LinkStack *Pop_LinkStack(LinkStack *T,int *t)
{
LinkStack *p=T->next;
if(T->next
NULL){
return NULL;
}
t=p->data;
T->next=p->next;
free§;
}
/队列的操作
/
LinkQueue *Init_LinkQueue()
{
LinkQueue *q=(LinkQueue *)malloc(sizeof(LinkQueue));
LNode *p=(LNode *)malloc(sizeof(LNode));
p->next=NULL;
q->front=q->rear=p;
return q;
}
int IsEmpty_LinkQueue(LinkQueue *q)
{
if(q->front == q->rear){
return 1;
}
return 0;
}
void EnterQueue(LinkQueue *q,int t)
{
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data=t;
s->next=NULL;
q->rear->next=s;
q->rear=s;
}
int OutQueue(LinkQueue *q,int *t)
{
LNode *p;
if(IsEmpty_LinkQueue(q)){
printf(“the Queue is Empty!\n”);
return 0;
}else{
p=q->front->next;
*t=p->data;
q->front->next=p->next;
free§;
if(q->front->next==NULL){
q->rear=q->front;
}
return 1;
}
}
VertexNode *Insert(VertexNode *h,ArcNode *p) //此函数的意义是把每个链表根据adjvex的按从小到大的顺序排列;
{
ArcNode *pre,*cur,*q;
cur=h->head;
if(cur == NULL){
p->next=cur;
cur->next=p;

}else{pre =h-&gt;head;q=h-&gt;head-&gt;next;while(q){if(p-&gt;adjvex &lt; q-&gt;adjvex ){p-&gt;next=q;pre-&gt;next=p;break;}pre = q;q=q-&gt;next;}if(q == NULL){  //当新的节点比当前链表中的所有的adjvex都大时,直接插在链表的最后面.p-&gt;next==NULL;pre-&gt;next = p;}
}
return h;

}
AdjList Created_Graph(AdjList G)
{
int i,j,k,n1,n2;
ArcNode s;
char vex1,vex2;
G=(AdjList )malloc(sizeof(AdjList));
printf(“请输入顶点的个数和边数:”);
scanf("%d%d",&G->vexnum,&G->arcnum);
printf(“请输入顶点:\n”);
for(i=1;i<=G->vexnum;i++)
{
printf(“No.%d号顶点的值:”,i);
scanf(" %c",&G->vertex[i].vexdata);
G->vertex[i].head=(ArcNode )malloc(sizeof(ArcNode)); //为每个头节点开辟空间;有头节点的链表;
G->vertex[i].head->next=NULL; //头节点指向为空;
}
printf(“请输入由两个顶点构成的边:”);
for(k=1;k<=G->arcnum;k++){
scanf(" %c%c",&vex1,&vex2);
for(i=1;i<=G->vexnum;i++){
if(G->vertex[i].vexdata == vex1){
n1=i;
}
if(G->vertex[i].vexdata == vex2){
n2=i;
}
}
s=(ArcNode )malloc(sizeof(ArcNode));
s->adjvex = n2;
Insert(&G->vertex[n1],s);
/如果是有向图,则下面的语句去掉就行/
s=(ArcNode )malloc(sizeof(ArcNode));
s->adjvex = n1;
Insert(&G->vertex[n2],s);
}
return G;
}
int visited[MAXVEX]={0};
void dfs(AdjList G,int i)
{
ArcNode p;
printf("%c ",G->vertex[i].vexdata);
visited[i]=1;
p=G->vertex[i].head->next;
while§{
if(visited[p->adjvex]==0){
dfs(G,p->adjvex);
}
p=p->next;
}
}
void trans_dfs(AdjList G)
{
int v;
for(v=1;v<=G->vexnum;v++){
visited[v]=0;
}
for(v=1;v<=G->vexnum;v++){
if(visited[v]==0){
dfs(G,v); //当图只有一个连通分量时,此句只会执行一次;
}
}
}
void undfs(AdjList G,int vo)
{
LinkStack T;
ArcNode p;
T=Init_LinkStack(T);
int visited[MAXVEX]={0},i, t;
Push_LinkStack(T,vo);
while(!IsEmpty_LinkStack(T)){
Pop_LinkStack(T,&t);
if(visited[t]==0){
printf("%c “,G->vertex[t].vexdata);
visited[t]=1;
}
p=G->vertex[t].head->next;
while§{
if(visited[p->adjvex] == 0){
printf(”%c ",G->vertex[p->adjvex].vexdata);
visited[p->adjvex]=1;
Push_LinkStack(T,p->adjvex);
p=G->vertex[p->adjvex].head->next;
}else{
p=p->next;
}
}
}
//for(i=1;i<=G->vexnum;i++){}
}
void bfs(AdjList G,int v)
{
int i,t;
ArcNode p;
LinkQueue S=Init_LinkQueue();
for(i=1;i<=G->vexnum;i++)
{
visited[i]=0;
}
visited[v]=1;
printf("%c “,G->vertex[v].vexdata);
EnterQueue(S,v);
while(!IsEmpty_LinkQueue(S)){
OutQueue(S,&t);
p=G->vertex[t].head->next;
while§{
if(visited[p->adjvex]==0){
printf(”%c ",G->vertex[p->adjvex].vexdata);
visited[p->adjvex]=1;
EnterQueue(S,p->adjvex);
}
p=p->next;
}
}
}
void print(AdjList G)
{
ArcNode p;
int i;
for(i=1;i<=G->vexnum;i++){
printf(" %c:",G->vertex[i].vexdata);
p=G->vertex[i].head->next;
while§
{
printf("%d “,p->adjvex);
p=p->next;
}
printf(”\n");
}
}
int main(int argc,char argv[])
{
AdjList G;
G=Created_Graph(G);
print(G);
printf("dfs递归遍历
\n");
dfs(G,1);
printf("\n");
printf("dfs递归遍历多个连通分量
**\n");
trans_dfs(G);
printf("\n");
printf(“dfs非递归遍历******\n”);
undfs(G,1);
printf("\n");
printf(“bfs遍历*******\n”);
bfs(G,1);
printf("\n");
return 0;
}



http://www.ngui.cc/el/4466243.html

相关文章

2018HPU暑期集训第四次积分训练赛 K - 方框 题解(图形打印)

2018HPU暑期集训第四次积分训练赛 K - 方框 题解&#xff08;图形打印&#xff09; 思路分析&#xff1a;题目已经明确透露了这道题的解法&#xff1a;就是画框。当 输入的边长 n - 4 > 0 的话&#xff0c;就表示可以在内层继续嵌套一个方框。废话就不多说了&#xff0c;直…

【洛谷】P1067 多项式输出

原题链接&#xff1a;P1067 多项式输出 代码如下&#xff1a; #include <bits/stdc.h>using namespace std;const int MAX 105;int n;int num[MAX]; int main() {int flag;cin >> n;for (int i 0; i < n; i) // 输入多项式的幂次数 cin >> num[i];f…

HDU 2032 杨辉三角

Problem Description 还记得中学时候学过的杨辉三角吗&#xff1f;具体的定义这里不再描述&#xff0c;你可以参考以下的图形&#xff1a; 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 Input 输入数据包含多个测试实例&#xff0c;每个测试实例的输入只包含一个正整数n&…

2058(等差求和)

HDU 2058 The sum problem 等差求和公式: Sn(a1aN)*n/2 (a1a1d(n-1))*n/2 a1*nd(n-1)*n/2; 因为此处公差d1&#xff0c;所以Sna1*n(n-1)*n/2,当从第一项开始算起时&#xff08;因本题首项为1&#xff0c;即a11时&#xff09;&#xff0c;SnM时的项的个数n最多; a11&a…

HDU 2059(dp)

龟兔赛跑 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description 据说在很久很久以前&#xff0c;可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后&#xff0c;心中郁闷&#xff0c;发誓要报仇雪恨&#xff0c;于是…

匈牙利算法 (二分匹配法)

过山车 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10683 Accepted Submission(s): 4699 Problem Description RPG girls今天和大家一起去游乐场玩&#xff0c;终于可以坐上梦寐以求的过山车了。可是&am…

HDU 汉诺塔III

汉诺塔III Problem Description 约19世纪末&#xff0c;在欧州的商店中出售一种智力玩具&#xff0c;在一块铜板上有三根杆&#xff0c;最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上&#xff0c;条件是一次只能移动一…

HDU 小兔的棋盘(卡特兰数)

小兔的棋盘 Problem Description 小兔的叔叔从外面旅游回来给她带来了一个礼物&#xff0c;小兔高兴地跑回自己的房间&#xff0c;拆开一看是一个棋盘&#xff0c;小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0&#xff0c;0)走到终点(n,n)的最短路径数是C(2n,n),…

HDU 2068(错排)

RPG的错排 Problem Description 今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜&#xff0c;第一次猜&#xff1a;R是公主&#xff0c;P是草儿&#xff0c;G是月野兔&#xff1b;第…

HDU 2069

hdu 2069 Coin Change&#xff08;完全背包&#xff09; Coin Change Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 16592 Accepted Submission(s): 5656 Problem Description Suppose there are 5 types of coins…