1.实验题目

1.【功能1】建立一个无向图。

2.【功能2】按深度优先遍历该无向图，输出遍历序列。

3.【功能3】按广度优先遍历该无向图，输出遍历序列。

2.实验要求

1、无向图以邻接矩阵或邻接表作为存储结构

2、主程序测试数据

3.算法思路

1.类的设计

这次实验可以设计出一个邻接表作为图的存储结构。因为题目要求图的边没有权值，所以，我们可以对课本上的邻接表作一些适当简化。在设计图的边类adjlistnetworkarc类时，可以去掉边权域，仅保留顶点域和指针域。在设计图类adjlistdirnetwork时，可以去掉对无穷大的值的定义。定义这两个类模板时，少了权值这一参数，仅保留数据域元素类型这一参数。但是，定义顶点结点adjlistnetwokvex时，无向图与带权有向图在形式上没有区别。

2.输入图

输入图分为3步：输入顶点个数，输入各个顶点的数据域，输入边。

输入顶点的个数后，完成了对图、顶点、边的初始化和构造。

输入边的同时，调用adjlistdirnetwork中添加边的函数，对V1结点添加(V1,V2)的边，对V2结点添加(V2,V1)的边。

可利用#键，提示输入已完成。在输入过程中，适当利用cin语句读取掉不需要的左括号、右括号、逗号等，并将数字按字符读取完成后转换回对应数字。

输入边完成后，可以自行定义一个输出功能，显示各个结点自己的数据域，并显示出与其邻接的所有结点。这一过程封装在adjlistdirnetwork类的函数中。

3.深度优先遍历

对于非连通图，先对每个顶点设置未访问标志，再从每一个未被访问的顶点出发进行深度优先搜索。深度优先搜索时，访问结点v，标记该结点已经被访问。再取邻接表上v的第一个邻接结点w。若顶点w不存在，退回到点v，结束。若顶点w存在且未被访问，则访问该结点。访问v在邻接表上下一个未被访问的结点。

4.广度优先遍历

对于非连通图，先对每个顶点设置未访问标志，再从每一个未被访问的顶点开始进行广度优先搜索。广度优先搜索时，先访问结点v，标记v已经被访问。将v入队列。当队列为空时结束。否则，队头顶点出队列v，取顶点v的第一个邻接顶点w，若w不存在，则将队头顶点出队列v。否则，若顶点w未被访问，则访问顶点w，标记w已被访问，将w入队列。否则，访问顶点v在邻接表上下一个未被访问的结点。

4.输出演示

1.先输入结点个数。

2.在结点个数输入完成后，根据提示可输入各个结点的数据域

3.在将各个结点数据域输入后，可以(a,b)的形式输入弧，将顶点a与顶点b连结在一起。

4.以#表示输入终止。此时，我们可以将这张图以邻接表的形式存储，看到其结点与结点之间的逻辑结构。

5.我们可以看到图的深度优先遍历序列与广度优先遍历序列

5.源代码

adjlistdirnetwork.h

