题目描述

已知邻接表存储的无向图的部分代码如下，请补充完成深度优先、广度优先遍历算法。
//graphmain.cpp
#include
#include
using namespace std;
//循环队列类
const int QueueSize=100; //循环队列的最大长度
template //定义模板类CirQueue
class CirQueue
{
public:
CirQueue( ); //构造函数，置空队
~ CirQueue( ); //析构函数
void EnQueue(T x); //将元素x入队
T DeQueue( ); //将队头元素出队
T GetQueue( ); //取队头元素（并不删除）
bool Empty( ); //判断队列是否为空
bool Full();
private:
T data[QueueSize]; //存放队列元素的数组
int front, rear; //队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置
};
//功 能：初始化空队列
template
CirQueue::CirQueue( )
{
front=rear=0;
}
// 功 能：销毁队列
template
CirQueue::~CirQueue( )
{
}
//功 能：元素x入队
template
void CirQueue::EnQueue(T x)
{
if (Full()) throw “Overflow”;
rear=(rear+1) % QueueSize; //队尾指针在循环意义下加1
data[rear]=x; //在队尾处插入元素
}
//功 能：队头元素出队，返回值为出队元素
template
T CirQueue::DeQueue( )
{
if (Empty()) throw “Downflow”;
front=(front+1) % QueueSize; //队头指针在循环意义下加1
return data[front]; //读取并返回出队前的队头元素，注意队头指针
}
//指向队头元素的前一个位置
// 功 能：获取队头元素
template
T CirQueue::GetQueue( )
{
int i;
if (Empty()) throw “Downflow”;
i=(front+1) % QueueSize; //注意不要给队头指针赋值
return data[i];
}
// 功 能：判断队列是否为空,若空返回true，否则返回false
template
bool CirQueue::Empty( )
{
return front==rear;
}
//功 能：判断队列是否满，若满返回true，否则false
template
bool CirQueue::Full()
{
return (rear+1)%QueueSize==front;
}
const int MaxSize=20; // 顶点个数的最大值
int visited[MaxSize]; //访问标志数组（0表示未访问，1表示已访问）
//定义边表结点
struct ArcNode
{
int adjvex; //邻接点的序号
ArcNode next; //指向下一个边结点的指针
};
//定义顶点表结点
template
struct VertexNode
{
T vertex; //顶点的名称
ArcNode firstedge; //指向第一个边表结点的头指针
};
//邻接表类
template
class ALGraph
{
public:
ALGraph(T a[ ], int n, int e); //构造函数，初始化一个有n个顶点e条边的图
~ALGraph(); //析构函数，释放邻接表中各边表结点的存储空间
void DispALGraph(); //输出邻接表
int Count( ); //计算连通分量个数，返回值为连通分量的个数（请大家自己测试）
void DFSTraverse(int v); //深度优先遍历图
void BFSTraverse(int v); //深度优先遍历图
private:
VertexNode adjlist[MaxSize]; //存放顶点表的数组
int vertexNum, arcNum; //图的顶点数和边数
};
/
前置条件：图不存在
输 入：无
功 能：图的初始化
输 出：无
后置条件：得到一个无向图
/
template
ALGraph::ALGraph(T a[ ], int n, int e)
{
arcNum = e; //边数
vertexNum=n; //顶点数
int i,j;
for (i=0; i{
adjlist[i].vertex = a[i];
adjlist[i].firstedge = NULL;
}
for (int k=0; k{
cin>>i>>j; //输入边所依附的两个顶点的序号
ArcNode s=new ArcNode;
s->adjvex=j; //生成一个边表结点s
s->next=adjlist[i].firstedge; //将结点s插入到i号表的头结点之后
adjlist[i].firstedge=s;
s=new ArcNode;
s->adjvex=i; //生成一个边表结点s
s->next=adjlist[j].firstedge; //将结点s插入到j号表的头结点之后
adjlist[j].firstedge=s;
}
}
/ 前置条件：图已存在
 输 入：无
功 能：销毁图
 输 出：无
后置条件：释放图所占用的存储空间
/
template
ALGraph::~ALGraph( )
{
for (int i=0; i{
ArcNode p=adjlist[i].firstedge;
while (p!=NULL) //循环删除
{
adjlist[i].firstedge=p->next;
delete p; //释放结点空间
p=adjlist[i].firstedge;
}
}
}
/
前置条件：图已存在
输 入：无
功 能：输出图中所有顶点及边的数据信息
输 出：图中所有顶点及边的数据信息
后置条件：图保持不变
/
template
void ALGraph::DispALGraph( )
{
int i;
ArcNode *p;
cout<<”图的邻接表:\n”;
for(i=0;icout<for(p=adjlist[i].firstedge;p;p=p->next)
cout<adjvex<<” “; //输出i号顶点的邻接点的序号
cout<}
}
template
int ALGraph::Count( )
{
int i,n=0;
for(i=0;ifor(i=0;iif(!visited[i]){
n++;
BFSTraverse(i); //利用深度优先或广度优先遍历算法均可
}
}
return n;
}
//在下面完成深度优先、广度优先遍历算法
int main()
{
string a[]={“A”,”B”,”C”,”D”,”E”,”F”,”G”,”H”,”I”,”J”,”K”,”L”,”M”,”N”}; //顶点信息
int i,n,e;
cin>>n>>e; //输入顶点个数和边个数
ALGraph G(a,n,e);
G.DispALGraph();
for(i=0;ivisited[i]=0;
cout<<”DFS:”;
G.DFSTraverse(0);
cout<for(i=0;ivisited[i]=0;
cout<<”BFS:”;
G.BFSTraverse(0);
// cout<<”\n连通分量个数:”;
// cout<return 0;
}

输入

第一行为顶点个数和边的条数：6 7
第二行为各条边所对应的顶点序号：0 1 0 3 1 2 1 5 2 4 3 5 4 5

输出

因为构造函数中各条边所对应的边表结点采用头插法插入到表头结点之后，因此输入0 1 0 3，0号链表后为3 1序列，其它亦如此。
图的邻接表:
0 A 3 1
1 B 5 2 0
2 C 4 1
3 D 5 0
4 E 5 2
5 F 4 3 1
DFS:A D F E C B
BFS:A D B F C E

样例输入

6 7 0 1 0 3 1 2 1 5 2 4 3 5 4 5

样例输出

Graph adjlist: 0 A 3 1 1 B 5 2 0 2 C 4 1 3 D 5 0 4 E 5 2 5 F 4 3 1 DFS:A D F E C B BFS:A D B F C E

提示

来源

提交

  1. package Q1026;
  2. import java.util.Scanner;
  5. class CirQueue{
  6.     Object[] queueElem;
  7.     int front;
  8.     int rear;
  9.     int QueueSize=5;
  10.     public CirQueue(){
  11.         front = rear = 0;
  12.         queueElem = new Object[QueueSize];
  13.     }
  15.     public void clear(){
  16.         front = rear = 0;
  17.     }
  19.     public boolean isEmpty(){
  20.         return front == rear;
  21.     }
  23.     public int length(){
  24.         return (rear-front+queueElem.length)% queueElem.length;
  25.     }
  27.     public boolean isFull(){
  28.         return (rear+1) % QueueSize ==front;
  29.     }
  31.     public void EnQueue(Object x) throws Exception{
  32.         if((rear+1)%queueElem.length==front){
  33.             throw new Exception(" Overflow");
  34.         }else{
  35.             queueElem[rear] = x;
  36.             rear = (rear+1)%queueElem.length;
  37.         }
  38.     }
  40.     public Object DeQueue() throws Exception {
  41.         if(front==rear){
  42.             throw new Exception("Downflow");
  43.         }else{
  44.             Object t = queueElem[front];
  45.             front = (front+1)%queueElem.length;
  46.             return t;
  47.         }
  48.     }
  50.     public Object GetQueue() throws Exception {
  51.         if(front==rear){
  52.             throw new Exception("Downflow");
  53.         }else{
  54.             Object t = queueElem[front];
  55.             return t;
  56.         }
  57.     }
  59. }
  61. //图的接口
  62. interface IGraph {
  63.     void createGraph();// 创建一个图
  65.     int getVexNum(); // 返回顶点数
  67.     int getArcNum();// 返回边数
  69.     Object getVex(int v) throws Exception;// 返回v表示结点的值， 0 <= v < vexNum
  71.     int locateVex(Object vex);// 给定顶点的值vex，返回其在图中的位置，如果图中不包含此顶点，则返回-1
  73.     int firstAdjVex(int v) throws Exception; // 返回v的第一个邻接点，若v没有邻接点，则返回-1，其中0≤v<vexNum
  75.     int nextAdjVex(int v, int w) throws Exception;// 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1，其中0≤v,
  76.                                                     // w<vexNum
  78. }
  81. class ArcNode {
  82.     public int adjVex;
  84.     public int value;
  86.     public ArcNode nextArc;
  88.     public ArcNode() {
  89.         this(-1, 0, null);
  90.     }
  92.     public ArcNode(int adjVex) {
  93.         this(adjVex, 0, null);
  94.     }
  96.     public ArcNode(int adjVex, int value) {
  97.         this(adjVex, value, null);
  98.     }
  100.     public ArcNode(int adjVex, int value, ArcNode nextArc) {
  101.         this.value = value;
  102.         this.adjVex = adjVex;
  103.         this.nextArc = nextArc;
  104.     }
  106. }
  108. class VNode {
  109.     public Object data;
  111.     public ArcNode firstArc;
  113.     public VNode() {
  114.         this(null, null);
  115.     }
  116.     public VNode(Object data) {
  117.         this(data, null);
  118.     }
  119.     public VNode(Object data, ArcNode firstArc) {
  120.         this.data = data;
  121.         this.firstArc = firstArc;
  122.     }
  125. }
  128. class ALGraph implements IGraph {
  130.     private int vexNum, arcNum;
  132.     private VNode[] vexs;
  134.     private static boolean[] visited;// 访问标志数组
  136.     public ALGraph() {
  137.         this(0, 0, null);
  138.     }
  140.     public ALGraph(int vexNum, int arcNum, VNode[] vexs) {
  141.         this.vexNum = vexNum;
  142.         this.arcNum = arcNum;
  143.         this.vexs = vexs;
  144.     }
  146.     public void createGraph() {
  147.         Scanner sc = new Scanner(System.in);
  148.         vexNum = sc.nextInt();
  149.         arcNum = sc.nextInt();
  150.         vexs = new VNode[vexNum];
  151.         String Node[]={"A","B","C","D","E","F","G","H","I","J","K","L","M","N"}; //顶点信息
  152.         for (int v = 0; v < vexNum; v++)
  153.             vexs[v] = new VNode(Node[v]);
  154.         for (int k = 0; k < arcNum; k++) {
  155.             int v = sc.nextInt();// 弧尾
  156.             int u = sc.nextInt();// 弧头
  157.             int value = 1;
  158.             addArc(v, u, value);
  159.             addArc(u, v, value);
  160.         }
  163.     }
  164.     public void addArc(int v, int u, int value) {
  165.         ArcNode arc = new ArcNode(u, value);
  166.         arc.nextArc=vexs[v].firstArc;
  167.         vexs[v].firstArc=arc;
  168.     }
  170.     public int getVexNum() {
  171.         return vexNum;
  172.     }
  174.     public int getArcNum() {
  175.         return arcNum;
  176.     }
  178.     public int locateVex(Object vex) {
  179.         for (int v = 0; v < vexNum; v++)
  180.             if (vexs[v].data.equals(vex))
  181.                 return v;
  182.         return -1;
  183.     }
  185.     public VNode[] getVexs() {
  186.         return vexs;
  187.     }
  189.     public Object getVex(int v) throws Exception {
  190.         if (v < 0 && v >= vexNum)
  191.             throw new Exception("第" + v + "个顶点不存在!");
  193.         return vexs[v].data;
  194.     }
  196.     public int firstAdjVex(int v) throws Exception {
  197.         if (v < 0 && v >= vexNum)
  198.             throw new Exception("第" + v + "个顶点不存在!");
  200.         VNode vex = vexs[v];
  201.         if (vex.firstArc != null)
  202.             return vex.firstArc.adjVex;
  203.         else
  204.             return -1;
  205.     }
  207.     public int nextAdjVex(int v, int w) throws Exception {
  208.         if (v < 0 && v >= vexNum)
  209.             throw new Exception("第" + v + "个顶点不存在!");
  210.         VNode vex = vexs[v];
  212.         ArcNode arcvw = null;
  213.         for (ArcNode arc = vex.firstArc; arc != null; arc = arc.nextArc)
  214.             if (arc.adjVex == w) {
  215.                 arcvw = arc;
  216.                 break;
  217.             }
  218.         if (arcvw != null && arcvw.nextArc != null)
  219.             return arcvw.nextArc.adjVex;
  220.         else
  221.             return -1;
  222.     }
  224.     public void setArcNum(int arcNum) {
  225.         this.arcNum = arcNum;
  226.     }
  228.     public void setVexNum(int vexNum) {
  229.         this.vexNum = vexNum;
  230.     }
  232.     public void setVexs(VNode[] vexs) {
  233.         this.vexs = vexs;
  234.     }
  236.     public void DFSTraverse() throws Exception {
  237.          visited = new boolean[getVexNum()];
  238.          for (int v = 0; v < getVexNum(); v++)
  239.         // 访问标志数组初始化
  240.         visited[v] = false;
  241.         System.out.print("DFS:");
  242.         for (int v = 0; v < getVexNum(); v++)
  243.               if (!visited[v])// 对尚未访问的顶点调用DFS
  244.             DFS(v);
  245.     }
  247.     private  void DFS(int v) throws Exception {
  248.          visited[v] = true;
  249.           // 访问第v个顶点
  250.          System.out.print(getVex(v).toString() + " "); 
  251.          for (int w = firstAdjVex(v); w >= 0; w = nextAdjVex(v, w))
  252.               if (!visited[w])// 对v的尚未访问的邻接顶点w递归调用DFS
  253.            DFS(w);
  254.     }
  256.     public void BFSTraverse() throws Exception {
  257.          visited = new boolean[getVexNum()];// 访问标志数组
  258.          for (int v = 0; v < getVexNum(); v++)
  259.                // 访问标志数组初始化
  260.               visited[v] = false;
  261.               System.out.print("BFS:");
  262.               for (int v = 0; v < getVexNum(); v++)
  263.         if (!visited[v]) // v尚未访问
  264.             BFS(v);
  265.     }
  267.     private void BFS(int v) throws Exception {
  268.          visited[v] = true;
  269.          System.out.print(getVex(v).toString() + " ");
  270.          CirQueue Q = new CirQueue();// 辅助队列Q
  271.          Q.EnQueue(v);// v入队列
  272.          while (!Q.isEmpty()) {
  273.               int u = (Integer) Q.DeQueue();// 队头元素出队列并赋值给u
  274.               for (int w = firstAdjVex(u); w >= 0; w = nextAdjVex(u, w))
  275.         if (!visited[w]) {// w为u的尚未访问的邻接顶点
  276.             visited[w] = true;
  277.             System.out.print(getVex(w).toString() + " "); 
  278.             Q.EnQueue(w);
  279.         }
  280.            }
  281.     }
  283.     void DispMGraph(){
  285.          int i;
  286.          ArcNode p;
  288.          System.out.println("Graph adjlist:");
  290.             for(i=0;i<vexNum;i++){
  291.                  System.out.print(i + " " +vexs[i].data + " ");
  292.                  p = vexs[i].firstArc;
  293.                  while(p!=null){
  294.                      System.out.print(p.adjVex + " ");
  295.                      p=  p.nextArc;
  296.                  }
  297.                  System.out.println("");
  298.             }
  299.          }
  303. }
  306. public class Main {
  308.     public static void main(String[] args) throws Exception {
  309.         ALGraph a = new ALGraph();
  310.         a.createGraph();
  311.         a.DispMGraph();
  312.         a.DFSTraverse();
  313.         System.out.println("");
  314.         a.BFSTraverse();
  315.     }
  317. }