图的深度、广度优先探索（数据结构）-Toy模板网

这篇具有很好参考价值的文章主要介绍了图的深度、广度优先探索（数据结构）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

深度：

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

typedef 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 100

typedef 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);//递归遍历
}

文章来源地址https://www.toymoban.com/news/detail-633185.html

到了这里，关于图的深度、广度优先探索（数据结构）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！