邻接矩阵 深度优先遍历 与广度优先

/*
图的存储结构  邻接矩阵
用一个一维数组 存放图中所有的顶点信息
用一个二维数组 存放边的信息  有向图称为弧 无向图称为边
*/
#include <iostream>
#include <vector>
#include <string>
#include <deque>


using namespace std;


#define MAXSIZE 32
#define INVAILDVALUE -1
typedef int Node;
//点和边集
struct Graph
{
public:
Graph()
{
nVert = 0;
Vertex.clear();
nEdge = 0;
isDirection = false;
isWeight = false;
edgeInfo = NULL;
}


bool Init(bool bDirection = false);


void print();


void depth();


void depthSearch(int index,bool *visit);


void Breadth();


void BreadthSearch(int index ,bool *visit);
public:
//顶点数
int nVert;
vector<string> Vertex;
//边
int nEdge;
int ** edgeInfo;


//是否有向
bool isDirection;


//是否带权
bool isWeight;

};


bool Graph::Init(bool bDirection)
{
cout << "请输入顶点数" << endl;
cin >> nVert;
getchar();
if (nVert <= 0 || nVert >= MAXSIZE) return false;
string s;
char test[256];
cout << "请输入顶点信息" << endl;
for (int  i = 0; i < nVert; i++)
{
if (getline(cin, s))
{
Vertex.push_back(s);
}
else
{
sprintf_s(test, "%d", i + 1);
Vertex.push_back(test);
}
}


cout << "请输入边数" << endl;


cin >> nEdge;
//n*(n-1)/2  顶点与边的关系
if (nEdge <= 0 || nEdge >= MAXSIZE || nEdge > nVert*(nVert-1)/2 ) return false;


isDirection = bDirection;


edgeInfo = new int*[nVert];
for (int i = 0; i < nVert; i++)
{
edgeInfo[i] = new int[nVert];
memset(edgeInfo[i], INVAILDVALUE, sizeof(int)*nVert);
}


for (int i = 0; i < nEdge; i++)
{
int Horizontal, Longitudinal,n;
cin >> Horizontal >> Longitudinal>>n;
edgeInfo[Horizontal][Longitudinal] = n;
if (!isDirection)
edgeInfo[Longitudinal][Horizontal] = n;
}
return true;
}


void Graph::print()
{
if (nVert <= 0) return;
for (int i = 0; i < nVert; i++)
{
for (int  j = 0; j < nVert; j++)
{
cout << edgeInfo[i][j] << " ";
}
cout << endl;
}
}


//深度优先遍历
void Graph::depth()
{
cout << "深度优先遍历开始" << endl;
bool visit[MAXSIZE];
memset(visit, true, sizeof(visit));
for (int i = 0; i < nVert; i++)
{
visit[i] = false;
}


for (int i = 0; i < nVert; i++)
{
depthSearch(i, visit);
}
}


void Graph::depthSearch(int index, bool *visit)
{
if (visit[index] )
{
return;
}
cout << "访问" << Vertex[index] << endl;
visit[index] = true;
for (int i = 0; i < nVert; i++)
{
if (!visit[i] && edgeInfo[index][i] != INVAILDVALUE)
{
depthSearch(i, visit);
}
}
}


void Graph::Breadth()
{
cout << "广度优先遍历开始" << endl;
bool visit[MAXSIZE];
memset(visit, true, sizeof(visit));
memset(visit, false, nVert*sizeof(bool));


for (int i = 0; i < nVert; i++)
{
BreadthSearch(i, visit);
}
}


deque<int> tDeque;
void Graph::BreadthSearch(int index, bool *visit)
{
if (visit[index])
{
return;
}
cout << "visit " << Vertex[index] << endl;
visit[index] = true;
for (int i = index + 1; i < nVert; i++)
{
if (!visit[i] && edgeInfo[index][i] != INVAILDVALUE)
{
tDeque.push_back(i);
}
}
while (tDeque.size() > 0)
{
int t = tDeque.front();
tDeque.pop_front();
BreadthSearch(t, visit);
}
}


int main()
{
while (true)
{
Graph t;
if (t.Init())
{
//t.print();
t.depth();
t.Breadth();
}
}
return 0;
}