[图]图和图遍历（BFS和DFS）（一）

1. 图的存储结构

常见的图存储结构主要分为邻接矩阵和邻接表两种。

1.1 图的邻接矩阵表示：

image.png

图结构：

#include <stdio.h>
#include <stdlib.h>
#define maxVertices 30              //最大顶点数目
#define maxEdges 450                //最大边数目
typedef char Type;

struct MGrap{
    Type VerticesList[maxVertices];
    int Edges[maxVertices][maxVertices];
    int numVertices,numEdges;
};

图的创建：

#include "MGraph.h"
#include <limits.h>
#include <queue>


int getVertexPos(MGrap &G, Type v)//根据顶点数据获取顶点号
{
    for(int i = 0; i < G.numVertices; i++)
    {
        if(G.VerticesList[i].data == v)
        {
            return i;
        }
    }
    return -1;
}

int numOfVertices(MGrap &G)
{
    return G.numVertices;
}

int numOfEdges(MGrap &G)
{
    return G.numEdges;
}

int firstNeighbor(MGrap &G, int v)
{
    if(v!=-1)
    {
        for(int i = 0; i < G.numVertices; i++)
        {
            if(G.Edges[v][i]>0&&G.Edges[v][i]<INT_MAX)
            {
                return i;
            }
        }
    }
    return -1;
}

int nextNeighbor(MGrap &G, int v, int w)
{
    if(v!=-1 && w!=-1)
    {
        for(int i = w+1; i < G.numVertices; i++)
        {
            if(G.Edges[v][i]>0&&G.Edges[v][i]<INT_MAX)
            {
                return i;
            }
        }

    }
    return -1;
}

void createALGrap(MGrap &G, Type v[], int n, Type ed[][2], int c[], int e, int d)
{
    G.numVertices = n;
    G.numEdges = e;
    for(int i = 0; i < n; i++)//建立顶点集
    {
        G.VerticesList[i] = v[i];
        for(int j = 0; j < G.numVertices; j++)
        {
            G.Edges[i][j] = (i==j)?0:INT_MAX;
        }
    }

    for(int i = 0; i < G.numEdges; i++)
    {
        int e1 = getVertexPos(G,ed[i][0]);
        int e2 = getVertexPos(G,ed[i][1]);
        G.Edges[e1][e2] = c[i];
        if(d == 0) G.Edges[e2][e1] = c[i];
    }

}

1.2 图的邻接表表示

image.png

邻接表结构：

#include <stdio.h>
#include <stdlib.h>
#define maxVertices 30              //最大顶点数目
#define maxEdges 450                //最大边数目
typedef char Type;
typedef int Weight;

struct Enode{//边节点
    int dest;//边的另一个顶点
    int cost;//权重
    struct Enode *link;//下一个边节点位置
};

struct Vnode{//顶点定义
    Type data;
    Enode *adj;//顶点的边
};

struct ALGrap{
    Vnode VerticesList[maxVertices];
    int numVertices,numEdges;
};

图的创建：

#include "MGraph.h"
#include <limits.h>
#include <queue>


int getVertexPos(MGrap &G, Type v)//根据顶点数据获取顶点号
{
    for(int i = 0; i < G.numVertices; i++)
    {
        if(G.VerticesList[i].data == v)
        {
            return i;
        }
    }
    return -1;
}

int numOfVertices(MGrap &G)
{
    return G.numVertices;
}

int numOfEdges(MGrap &G)
{
    return G.numEdges;
}

int firstNeighbor(MGrap &G, int v)
{
    if(v!=-1)
    {
        for(int i = 0; i < G.numVertices; i++)
        {
            if(G.Edges[v][i]>0&&G.Edges[v][i]<INT_MAX)
            {
                return i;
            }
        }
    }
    return -1;
}

int nextNeighbor(MGrap &G, int v, int w)
{
    if(v!=-1 && w!=-1)
    {
        for(int i = w+1; i < G.numVertices; i++)
        {
            if(G.Edges[v][i]>0&&G.Edges[v][i]<INT_MAX)
            {
                return i;
            }
        }

    }
    return -1;
}

