题目描述

利用邻接矩阵存储结构，完成深度优先遍历和广度优先遍历算法。已知部分代码如下（勿改动），只需完成深度遍历DFSTraverse和广度遍历BFSTraverse即可。
#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;
}
//Class MGraph
const int MaxSize=20; //图中最多顶点个数
int visited[MaxSize]; //访问标志数组（0表示未访问，1表示已访问）
template
class MGraph
{
public:
MGraph(T a[],int n,int e); //构造函数，初始化具有n个顶点,e条边的图
void DispMGraph(); //输出图中顶点值和矩阵值

void DFSTraverse(int v); // 从v顶点出发深度优先遍历图（一个连通子图）
void BFSTraverse(int v); // 从v顶点出发广度优先遍历图（一个连通子图）
private:
T vertex[MaxSize]; //存放图中顶点信息的数组
int arc[MaxSize][MaxSize]; //存放图中顶点关系（边）的数组
int vertexNum,arcNum; //图的顶点数和边数
};
//构造一个邻接矩阵存储的无向图
template
MGraph::MGraph(T a[], int n, int e)
{
vertexNum=n; //顶点数
arcNum=e; //边数
int i,j,k;
for (i=0; ivertex[i]=a[i]; //顶点值
for (i=0; ifor (j=0; jarc[i][j]=0;
for (k=0; k{
cin>>i>>j; //输入各条边依附的两个顶点的序号
arc[i][j]=1; //置有边标志
arc[j][i]=1;
}
}
//输出图中所有顶点信息，和边信息
template
void MGraph::DispMGraph( )
{
int i,j;
cout<<” “;
for(i=0;icout<cout<for(i=0;i{
cout<for(j=0;jcout<cout<}
}
//在此处实现深度优先遍历算法

//在此处实现广度优先遍历算法

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; //输入顶点个数和边个数
MGraph G(a,n,e);
G.DispMGraph();
for(i=0;ivisited[i]=0;
cout<<”DFS:”;
G.DFSTraverse(0);
cout<for(i=0;ivisited[i]=0;
cout<<”BFS:”;
G.BFSTraverse(0);
return 0;
}

输入

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

输出

样例输入

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

样例输出

A B C D E F A 0 1 0 1 0 0 B 1 0 1 0 0 1 C 0 1 0 0 1 0 D 1 0 0 0 0 1 E 0 0 1 0 0 1 F 0 1 0 1 1 0 DFS:A B C E F D BFS:A B D C F E

提示

来源

提交

  1. import java.util.Scanner;
  3. class Node{
  4.     Object data;
  5.     Node next;
  7.     public Node() {
  9.     }
  11.     public Node(Object data) {
  12.         this.data = data;
  13.         this.next = null;
  14.     }
  16.     public Node(Object data, Node next) {
  17.         this.data = data;
  18.         this.next = next;
  19.     }
  21.     public Object getData() {
  22.         return data;
  23.     }
  24.     public void setData(Object data) {
  25.         this.data = data;
  26.     }
  27.     public Node getNext() {
  28.         return next;
  29.     }
  30.     public void setNext(Node next) {
  31.         this.next = next;
  32.     }
  34. }
  36. class LinkQueue{
  37.     Node front;
  38.     Node rear;
  40.     public LinkQueue(){
  41.         rear = front = null;
  42.     }
  45.     void EnQueue(Object data){
  46.         Node p =new Node(data);
  47.         if(front != null){
  48.             rear.next = p;
  49.             rear = p;
  50.         }else{
  51.             front = rear = p;
  52.         }
  53.     }
  55.     Object DeQueue() throws Exception{
  56.         if(front != null){
  57.             Node p = front;
  58.             front = front.next;
  59.             if(p==rear){
  60.                 rear = null;
  61.             }
  62.             return p.data;
  63.         }else{
  64.             throw new Exception("Downflow");
  65.         }
  67.     }
  69.     Object GetQueue() throws Exception{
  70.         if(front != null){
  71.             return front.data;
  72.         }else{
  73.             throw new Exception("Downflow");
  74.         }
  76.     }
  78.     boolean isEmpty(){
  79.         return front == null;
  80.     }
  82.     public void offer(Object o) {
  83.         Node p = new Node(o);
  84.         if (front != null) {
  85.             rear.next=p;
  86.             rear = p;
  87.         } else
  89.             front = rear = p;
  90.     }
  92.     public Object peek() {
  93.         if (front != null)
  94.             return front.data;
  95.         else
  96.             return null;
  97.     }
  99.     public Object poll() {
  100.         if (front != null) {
  101.             Node p = front;
  102.             front = front.next;
  103.             if (p==rear)
  104.                 rear=null;
  105.             return p.data;
  106.         } else
  107.             return null;
  108.     }
  111. }
  114. //图的接口
  115. interface IGraph {
  116.     void createGraph();// 创建一个图
  118.     int getVexNum(); // 返回顶点数
  120.     int getArcNum();// 返回边数
  122.     Object getVex(int v) throws Exception;// 返回v表示结点的值， 0 <= v < vexNum
  124.     int locateVex(Object vex);// 给定顶点的值vex，返回其在图中的位置，如果图中不包含此顶点，则返回-1
  126.     int firstAdjVex(int v) throws Exception; // 返回v的第一个邻接点，若v没有邻接点，则返回-1，其中0≤v<vexNum
  128.     int nextAdjVex(int v, int w) throws Exception;// 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1，其中0≤v,
  129.     // w<vexNum
  131. }
  133. // 图的实现
  134. class MGraph implements IGraph {
  135.     public final static int INFINITY = Integer.MAX_VALUE;
  137.     private int vexNum, arcNum;// 图的当前顶点数和边数
  139.     private Object[] vexs;;// 顶点
  141.     private int[][] arcs;;// 邻接矩阵
  143.     private static boolean[] visited;// 访问标志数组
  145.     public MGraph() {
  146.         this(0, 0, null, null);
  147.     }
  149.     public MGraph(int vexNum, int arcNum, Object[] vexs, int[][] arcs) {
  150.         this.vexNum = vexNum;
  151.         this.arcNum = arcNum;
  152.         this.vexs = vexs;
  153.         this.arcs = arcs;
  154.     }
  156.     public void createGraph() {
  157.         Scanner sc = new Scanner(System.in);
  159. //        System.out.println("请分别输入图的顶点数、图的边数:");
  160.         vexNum = sc.nextInt();
  161.         arcNum = sc.nextInt();
  162.         vexs = new Object[vexNum];
  163.         String _vexs[]={"A","B","C","D","E","F","G","H","I","J","K","L","M","N"}; //顶点信息
  164.         this.vexs = _vexs;
  165. //        System.out.println("请分别输入图的各个顶点:");
  166. //        for (int v = 0; v < vexNum; v++)
  167. //            // 构造顶点向量
  168. //            vexs[v] = _vexs[v];
  169.         arcs = new int[vexNum][vexNum];
  171.         for (int v = 0; v < vexNum; v++)
  172.             // 初始化邻接矩阵
  173.             for (int u = 0; u < vexNum; u++)
  174.                 arcs[v][u] = 0;
  176. //        System.out.println("请输入各个边的顶点:");
  178.         for (int k = 0; k < arcNum; k++) {
  179.             int v = sc.nextInt();
  180.             int u = sc.nextInt();
  181.             arcs[v][u] = arcs[u][v] = 1;
  182.         }
  184.     }
  186.     void DispMGraph(){
  187.         int i,j;
  188.         System.out.print("  ");
  189.         for(i=0;i<vexNum;i++)
  190.             System.out.print(vexs[i]+" ");
  191.         System.out.println();
  192.         for(i=0;i<vexNum;i++)
  193.         {
  194.             System.out.print(vexs[i]+" ");
  195.             for(j=0;j<vexNum;j++)
  196.                 System.out.print(arcs[i][j]+" ");
  197.             System.out.println();
  198.         }
  199.     }
  201.     public int getVexNum() {
  202.         return vexNum;
  203.     }
  205.     public int getArcNum() {
  206.         return arcNum;
  207.     }
  209.     public int locateVex(Object vex) {
  210.         for (int v = 0; v < vexNum; v++)
  211.             if (vexs[v].equals(vex))
  212.                 return v;
  213.         return -1;
  214.     }
  216.     public Object getVex(int v) throws Exception {
  217.         if (v < 0 && v >= vexNum)
  218.             throw new Exception("第" + v + "个顶点不存在!");
  219.         return vexs[v];
  220.     }
  222.     public int firstAdjVex(int v) throws Exception {
  223.         if (v < 0 && v >= vexNum)
  224.             throw new Exception("第" + v + "个顶点不存在!");
  226.         for (int j = 0; j < vexNum; j++)
  227.             if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
  228.                 return j;
  230.         return -1;
  231.     }
  233.     public int nextAdjVex(int v, int w) throws Exception {
  234.         if (v < 0 && v >= vexNum)
  235.             throw new Exception("第" + v + "个顶点不存在!");
  237.         for (int j = w + 1; j < vexNum; j++)
  238.             if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
  239.                 return j;
  241.         return -1;
  242.     }
  244.     public int[][] getArcs() {
  245.         return arcs;
  246.     }
  248.     public Object[] getVexs() {
  249.         return vexs;
  250.     }
  252.     public void setArcNum(int arcNum) {
  253.         this.arcNum = arcNum;
  254.     }
  256.     public void setArcs(int[][] arcs) {
  257.         this.arcs = arcs;
  258.     }
  260.     public void setVexNum(int vexNum) {
  261.         this.vexNum = vexNum;
  262.     }
  264.     public void setVexs(Object[] vexs) {
  265.         this.vexs = vexs;
  266.     }
  268.     // 对图G做深度优先遍历
  269.     public void DFSTraverse() throws Exception {
  270.         System.out.print("DFS:");
  271.         visited = new boolean[getVexNum()];
  272.         for (int v = 0; v < getVexNum(); v++)
  273.             // 访问标志数组初始化
  274.             visited[v] = false;
  275.         for (int v = 0; v < getVexNum(); v++)
  276.             if (!visited[v])// 对尚未访问的顶点调用DFS
  277.                 DFS(v);
  278.     }
  280.     // 从第v个顶点出发递归地深度优先遍历图G
  281.     public void DFS(int v) throws Exception {
  282.         visited[v] = true;
  283.         System.out.print(getVex(v).toString() + " ");// 访问第v个顶点
  284.         for (int w = firstAdjVex(v); w >= 0; w = nextAdjVex(v, w))
  285.             if (!visited[w])// 对v的尚未访问的邻接顶点w递归调用DFS
  286.                 DFS(w);
  287.     }
  289.     // 对图G做广度优先遍历
  290.     public void BFSTraverse() throws Exception {
  291.         System.out.print("BFS:");
  292.         visited = new boolean[getVexNum()];// 访问标志数组
  293.         for (int v = 0; v < getVexNum(); v++)
  294.             // 访问标志数组初始化
  295.             visited[v] = false;
  296.         for (int v = 0; v < getVexNum(); v++)
  297.             if (!visited[v]) // v尚未访问
  298.                 BFS(v);
  299.     }
  301.     private void BFS(int v) throws Exception {
  302.         visited[v] = true;
  303.         System.out.print(getVex(v).toString() + " ");
  304.         LinkQueue Q = new LinkQueue();// 辅助队列Q
  305.         Q.offer(v);// v入队列
  306.         while (!Q.isEmpty()) {
  307.             int u = (Integer) Q.poll();// 队头元素出队列并赋值给u
  308.             for (int w = firstAdjVex(u); w >= 0; w = nextAdjVex(u, w))
  309.                 if (!visited[w]) {// w为u的尚未访问的邻接顶点
  310.                     visited[w] = true;
  311.                     System.out.print(getVex(w).toString() + " ");
  312.                     Q.offer(w);
  313.                 }
  314.         }
  315.     }
  317. }
  319. public class Main {
  321.     public static void main(String[] args) throws Exception {
  322.         MGraph m = new MGraph();
  323.         m.createGraph();
  324.         m.DispMGraph();
  325.         m.DFSTraverse();
  326.         System.out.println("");
  327.         m.BFSTraverse();
  328.     }
  330. }