图的邻接矩阵表示法和图的遍历

图有邻接矩阵表示法，邻接表表示法等方法。邻接矩阵适合线路比较多的图，邻接表适合线路相对来说比较少的图。我们遍历的图如下图所示：
我们使用邻接矩阵表示图。建立图的类：
class Graph
{
public:
Graph(int n = 10)//构造函数中完成对类的各种数据的初始化。
{
this->vertexNum = n;
this->vertexMatrix = new int *[this->vertexNum];
for (int i = 0; i < this->vertexNum; i++)
{
this->vertexMatrix[i] = new int[this->vertexNum];
}
this->visit = new int[this->vertexNum];
for (int i = 0; i < this->vertexNum; i++)
{
this->visit[i] = 0;
for (int j = 0; j < this->vertexNum; j++)
{
if (i == j)
this->vertexMatrix[i][j] = 0;
else
this->vertexMatrix[i][j] = MAX_VAL;
}
}
}
bool addEdge(int x, int y, int val)//插入边，并判断边的顶点是否符合要求
{
if (x < 0 || x >= this->vertexNum || y < 0 || y >= this->vertexNum)
{
return false;
}
this->vertexMatrix[x][y] = val;
this->vertexMatrix[y][x] = val;
return true;
}
void displayMatrix()//打印邻接矩阵
{
for (int i = 0; i < this->vertexNum; i++)
{
for (int j = 0; j < this->vertexNum; j++)
{
if (this->vertexMatrix[i][j] == 900)
{
cout << “inf” << " ";
}
else
{
cout << this->vertexMatrix[i][j] << " ";
}
}
cout << endl;
}
}
void DFS(int v)//深度优先遍历
{
cout << v << " ";
this->visit[v] = 1;
for (int i = 0; i < this->vertexNum; i++)
{
if (this->visit[i] == 0 && this->vertexMatrix[v][i] != MAX_VAL)
{
DFS(i);
}
}
}
void BFS(int v)
{
queue gq;
gq.push(v);
while (!gq.empty())
{
int v1 = gq.front();
gq.pop();
if (this->visit[v1] == 0)//一定要加这个判断，否则一个同层次的节点会把一个节点写到队列两次，导致打印两次。产生错误。
{
this->visit[v1] = 1;
cout << v1 << " ";
}
for (int i = 0; i < this->vertexNum; i++)
{
if (this->visit[i] == 0 && this->vertexMatrix[v1][i]!=MAX_VAL)
{
gq.push(i);
}
}
}
}
private:
int **vertexMatrix;//类的邻接矩阵，用二维数组表示。
int vertexNum;//顶点个数
int *visit;//表明该顶点是否被访问过
};
int main()
{
Graph *g = new Graph(7);
g->addEdge(1, 2, 4);//添加各个图形的边
g->addEdge(1, 4, 6);
g->addEdge(2, 4, 1);
g->addEdge(2, 5, 4);
g->addEdge(3, 4, 3);
g->addEdge(3, 5, 7);
g->addEdge(4, 5, 2);
g->addEdge(4, 6, 5);
g->addEdge(5, 0, 4);
g->addEdge(6, 0, 6);
g->displayMatrix();
g->BFS(1);
system(“pause”);
return 0;
}
执行结果：

图的深度遍历主要应用在求解一个这样的问题，比如入口到出口存在多条路径，求出所有路径。
图的广度遍历主要应用在比如入口到出口存在多天路径，求出最短路径。

图的邻接矩阵表示法和图的遍历

相关推荐