考研之图的遍历

我不是女神ヾ 2021-11-09 02:50 255阅读 0赞

我觉得我在学英语。arc 弧 node 点 graph 图
    以下代码都是连接表访问

typedef struct arcnode//边节点
    {
        int adjvex;
        struct arcnode *nextarc;
        int info;
        
    }arcnod
    //我们去想象一个图，边是不是连接着2个点。和可能需要长度。 adjvex-邻接点域也就是他指向一个节点，那么我们这里用下一条边的指针。
    ps ：那个info是information的缩写。
    
    typedef struct vnode//点节点
    {
        char data;
        arcnode *fristarc;
    }vnode;  
    
    //接下来就是点。我们的点节点不一定是1234也有可能是ABC呀我们就需要一个去存信息。
    点链接的是边。还需要下一个边。
    int visit[1000];
    typedef struct Agraph//图节点
    {
        vnode adjlist[maxSize];
        int n,e;
    }Agraph;
    就是一张图。adjlist——连接表。这个连接表是maxsize个的点组成，在保存一个节点数和边数。

void dfs(Agraph *G,int v)
    {
        arcnode *p;
        visit[v]=1;
        Visit(v);//漏了；
        p=G->adjlist[v].fristarc;
        if(p!=NULL)
        {
            if(visit[p->adjvex]==0)
                dfs(G ,p->adjvex);
            p=p->nextarc;
        }
        
    }
    //深度优先遍历。搜到底为止，相当于树的前序遍历，防止重复遍历需要一个visit标记。visit=1访问完成。

void  bfs(Agraph *G,int v)
    {
        Visit(v);
        visit[v]=1;
        arcnode *p;
        int queue[maxSize],front=0,rear=0;
        rear=(rear+1)%maxSize;
        queue[rear]=v;
        while(rear!=front)
        {
            front=(front+1)%maxSize;
            int temp=queue[front];
            p=G->adjlist[temp].fristarc;
            if(visit[temp]==0)
            {
                Visit(temp);
                visit[temp]=1;
                rear=(rear+1)%maxSize;
                queue[rear]=p->adjvex;
            }
            p=p->nextarc;
        }
        
        
    }

广度优先遍历。搜到底为止，相当于树的层次遍历，防止重复遍历需要一个visit标记。visit=1访问完成。每到一个结点若没有遍历过就入队列。直到队列空。

转载于:https://www.cnblogs.com/2014slx/p/11131190.html