邻接矩阵
图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。⼀
个⼀维数组存储图中顶点信息,⼀个⼆维数组(称为邻接矩阵)存储图中
的边或弧的信息。
假设存储下面的一个无向图
定义如下的数据结构
//图的邻接矩阵存储结构
typedef struct Graph{
//顶点表
vector<string> Vexs;
//边表,表示顶点与顶点之间的连接关系
vector<vector<int>> arc;
//存储顶点和边的个数
int Vertexs,Edges;
}Graph;
注:此处参考《大话数据结构》,书中的Vexs和arc的数据结构感觉使用起来不方便,因此改为C++中支持的string ,vector。
创建图
定义完了图的基础数据结构以后则开始创造一个图。
void CreateGraph(Graph *G)
{
cout << "请输入顶点个数和边的个数" <<endl;
cin >> G->Vertexs >> G->Edges;
cout << "请输入顶点信息" << endl;
for (int i = 0; i < G->Vertexs; ++i)
{
string tmp;
cin >> tmp;
G->Vexs.push_back(tmp);
}
//边表初始化
vector<vector<int>> data(G->Vertexs, vector<int>(G->Vertexs, 0));
G->arc = data;
for (int i = 0; i < G->Vertexs; ++i){
for (int j = 0; j < G->Vertexs; ++j){
//因为是对称矩阵
if (i != j)
{
G->arc[i][j] = 1000;
G->arc[j][i] = 1000;
}
}
}
//边表正式录入数据
for (int k = 0; k < G->Edges; ++k){
int i,j;
cout << "请输入边(Vi,Vj)" << endl;
cin >> i >> j;
//(Vi,Vj)是连通的顶点,则acr[i][j]与arc[j][i]都为1
G->arc[i][j] = 1;
G->arc[j][i] = 1;
}
return;
}
此处使用vector 创建二维矩阵的优势就体现出来了,不用给一个设定的MAX值,有时候用不完,浪费空间,有时候又不够用,很麻烦!且顶点的信息现在就可以实现多样化的输入了,比如:V0、V1或者是A、B等等。
emmm ,还写了一个打印图的函数。
//打印连接链表
void PrintGraph(Graph *G)
{
cout << "所建立的矩阵表如以下所示:" << endl;
for (int i = 0; i<G->Vertexs; i++)
{
cout << G->Vexs[i]<<":"; //先输出顶点信息
for (int j = 0; j<G->Vertexs; ++j) //然后就开始遍历输出每个边表所存储的邻接点的下标
{
cout << G->arc[i][j] ;
}
cout << endl;
}
}
创建一个全局的访问数组
bool Visted[100];
深度优先遍历(DFS)
下面开始以邻接矩阵实现图数据结构的深度优先遍历。
//DFS
void DFS(Graph *G, int i)
{
//只要你进来了,就说明你已经访问了
Visted[i] = true;
cout << "当前节点为:" << G->Vexs[i];
for (int j = 0; j < G->Vertexs; ++j){
//arc[i][j]之间要有通路,并且J还没有被访问
if (G->arc[i][j] == 1 && !Visted[j])
DFS(G, j);
}
cout << endl;
}
void DFSTraver(Graph *G)
{
//将访问列表初始化
cout << "DFS遍历顺序为" << endl;
for (int i = 0; i < G->Vertexs; ++i){
Visted[i] = false;
}
for (int i = 0; i < G->Vertexs; ++i){
if (!Visted[i])
DFS(G, i);
}
}
其实就是一个递归,很像二叉树的三种普通遍历方法。
广度优先遍历(BFS)
广度优先遍历很像是二叉树的层序遍历,此处需要用到栈(stack)这个辅助的数据结构,因此使用C++也就会方便很多。
//BFS 特点要使用队列,很像树的层序遍历
void BFSTraver(Graph *G)
{
cout << "BFS遍历顺序为" << endl;
//辅助队列
queue<int> Q;
//同样要初始化访问数组
for (int i = 0; i < G->Vertexs; ++i)
Visted[i] = false;
//开始对每个顶点循环
for (int i = 0; i < G->Vertexs; ++i){
if (!Visted[i]){
Q.push(i);
Visted[i] = true;
cout << "当前节点为:" << G->Vexs[i];
while(!Q.empty()){
i = Q.front();
Q.pop();
for (int j = 0; j < G->Vertexs; ++j){
if (G->arc[i][j] == 1 && !Visted[j]){
Visted[j] = true;
cout << "当前节点为:" << G->Vexs[j];
Q.push(j);
}
}
}
}
}
return;
}
测试一下
emmm ,写完以后就开始测试了。测试的图信息如下所示。
结果。
emmm ,因为顶点之间没有连接的时候用1000表示,(V0,V0)在矩阵中用0表示,(V0,V1)用1表示,所以二维矩阵看着有些乱。
图的邻接矩阵就酱紫吧!!!