图:邻接矩阵表示法创建无向图并深度优先搜索遍历
无向图样式:
邻接矩阵法类似于用数组储存,一个一维数组储存顶点信息,还有一个二维数组储存邻接矩阵
用邻接矩阵进行无向图的创建过程:
一,输入总顶点数和边数(几个点,几条边)
eg:如图所示即为8点,9边。
二,依次输入点的信息存入顶点表中(每个点一个名字)
eg:如图即可以写为ABCDEFGH。
三,初始化邻接矩阵,将每个权值初始化为最大值或零(每个边赋一个值)
eg:上图最开始初始化为32767,即表示,所有连接的两点之间距离都是32767
四,构造邻接矩阵。
依次输入每条边依附的顶点和其权值,(输入值后,先确定两个顶点在图中的位置,然后将权赋给两点之间边)
eg:输入AB1,即代表A点B点之间的距离为1;输入AC2,即代表A点C点之间的距离为2.
邻接矩阵表示法深度优先搜索遍历过程:
遍历过程类似于递归过程。
先从你输入的呢一点开始遍历(因为刚开始给全部都初始化值了,所以默认是任何一点与所有点都连接);
已经遍历的点visited[i]赋值为一,代表已经遍历。
碰到不是默认值的数,即为真正有连接的点,若该点已经被遍历,则继续向下,否则跳转到该点。
等到某一点遍历过后,再返回到上一层
eg:
如果上图从A点开始遍历,默认的话,A与其余所有点都有连接,权值为32767.若赋值AB1,AC1。
第一步:看AB是否连接,若AB连接,且B点尚未遍历,则跳转到B点
第二步:B点再开始遍历,首先是BA,虽然BA连接,但是A点已经遍历,所以找下一个真正连接的点,即为D,
第三步:因为BD连接且D尚未遍历,所以从D开始,再以D为起始点,开始遍历
。。。。。。。。。。。
(根据代码可知遍历过程都是从i=0到i= A.point,所以每次都是按照ABCDEFGH进行遍历)
运行截图:
代码:
#include<iostream>
using namespace std;
#define pointMax 100
#define MaxInt 32767
struct AMgroup
{
char VTchart[pointMax]; //顶点表
int AMchart[pointMax][pointMax]; //邻接矩阵
int point, vert; //点,边
};
int AMlocate(AMgroup A, char x)
{
for (int i = 0; i < A.point; i++) //依次输入点的信息
{
if (A.VTchart[i] == x)
{
return i;
break;
}
}
}
void CreatAM(AMgroup &A)
{
cout << "输入邻接矩阵顶点数:"; //第一步
cin >> A.point;
cout << "输入邻接矩阵边数:";
cin >> A.vert;
getchar();
char a[100];
cout << "输入点的信息:"; //第二步
gets_s(a);
for (int i = 0; i < A.point; i++) //依次输入点的信息
{
A.VTchart[i] = a[i];
}
for (int i = 0; i < A.point; i++) //初始换邻接矩阵,边的权值均设为最大 //第三步
{
for (int j = 0; j < A.point; j++)
{
A.AMchart[i][j] = MaxInt;
}
}
cout << endl;
char v1, v2; int len;
for (int i = 1; i <= A.vert; i++) //构造邻接矩阵
{
cout << "输入第"<<i<<"条边的两个顶点以及权值:"; //第四步
cin >> v1 >> v2 >> len;
int m, n;
m = AMlocate(A, v1);
n = AMlocate(A, v2);
A.AMchart[m][n] = A.AMchart[n][m] = len;
}
}
int visited[100] = { 0 };
void Show(AMgroup &A, int v)
{
cout << A.VTchart[v];
visited[v] = 1;
for (int i = 0; i < A.point; i++)
{
if (A.AMchart[v][i] != MaxInt && visited[i] != 1)
{
Show(A, i);
}
}
}
int main()
{
AMgroup *A = new AMgroup;
CreatAM(*A);
int m;
cout << "\n从第几个点开始遍历:";
cin >> m;
Show(*A,m);
getchar();
}