void createALGrap(MGrap &G, Type v[], int n, Type ed[][2], int c[], int e, int d)
{
    G.numVertices = n;
    G.numEdges = e;
    for(int i = 0; i < n; i++)//建立顶点集
    {
        G.VerticesList[i] = v[i];
        for(int j = 0; j < G.numVertices; j++)
        {
            G.Edges[i][j] = (i==j)?0:INT_MAX;
        }
    }

    for(int i = 0; i < G.numEdges; i++)
    {
        int e1 = getVertexPos(G,ed[i][0]);
        int e2 = getVertexPos(G,ed[i][1]);
        G.Edges[e1][e2] = c[i];
        if(d == 0) G.Edges[e2][e1] = c[i];
    }

}

void DFS1(MGrap &G, int v, int visit[])
{
    cout<<v;
    visit[v] = true;
    for(int w = firstNeighbor(G,v); w!=-1; w = nextNeighbor(G,v,w))
    {
        if(!visit[w]) DFS1(G,w,visit);
    }
}

void DFS_Traversal(MGrap &G, int v)
{
    int n = G.numVertices;
    bool visit[n];
    for(int i = 0; i < n; i++)
    {
        visit[i] = false;
    }
    DFS1(G,v,visit);

}

void BFS(MGrap &G)
{
    int n = G.numVertices;
    bool visit[n];
    for(int i = 0; i < n; i++)
    {
        visit[i] = false;
    }
    queue<int> Q;

    for(int i = 0; i < n; i++)
    {
        if(!visit[i])
        {
            cout<<G.numVertices[i];
            visit[i] = true;
            Q.push(i);
            while(!Q.empty())
            {
                int j = Q.front();
                Q.pop();
                for(int w = firstNeighbor(G,j); w!=-1; w = nextNeighbor(G,j,w))
                {
                    if(!visit[w])
                    {
                        cout<<G.numVertices[w];
                        visit[w] = true;
                        Q.push(w);
                    }
                }

            }
        }

    }

}

2. 图遍历

深度优先遍历DFS

void DFS1(MGrap &G, int v, int visit[])
{
    cout<<v;
    visit[v] = true;
    for(int w = firstNeighbor(G,v); w!=-1; w = nextNeighbor(G,v,w))
    {
        if(!visit[w]) DFS1(G,w,visit);
    }
}

void DFS_Traversal(MGrap &G, int v)
{
    int n = G.numVertices;
    bool visit[n];
    for(int i = 0; i < n; i++)
    {
        visit[i] = false;
    }
    DFS1(G,v,visit);

}

广度优先遍历BFS

void BFS(MGrap &G)
{
    int n = G.numVertices;
    bool visit[n];
    for(int i = 0; i < n; i++)
    {
        visit[i] = false;
    }
    queue<int> Q;

    for(int i = 0; i < n; i++)
    {
        if(!visit[i])
        {
            cout<<G.numVertices[i];
            visit[i] = true;
            Q.push(i);
            while(!Q.empty())
            {
                int j = Q.front();
                Q.pop();
                for(int w = firstNeighbor(G,j); w!=-1; w = nextNeighbor(G,j,w))
                {
                    if(!visit[w])
                    {
                        cout<<G.numVertices[w];
                        visit[w] = true;
                        Q.push(w);
                    }
                }

            }
        }

    }

}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 数据结构与算法（六），图
    图是一种比线性表和树更复杂的数据结构，在图中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。图是一种多对...
    Alent阅读 2,431评论 1赞 22
  • 《大话数据结构》总结
    第一章 绪论 什么是数据结构？ 数据结构的定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 6,013评论 0赞 19
  • 雨滴
    雨一直下个不停 听着窗外的雨声 和我现在的心情一样 心头有太多的事被烦扰 5月在雨水的陪伴下已过去大半 而我也已经...
    BINGBIGN阅读 384评论 0赞 2
  • 我想和你虚度时光                            ----李元胜
    我想和你虚度时光，比如低头看鱼 比如把茶杯留在桌子上，离开 浪费它们好看的阴影 我还想连落日一起浪费，比如散步 一...
    芬fen阅读 290评论 0赞 0
  • 观紫荆花 游太平峪
    己丑愚人次日，恰太平五届紫荆节，锣鼓激越，彩旗风烈。沿阶趋上，直走龙口瀑布，冷气袭人，顿觉舒然，欲走近而未行。稍息...
    邓文伟阅读 234评论 0赞 0

友情链接更多精彩内容