#pragma once
#define DEFAULT_SIZE 100
#define DEFAULT_INFI 32767
#define status int
#define UNVISITED 0
#define VISITED 1
#include"adjlistnetworkvex.h"
#include"adjlistnetworkarc.h"
#include<iostream>
#include"seqqueue.h"
#include<stdio.h>
using namespace std;
template<class ElemType>
class adjlistdirnetwork
{
protected:
  mutable status* tag;
  int vexnum, vexmaxnum, arcnum;
  adjlistnetworkvex<ElemType>* vextable;
public:
/*  adjlistdirnetwork(ElemType es[], int vertexNum, int vertexMaxNum = DEFAULT_SIZE) {
    if (vertexMaxNum < 0)
      cerr<<"允许的顶点的最大数目不能为负！";
    if (vertexMaxNum < vertexNum)
      cerr<<"顶点数目不能大于允许的顶点的最大数目！";
    vexnum = vertexNum;
    vexmaxnum = vertexMaxNum;
    arcnum = 0;
    tag = new status[vexmaxnum];
    vextable = new adjlistnetworkvex<ElemType>[vexmaxnum];
    for (int v = 0; v < vexnum; v++) {
      tag[v] = UNVISITED;
      vextable[v].data = es[v];
      vextable[v].firstarc = NULL;
    }
  }
  */
  ~adjlistdirnetwork() {//析构函数
    delete [] vextable;
    delete []tag;
  }
  adjlistdirnetwork(int vertexMaxNum=DEFAULT_SIZE) {//默认构造函数
    if (vertexMaxNum < 0)//抛出异常
      cerr<<"允许顶点的最大数目不能为负！";
    vexnum = 0;
    vexmaxnum = vertexMaxNum;
    arcnum = 0;
    tag = new status[vexmaxnum];
    vextable = new adjlistnetworkvex<ElemType>[vexmaxnum];//构造顶点
    for (int v = 0; v < vexmaxnum; v++) 
      tag[v] = UNVISITED;//将是否访问的标志初始化
  }
  void setvexnum(int val) {
    vexnum = val;
  }
  void insertarc(int v1, int v2) {
    if (v1 < 0 || v1 >= vexnum)
      cerr << "v1不合法！";
    if (v2 < 0 || v2 >= vexnum)
      cerr << "v2不合法！";
    if (v1 == v2)
      cerr << "v1不能等于v2！";//判断不合法情况
    adjlistnetworkarc* p, * q;
    p = vextable[v1].getfirstarc();
    vextable[v1].setfirstarc(v2,p);//v1顶点的邻接表里连一条(v1,v2)的边
    arcnum++;
    q = vextable[v2].getfirstarc();
    vextable[v2].setfirstarc(v1,q);//v2顶点的邻接表里连一条(v2,v1)的边
    arcnum++;
  }
  adjlistnetworkvex<ElemType>* getvex(int i) {
    return &vextable[i];//因为类被封装了找到这个图对应的顶点表
  }
  void show() {//将图以邻接表的形式展示
    adjlistnetworkarc* p;
    for (int i = 0; i < vexnum; i++) {
      cout << vextable[i].getdata();
      p = vextable[i].getfirstarc();
      while (p != NULL) {
        cout<<"("<<vextable[i].getdata()<<"," <<vextable[p->getadjvex()].getdata()<<")";
        p = p->getnextarc();
      }
      cout << endl;
    }
  }
  void settag(int v, status _tag) {
    tag[v] = _tag;//改变v顶点的标志
  }
  void DFS(int v) {//深度优先搜索
    ElemType e;
    settag(v, VISITED);
    cout<<vextable[v].getdata();
    adjlistnetworkarc* w=vextable[v].getfirstarc();
    while(w!=NULL){
      if (tag[w->getadjvex()] == UNVISITED) 
        DFS(w->getadjvex());
      w = w->getnextarc();
    }
  }
  void DFSTraverse() {//完整的深度优先遍历过程
    int v;
    for (v = 0; v < vexnum; v++)
      settag(v, UNVISITED);
    for (v = 0; v < vexnum; v++)
      if (tag[v] == UNVISITED)
        DFS(v);
  }
  void resettag() {//在进行另一次遍历之前，先把是否访问的标记重置
    for (int i = 0; i < vexnum; i++)
      tag[i] = UNVISITED;
  }
  void BFS(int v) {//广度优先搜索
    seqqueue<int> q;
    int u;
    adjlistnetworkarc* w=NULL;
    settag(v, VISITED);
    cout << vextable[v].getdata();
    q.enqueue(v);
    while (!q.isempty()) {
      q.delqueue(u);
      w = vextable[u].getfirstarc();
      while (w != NULL) {
        if (tag[w->getadjvex()] == UNVISITED) {
          cout << vextable[w->getadjvex()].getdata();
          settag(w->getadjvex(), VISITED);
          q.enqueue(w->getadjvex());
        }
        w = w->getnextarc();
      }
    }
  }
  void BFSTraverse() {//完整的广度优先遍历
    int v;
    for (v = 0; v < vexnum; v++)
      settag(v, UNVISITED);
    for (v = 0; v < vexnum; v++)
      if (tag[v] == UNVISITED)
        BFS(v);
  }
};

adjlistnetworkarc.h

#pragma once
#include"Windows.h"
struct adjlistnetworkarc {
protected:
  int adjvex;
  adjlistnetworkarc* nextarc;
public:
  int getadjvex() {
    return adjvex;
  }
  adjlistnetworkarc* getnextarc() {
    return nextarc;
  }
  void setnextarc(adjlistnetworkarc* _nextarc) {
    nextarc = _nextarc;
  }
  //因为边类被封装了，所以要写getter/setter
  adjlistnetworkarc() {//默认的无参构造函数
    adjvex = -1;
    nextarc = NULL;
  }
  adjlistnetworkarc(int v, adjlistnetworkarc* next = NULL) {
    adjvex = v;//边的一段指向顶点v
    nextarc = next;
  }
};

adjlistnetworkvex.h

