#include<iostream>
#include<string.h>
#include"queue.cpp"
#define GElemType char
#define MAX 10
#define TRUE 1
#define ERROR 0
#define IsLetter(a) (((a)>='a')&&((a)<='z')||((a)>='A')&&((a)<='Z'))
#define Length(a) (sizeof(a)/sizeof(a[0]))
using namespace std;
class Graph
{
protected:
GElemType vexs[MAX]; //顶点集合
int vexnum; //顶点总数
int edgenum; //边总数
int matrix[MAX][MAX]; //邻接矩阵
int visit[7];
public:
Graph();
int get_position(GElemType elem);
GElemType read_elem();
void Init_example_graph();
int DFSTraverse(int v);
void DFS();
void BFS();
void printG();
};
Graph::Graph()
{
Init_example_graph();
memset(visit,0,sizeof(visit));
}
int Graph::get_position(GElemType elem)
{
for(int i=0;i<vexnum;i++)
if(vexs[i]==elem)
return i;
return -1;
}
GElemType Graph::read_elem()
{
GElemType elem;
do
{
elem = getchar();
}while(!IsLetter(elem));
return elem;
}
void Graph::Init_example_graph()
{
GElemType vex[] = {'A','B','C','D','E','F','G'};
GElemType edge[][2] = {
{'A', 'C'},
{'A', 'D'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'F', 'G'}};
int vlen = Length(vex);
int elen = Length(edge);
int i, pos1, pos2;
vexnum = vlen;
edgenum = elen;
for(i=0;i<vexnum;i++)
vexs[i] = vex[i];
memset(matrix, 0, sizeof(matrix));
for(int i=0;i<vexnum;i++)
{
int pos1 = get_position(edge[i][0]);
int pos2 = get_position(edge[i][1]);
matrix[pos1][pos2] = 1;
matrix[pos2][pos1] = 1;
}
}
int Graph::DFSTraverse(int v)
{
visit[v] = 1;
for(int row=0;row<7;row++)
{
if(visit[row]==0&&matrix[v][row]==1)
{
DFSTraverse(row);
}
}
}
void Graph::DFS()
{
memset(visit,0,sizeof(visit));
cout<<"深度优先遍历前：";
cout<<"visit:";
for(int i=0;i<7;i++)
cout<<visit[i]<<" ";
cout<<endl;
for(int i=0;i<7;i++)
if(visit[i]==0)
DFSTraverse(i);
cout<<"深度优先遍历后：";
cout<<"visit:";
for(int i=0;i<7;i++)
cout<<visit[i]<<" ";
cout<<endl;
}
void Graph::BFS()
{
memset(visit,0,sizeof(visit));
cout<<"广度优先遍历前：";
cout<<"visit:";
for(int i=0;i<7;i++)
cout<<visit[i]<<" ";
queue q;
int line=0;
cout<<endl<<"广度优先遍历后："<<"visit:";
do
{
q.Pop_queue();
for(int i=0;i<vexnum;i++)
{
if(matrix[line][i]==1)
{
matrix[line][i] = 2;
matrix[i][line] = 2;
visit[line] = 1;
visit[i] = 1;
q.Push_queue(i);
}
}
line = q.getfront();
}while(!q.ifEmpty());
for(int i=0;i<7;i++)
cout<<visit[i]<<" ";
}
void Graph::printG()
{
for(int i=0;i<vexnum;i++)
{
for(int j=0;j<vexnum;j++)
cout<<matrix[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
int main()
{
Graph G;
G.printG();
G.DFS();
G.BFS();
}
