MENU

[C++]图的储存结构的实现和应用

November 28, 2019 • Read: 109 • 程序笔记

前言

第七次数据结构作业,记录一下代码

运行结果

Snipaste_2019-11-27_20-57-24.png

源代码

#include<iostream>
using namespace std;
#define MaxVertexNum 50       /*最大顶点数设为50*/
typedef struct
{    int vexs[MaxVertexNum]; /*顶点表*/
    int edges[MaxVertexNum][MaxVertexNum];   /*邻接矩阵,即边表*/
    int n,e;                       /*顶点数和边数*/
}MGraph;   /*Maragh是以邻接矩阵存储的图类型*/

int visited[MaxVertexNum] = {0};   //记录被访问过的顶点,初始值0

void CreateMGraph(MGraph *G)
{  int i, j, k;
    cout<<"请输入顶点数和边数:\n";
    cin>>G->n>>G->e;          /*输入顶点数和边数*/
    for (i=1;i<=G->n;i++)  /*获取顶点信息,建立顶点表*/
        G->vexs[i]=i;
    for (i=1;i<=G->n;i++)
        for (j=1;j<=G->n;j++)
            G->edges[i][j]=0;                     /*初始化邻接矩阵*/
    for (k=1;k<=G->e;k++)
    {   cout<<"请输入每条边对应的两个顶点的序号:\n";
        cin>>i>>j;   /*输入e条边,建立邻接矩阵*/
        G->edges[i][j]=1;
        G->edges[j][i]=1;
    }
}

void DFSAL(MGraph *G,int v)//深度递归遍历连通图
{    int i=1 ;
    cout<<G->vexs[v]<<"\t";
    visited[v]=1;
    for (i=1; i<=G->n; i++)     /*vi未访问过,从vi开始DFS搜索*/
        if(!visited[i]&&G->edges[v][i]==1) DFSAL(G,i);            //补充
}

void Bread(MGraph *G)  /*广度非递归搜索遍历算法*/
{
    int q[MaxVertexNum];
    int front=0;
    int rear=0;
    int k,i,j;
    for(i=1;i<=G->n;i++)   /*辅助数组初始化*/
        visited[i]=0  ;//补充
    for(k=1;k<=G->n;k++)    /*从出发点开始搜索遍历*/
    {
        if( visited[k]==0)
        {
            rear++;       /*起始点入队列*/
            q[rear]=k;
            while(front!=rear)    /*队列非空*/
            {
                front++;          /*队头元素出队列*/
                i=q[front];
                if( visited[i]!=1)    /*如果未被访问*/
                {
                    visited[i]=1;     /*置访问标志为1,遍历输出*/
                    cout<<i<<'\t';
                }
                for(j=1;j<=G->n;j++) /*依次访问各个未曾被访问的邻接点*/
                    if(G->edges[i][j]==1 &&  visited[j]==0)
                    {
                        cout<<j<<'\t';   /*遍历输出,置访问标志,入队列*/
                        visited[j]=1;
                        rear++;
                        q[rear]=j;
                    }
            }
        }
    }
}

int main() {
    MGraph *G = new MGraph;
    int v;
    CreateMGraph(G);
    cout << "请输入开始遍历的顶点编号:\n";
    cin >> v;
    cout << "深度递归遍历结果:\n";
    DFSAL(G, v);
    cout << endl;
    cout << "广度非递归遍历结果:\n";
    Bread(G);
    cout << endl;
    return 0;
}
Archives QR Code Tip
QR Code for this page
Tipping QR Code