#pragma once
#define DEFAULT_SIZE 100
#define status int
#include"adjlistnetworkarc.h"
#include<iostream>
using namespace std;
template<typename ElemType>
class adjlistnetworkvex
{
protected:
  ElemType data;
  adjlistnetworkarc* firstarc;
public:
  adjlistnetworkvex() {
    firstarc = NULL;//默认的无参构造函数
  }
/*  ~adjlistnetworkvex() {
    if (firstarc != NULL) {
      adjlistnetworkarc* p = firstarc;
      while (p ->getnextarc()!= NULL) {
        firstarc->setnextarc(p->getnextarc());
        delete p;
        p = firstarc;
      }
    }
  }*/
  adjlistnetworkvex(ElemType val, adjlistnetworkarc* adj=NULL) {//构造函数
    data = val;
    firstarc = adj;
  }
  void setfirstarc(int v, adjlistnetworkarc* next = NULL) {
    firstarc = new adjlistnetworkarc(v, next);
  }
  void setdata(ElemType val) {
    data = val;
  }
  adjlistnetworkarc* getfirstarc() {
    return firstarc;
  }
  ElemType getdata() {
    return data;
  }
  //因为类被封装了，所以要写getter/setter
};

sequeue.h

#pragma once
#define DEFAULT_SIZE 100
#define OVER_FLOW 0
#define SUCCESS 1
#define UNDER_FLOW 0
#define status int
template<class ElemType>
class seqqueue {
protected:
  int front, rear;
  int maxSize;
  ElemType* elems;
public:
  seqqueue(int size = DEFAULT_SIZE) {
    maxSize = size;
    if (elems != NULL) delete []elems;
    elems = new ElemType[maxSize];
    rear = front = 0;
  }
  virtual ~seqqueue() {
    delete[]elems;
  }
  bool isempty() {
    return rear == front;
  }
  status enqueue(const ElemType e) {
    if ((rear + 1) % maxSize == front)
      return OVER_FLOW;
    else {
      elems[rear] = e;
      rear = (rear + 1) % maxSize;
      return SUCCESS;
    }
  }
  status delqueue(ElemType& e) {
    if (!isempty()) {
      e = elems[front];
      front = (front + 1) % maxSize;
      return SUCCESS;
    }
    else
      return UNDER_FLOW;
  }
  status gethead(ElemType& e) const {
    if (!isempty()) {
      e = elems[front];
      return SUCCESS;
    }
    else
      return UNDER_FLOW;
  }
};

main.cpp

#include<iostream>
#include<cstring>
#include<stdio.h>
#include"adjlistdirnetwork.h"
#define DEFAULT_SIZE 100
using namespace std;
int main() {
  adjlistdirnetwork<string> adj(DEFAULT_SIZE);
  cout << "请输入结点个数:";
  int vexcount;
  int v1, v2;
  string vexname;
  char ch=' ';
  cin >> vexcount;
  adj.setvexnum(vexcount);
  for (int i = 0; i < vexcount; i++) {
    printf_s("\n请输入第%d个结点的数据域\n", i+1);
    cin >> vexname;
    adj.getvex(i)->setdata(vexname);
  }
  cout << "请输入弧(a,b),以#表示输入终止" << endl;
  cin >> ch;//读取左括号(
  while (ch != '#') {
    cin >> ch;//以字符的形式读取顶点结点
    v1 = int(ch - '0')-1;//将字符转换成数字。
    //因为人从1开始数数，电脑从0开始数数，所以-1
    cin >> ch;//读取逗号,
    cin >> ch;//以字符的形式读取另一个顶点结点
    v2 = int(ch - '0')-1;
    cin >> ch;//读取右括号)
    cout << "请输入弧(a,b),以#表示输入终止" << endl;
    cin >> ch;//读取下一个左括号(或终止符号#
    adj.insertarc(v1, v2);//插入从v1到v2的边和从v2到v1的边
  }
  cout <<  "\n输出该图：\n";
  adj.show();
  cout << "\n深度优先遍历序列为：";
  adj.DFSTraverse();
  cout << "\n广度优先遍历序列为：";
  adj.BFSTraverse();
  cout << "\n运行完成";
}

数据结构/数据结构与算法实验三图的相关算法实现

1.实验题目

2.实验要求

3.算法思路

1.类的设计

2.输入图

3.深度优先遍历

4.广度优先遍历

4.输出演示

5.源代码

adjlistdirnetwork.h

adjlistnetworkarc.h

adjlistnetworkvex.h

sequeue.h

main.cpp

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构/数据结构与算法实验三 图的相关算法实现

1.实验题目

2.实验要求

3.算法思路

1.类的设计

2.输入图

3.深度优先遍历

4.广度优先遍历

4.输出演示

5.源代码

adjlistdirnetwork.h

adjlistnetworkarc.h

adjlistnetworkvex.h

sequeue.h

main.cpp

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构/数据结构与算法实验三图的相关算法实现