图遍历的算法

叁歲伎倆 2022-06-04 03:38 182阅读 0赞

深度优先遍历 (递归)  
广度优先遍历

深度优先遍历 (非递归)

//graph.h头文件
    typedef int InfoType;
    #define MAXV 100
    typedef struct
    {
        int no;
        InfoType info;
    }VertexType;
    typedef struct
    {
        int edges[MAXV][MAXV];
        int vexnum,arcnum;
        VertexType vexs[MAXV];
    }MGraph;
    typedef struct ANode
    {
        int adjvex;
        struct ANode *nextarc;
        InfoType info;
    
    }ArcNode;
    typedef int Vertex;
    typedef struct Vnode
    {
        Vertex data;
        ArcNode *firstarc;
    }VNode;
    typedef VNode AdjList[MAXV];
    typedef struct
    {
        AdjList adjlist;
        int n,e;
    }ALGraph;

//主要实现代码
    #include <iostream>
    #include <malloc.h>
    #include "graph.h"
    int visited[MAXV];
    
    using namespace std;
    
    ALGraph *MatToList(MGraph g)
    {
        int i,j,n=g.vexnum;
        ArcNode *p;
        ALGraph *G;
        G=(ALGraph*)malloc(sizeof(ALGraph));
        for(i=0;i<n;i++)
        {
            G->adjlist[i].firstarc=NULL;
        }
        for(i=0;i<n;i++)
    
            for(j=n-1;j>=0;j--)
    
                if(g.edges[i][j]!=0)
                {
                    p=(ArcNode*)malloc(sizeof(ArcNode));
                    p->adjvex=j;
                    p->info=g.edges[i][j];
                    p->nextarc=G->adjlist[i].firstarc;
                    G->adjlist[i].firstarc=p;
                }
                G->n=n;
        G->e=g.arcnum;
    
    
    return G;
    
    }
    void DispAdj(ALGraph *G)
    {
        int i;
        ArcNode *p;
        for(i=0;i<G->n;i++)
        {
            p=G->adjlist[i].firstarc;
            if(p!=NULL)
            {
                cout<<"  "<<i;
                while(p!=NULL)
                {
                    cout<<"  "<<p->adjvex;
                    p=p->nextarc;            }
            }
            cout<<endl;
        }
    }
    void DFS(ALGraph *G,int v)
    {
        ArcNode *p;
        visited[v]=1;
        cout<<"  "<<v;
        p=G->adjlist[v].firstarc;
        while(p!=NULL)
        {
            if(visited[p->adjvex]==0)
            {
                DFS(G,p->adjvex);
    
            }
              p=p->nextarc;
        }
    }
    void DFS1(ALGraph *G,int v)
    {
        int i,visited[MAXV],St[MAXV],top=-1;
        ArcNode *p;
        for(i=0;i<G->n;i++)
        {
            visited[i]=0;
        }
        cout<<"  "<<v;
        top++;
        St[top]=v;
        visited[v]=1;
        while(top>-1)
        {
            v=St[top];
            p=G->adjlist[v].firstarc;
            while(p!=NULL&&visited[p->adjvex]==1)
            {
                p=p->nextarc;
            }
            if(p==NULL)
            {
                top--;
            }
            else
            {
                v=p->adjvex;
                cout<<"  "<<v;
                visited[v]=1;
                top++;
                St[top]=v;
            }
        }
        cout<<endl;
    }
    void BFS(ALGraph *G,int v)
    {
        ArcNode *p;
        int queue[MAXV],front=0,rear=0;
        int visited[MAXV];
        int w,i;
        for(i=0;i<G->n;i++)
        {
            visited[i]=0;
        }
        cout<<"  "<<v;
        visited[v]=1;
        rear=(rear+1)%MAXV;
        queue[rear]=v;
        while(front!=rear)
        {
            front=(front+1)%MAXV;
            w=queue[front];
            p=G->adjlist[w].firstarc;
            while(p!=NULL)
            {
                if(visited[p->adjvex]==0)
                {
                    cout<<"  "<<p->adjvex;
                    visited[p->adjvex]=1;
                    rear=(rear+1)%MAXV;
                    queue[rear]=p->adjvex;
                }
                p=p->nextarc;
            }
        }
    
        cout<<endl;
    }
    
    int main()
    {
        int i,j;
        MGraph g;
        ALGraph *G;
        int A[MAXV][5]={
        {0,1,1,0,0},
        {1,0,0,1,1},
        {1,0,0,0,0},
        {0,1,0,0,0},
        {0,1,0,0,0},
        };
       g.vexnum=5;
       g.arcnum=4;
       for(i=0;i<g.vexnum;i++)
       {
           for(j=0;j<g.vexnum;j++)
           {
               g.edges[i][j]=A[i][j];
           }
       }
       G=MatToList(g);
       cout<<"图的邻接表"<<endl;
       DispAdj(G);
       cout<<"从顶点0开始的DFS（递归算法）"<<endl;
       DFS(G,0);
       cout<<endl;
       cout<<"从顶点0开始的DFS（非递归算法）"<<endl;
       DFS1(G,0);
       cout<<"从顶点0开始的BFS（递归算法）"<<endl;
       BFS(G,0);
        return 0;
    }

![Center][]

[Center]: /images/20220604/2bb9a8f5f2c44cbea77834d0d658cd69.png