[图]图和图遍历（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);
                    }
                }

            }
        }

    }

}