SCNU_数据结构作业_实验5 图的算法与应用

本文主要是介绍SCNU_数据结构作业_实验5 图的算法与应用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、 邻接矩阵（验证实验【必做】）
以lab5_1.cpp为基础，参考课本180页-182页的内容，建立无向图的邻接矩阵存储结构,对建立的无向图进行深度优先遍历和广度优先遍历。请把答案代码直接补充在源文件中。课本178页图6-7的输入和输出样张如下图所示。

#include <iostream>
using namespace std;

const int MaxSize = 10;           //图中最多顶点个数
int visited[MaxSize]={0};//对全局的点初始化，表示都没有被访问

template <class DataType>
class MGraph
{
public:
	MGraph(DataType a[] , int n, int e);    //构造函数，建立具有n个顶点e条边的图
	~MGraph( ){}                  //析构函数为空
	void DFTraverse(int v);              //深度优先遍历图
	void BFTraverse(int v);               //广度优先遍历图
private:
    DataType vertex[MaxSize];          //存放图中顶点的数组
    int edge[MaxSize][MaxSize];          //存放图中边的数组
    int vertexNum, edgeNum;             //图的顶点数和边数
};

补充1//
//构造函数-图的建立
template <class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e)
{
    int i, j, k;
    vertexNum = n;
    edgeNum = e;
    //存放顶点
    for(i = 0; i < vertexNum; i++)
        vertex[i] = a[i];
    //初始化邻接矩阵
    for(i = 0; i < vertexNum; i++)
        for(j = 0; j < vertexNum; j++)
            edge[i][j] = 0;
    //依次输入每一条边
    for(k = 0; k < edgeNum; k++)
    {
        cout<< "请输入两个边的顶点序号：";
        cin >>i >>j;//输入边依附的两个顶点的编号
        edge[i][j] = 1;
        edge[j][i] = 1;//初始化边

    }

}

//深度优先遍历
template <class DataType>
void MGraph<DataType>::DFTraverse(int v)
{
    cout <<vertex[v];
    visited[v] = 1;//访问了的点，就改写为1，表示已经访问过了
    for(int j = 0; j < vertexNum; j++)
        if(edge[v][j] == 1 && visited[j] == 0)//如果边存在，且点没被访问
            DFTraverse(j);
}

//广度优先遍历
template <class DataType>
void MGraph<DataType>::BFTraverse(int v)
{
    int w, j, Q[MaxSize];//采用顺序队列
    int front = -1, rear = -1;
    cout <<vertex[v];
    visited[v] = 1;//输出顶点的值，表示已经访问
    Q[++rear] = v;//别访问的顶点入队
    while(front!=rear)//当队列非空，头尾不相等，队列就不为空
    {
        w = Q[++front];//将队头元素出队送到v中
        for(j = 0; j < vertexNum; j++)
            if(edge[w][j] == 1 && visited[j] == 0)//如果边存在，点未被访问
        {
            cout <<vertex[j];//输出点数据
            visited[j] = 1;//表示已经访问
            Q[++rear] = j;//推下一个进来
        }
    }
}

//

int main( )
{
    int i;
	char ch[]={'A','B','C','D','E','F'};
	MGraph<char> MG(ch, 6, 6);//建立6个顶点，6条边的无向图

补充2//
    for(i = 0; i < MaxSize; i++)
        visited[i] = 0;//对每个点初始化未被访问
    cout << "深度优先遍历序列是：";
    MG.DFTraverse(0);//从顶点0出发进行深度优先遍历
    cout << "\n";
    for(i = 0; i < MaxSize; i++)
        visited[i] = 0;
    cout<< "广度优先遍历序列是：";
    MG.BFTraverse(0);//从顶点0出发进行广度优先遍历
    return 0;

//
}

太难了，完全是照着书本来，不然根本不会（捂脸）
磕磕碰碰，各种小错误，完全像新学一样，懵懵懂懂的，什么都不懂。

这篇关于SCNU_数据结构作业_实验5 图的算法与应用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！