图的深度、广度优先探索（数据结构）

深度：

#include <stdio.h>
#include <stdlib.h>
#define MAX 20typedef struct ANode
{int adjver,len;struct ANode*next;
} ArcNode;typedef struct VNode
{int data;ArcNode*firstarc;
} VertexNode;typedef struct
{VertexNode vers[MAX+1];int vernum,arcnum;
} AdjList;void Create(AdjList*AL);
void Deepth(AdjList AL,int v0,int v1);int sign;
int visited[MAX];int main()
{AdjList A;Create(&A);for(int i=1; i<=A.vernum; i++)visited[i]=0;int v0,v1;scanf("%d %d",&v0,&v1);Deepth(A,v0,v1);if(sign)printf("yes");else printf("no");return 0;
}void Create(AdjList*AL)
{scanf("%d %d",&(AL->vernum),&(AL->arcnum));for(int i=1; i<=AL->vernum; i++)scanf("%d",&(AL->vers[i].data));for(int i=1; i<=AL->vernum; i++){int v1,v2;scanf("%d %d",&v1,&v2);ArcNode*ins=(ArcNode*)malloc(sizeof(ArcNode));ins->adjver=v2;ins->next=AL->vers[v1].firstarc;AL->vers[v1].firstarc=ins;}
}void Deepth(AdjList AL,int v0,int v1)
{visited[v0]=1;if(v0==v1){sign=1;return;}ArcNode*p=AL.vers[v0].firstarc;for(; p!=NULL; p=p->next){if(visited[p->adjver]==0)Deepth(AL,p->adjver,v1);}
}

广度：

#include <stdio.h>
#include <stdlib.h>
#define MAX 100typedef struct
{int data[MAX];int front,rear;//队头，队尾
}Queue;typedef struct ArcNode
{int adjver;//弧指向的顶点struct ArcNode* nextarc;//下一条弧的指针
}ArcNode;typedef struct VertexNode
{int data;//顶点数据ArcNode*firstarc;//该顶点的一条弧的指针
}VertexNode;typedef struct
{VertexNode vertexs[MAX];//顶点数组int vernum,arcnum;//顶点总数，弧总数
}AdjList,*AList;void CreateAdjList(AList *g);//创建邻接表
void BreadthSearch(AdjList g,int vi,int vj);//广度优先搜索int visited[MAX]={0};//全局变量，标记是否查询过
Queue q;//队列，按顺序存储应该访问的顶点int main()
{AList g;int vi,vj;//要查询的两个顶点q.rear=q.front=0;//队初始化CreateAdjList(&g);//创建邻接表scanf("%d %d",&vi,&vj);BreadthSearch(*g,vi,vj);//广度优先搜索if(visited[vj]==1)printf("yes");else printf("no");return 0;
}/*创建邻接表*/
void CreateAdjList(AList *g)
{int vn,an,v1,v2;//分别是顶点总数，弧总数, 弧的前后两个顶点(*g)=(AList)malloc(sizeof(AdjList));scanf("%d %d",&vn,&an);(*g)->arcnum=an;(*g)->vernum=vn;for(int i=0;i<vn;i++){scanf("%d",&((*g)->vertexs[i].data));}for(int i=0;i<an;i++){scanf("%d %d",&v1,&v2);//弧的前后两个顶点ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));//插入的弧结点p->adjver=v2;p->nextarc=(*g)->vertexs[v1].firstarc;(*g)->vertexs[v1].firstarc=p;//完成弧节点的插入}
}/*广度优先搜索*vi：起始点*vj：终止点*/
void BreadthSearch(AdjList g,int vi,int vj)
{if(q.front>q.rear)//如果队已经没有元素，则结束return;visited[vi]=0;if(vi==vj)//找到 vj ，结束return;ArcNode*search=(ArcNode*)malloc(sizeof(ArcNode));for(search=g.vertexs[vi].firstarc;search!=NULL;search=search->nextarc)//把 vi 顶点的所有邻接点遍历{int v=search->adjver;if(visited[v]==0){visited[v]=1;q.data[q.rear++]=v;//把先访问的邻接点放在队中if(v==vj)//找到 vj ，结束return;}}BreadthSearch(g,q.data[q.front++],vj);//递归遍历
}