/**

* C++: 邻接矩阵表示的"无向图(Matrix Undirected Graph)"

*

* @author skywang

* @date 2014/04/19

*/

#include"stdafx.h"

#include <iomanip>

#include <iostream>

#include <vector>

#include"matrix_udg.h"

using namespace std;

/*

* 创建图(自己输入数据)

*/

MatrixUDG::MatrixUDG()

{

char c1, c2;

int i, p1, p2;

// 输入"顶点数"和"边数"

cout << "input vertex number: ";

cin >> mVexNum;

cout << "input edge number: ";

cin >> mEdgNum;

// 1、顶点数量<1

// 2、边数量<1

// 3、无向图，边数量最多=1+……+n-1，共n-1项=(1+n-1)*(n-1)/2；

// 4、无向图，边数量最少=n-1

if (mVexNum < 1 || mEdgNum < 1 || (mEdgNum >(mVexNum * (mVexNum - 1)/2)))

{

cout << "input error: invalid parameters!" << endl;

return;

}

// 初始化"顶点"

for (i = 0; i < mVexNum; i++)

{

cout << "vertex(" << i << "): ";

mVexs[i] = readChar();

}

// 初始化"边"

for (i = 0; i < mEdgNum; i++)

{

// 读取边的起始顶点和结束顶点

cout << "edge(" << i << "): ";

c1 = readChar();

c2 = readChar();

p1 = getPosition(c1);

p2 = getPosition(c2);

if (p1 == -1 || p2 == -1)

{

cout << "input error: invalid edge!" << endl;

return;

}

mMatrix[p1][p2] = 1;

mMatrix[p2][p1] = 1;

}

}

/*

* 创建图(用已提供的矩阵)

*

* 参数说明：

* vexs -- 顶点数组

* vlen -- 顶点数组的长度

* edges -- 边数组

* elen -- 边数组的长度

*/

MatrixUDG::MatrixUDG(char vexs[], int vlen, char edges[][2], int elen)

{

int i, p1, p2;

// 初始化"顶点数"和"边数"

mVexNum = vlen;

mEdgNum = elen;

// 初始化"顶点"

for (i = 0; i < mVexNum; i++)

mVexs[i] = vexs[i];

//初始化矩阵

memset(mMatrix, 0, sizeof(mMatrix));

// 初始化"边"

for (i = 0; i < mEdgNum; i++)

{

// 读取边的起始顶点和结束顶点

p1 = getPosition(edges[i][0]);

p2 = getPosition(edges[i][1]);

mMatrix[p1][p2] = 1;

mMatrix[p2][p1] = 1;

}

}

/*

* 析构函数

*/

MatrixUDG::~MatrixUDG()

{

}

/*

* 返回ch在mMatrix矩阵中的位置

*/

int MatrixUDG::getPosition(char ch)

{

int i;

for (i = 0; i<mVexNum; i++)

if (mVexs[i] == ch)

return i;

return -1;

}

/*

* 读取一个输入字符

*/

char MatrixUDG::readChar()

{

char ch;

do {

cin >> ch;

} while (!((ch >= 'a'&&ch <= 'z') || (ch >= 'A'&&ch <= 'Z')));

return ch;

}

/*

* 返回顶点v的第一个邻接顶点的索引，失败则返回-1

*/

int MatrixUDG::firstVertex(int v)

{

int i;

if (v<0 || v>(mVexNum - 1))

return -1;

for (i = 0; i < mVexNum; i++)

if (mMatrix[v][i] == 1)

return i;

return -1;

}

/*

* 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1

*/

int MatrixUDG::nextVertex(int v, int w)

{

int i;

if (v<0 || v>(mVexNum - 1) || w<0 || w>(mVexNum - 1))

return -1;

for (i = w + 1; i < mVexNum; i++)

if (mMatrix[v][i] == 1)

return i;

return -1;

}

/*

* 深度优先搜索遍历图的递归实现

*/

void MatrixUDG::DFS(int i, int *visited)

{

int w;

visited[i] = 1;

cout << mVexs[i] << " ";

// 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走

for (w = firstVertex(i); w >= 0; w = nextVertex(i, w))

{

if (!visited[w])

DFS(w, visited);

}

}

/*

* 深度优先搜索遍历图

*/

void MatrixUDG::DFS()

{

int i;

int visited[MAX]; // 顶点访问标记

// 初始化所有顶点都没有被访问

for (i = 0; i < mVexNum; i++)

visited[i] = 0;

cout << "DFS: ";

for (i = 0; i < mVexNum; i++)

{

//printf("\n== LOOP(%d)\n", i);

if (!visited[i])

DFS(i, visited);

}

cout << endl;

}

/*

* 广度优先搜索（类似于树的层次遍历）

*/

void MatrixUDG::BFS()

{

int head = 0;

int rear = 0;

int queue[MAX]; // 辅组队列

int visited[MAX]; // 顶点访问标记

int i, j, k;

for (i = 0; i < mVexNum; i++)

visited[i] = 0;

cout << "BFS: ";

for (i = 0; i < mVexNum; i++)

{

if (!visited[i])

{

visited[i] = 1;

cout << mVexs[i] << " ";

queue[rear++] = i; // 入队列

}

while (head != rear)

{

j = queue[head++]; // 出队列

for (k = firstVertex(j); k >= 0; k = nextVertex(j, k)) //k是为访问的邻接顶点

{

if (!visited[k])

{

visited[k] = 1;

cout << mVexs[k] << " ";

queue[rear++] = k;

}

}

}

}

cout << endl;

}

/*

* 打印矩阵队列图

*/

void MatrixUDG::print()

{

int i, j;

cout << "Martix Graph:" << endl;

for (i = 0; i < mVexNum; i++)

{

for (j = 0; j < mVexNum; j++)

cout << mMatrix[i][j] << " ";

cout << endl;

}

}

int matrix_udg_main()

{

char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };

char edges[][2] = {

{ 'A', 'C' },

{ 'A', 'D' },

{ 'A', 'F' },

{ 'B', 'C' },

{ 'C', 'D' },

{ 'E', 'G' },

{ 'F', 'G' } };

int vlen = sizeof(vexs) / sizeof(vexs[0]);

int elen = sizeof(edges) / sizeof(edges[0]);

MatrixUDG* pG;

// 自定义"图"(输入矩阵队列)

//pG = new MatrixUDG();

// 采用已有的"图"

pG = new MatrixUDG(vexs, vlen, edges, elen);

pG->print(); // 打印图

pG->DFS(); // 深度优先遍历

pG->BFS(); // 广度优先遍历

return 0;

}