深入理解图结构：邻接矩阵与邻接表的DFS(深度优先遍历)实现解析
最编程
2024-02-20 20:09:50
...
#include<algo.h>
typedef struct Adjvex //邻接域
{
int adjvex; //顶点的邻接点在数组的下标
int weight; //权值
Adjvex* next; //下一个邻接点在数组的下标
}*Edgenode,Adjvex;
typedef struct Vertxnode //顶点节点
{
ElemType data;
Adjvex* firstedge;
}Vertexnode,Adjlist[MAXSIZE];
typedef struct Graphlist //邻接表
{
Adjlist adjlist; //顶点数组以及邻接域
int vexnum, edgenum; //顶点和边数目;
}Graphlist,*p_Graphlist;
int Visited[MAXSIZE] = {0}; //用来表示当前顶点是否被访问 1表示访问 0表示没有访问
int AdjRectangle[MAXSIZE][MAXSIZE]; //二维数组模拟邻接矩阵
void DFS(p_Graphlist p, int i)//邻接矩阵的深度优先递归遍历
{
int j;
Visited[i] = 1; //如果访问了该节点则设置为1
cout << "顶点数据为:" << p->adjlist[i].data << endl; //输出当前节点数据
for (j = 0; j < p->vexnum; j++)//循环调用递归
{
if (AdjRectangle[i][j] == 1 && !Visited[j])//如果边表是1且当前节点没有被访问过则调用递归
{
DFS(p, j);//j=0，1，2，3，4...,直到将每一个节点都递归访问了一次之后才结束
}
}
}
void DFSTraverse(p_Graphlist p)
{
int i;
for (i = 0; i < p->vexnum; i++)
{
Visited[i] = 0; //先将所有数据设置为未遍历状态0
}
cout << "数据如下：" << endl;
for (i = 0; i < p->vexnum; i++)//
{
if (!Visited[i])
{
DFS(p,i);
}
}
}
//邻接表的深度优先递归算法
void AdjDFS(p_Graphlist p, int i)
{
Edgenode e;
Visited[i] = 1; //访问了当前节点就设置为1
cout << p->adjlist[i].data << endl; //输出当前数据
e = p->adjlist[i].firstedge; //将第一个邻接点赋值给边表结构体指针
while (e)
{
if (!Visited[e->adjvex])//判断节点是否被访问过 没有则进行递归遍历
{
AdjDFS(p, e->adjvex);
}
e = e->next;//让e指向自己的下一个位置
}
}
void AdjDFSTraverse(p_Graphlist p)
{
int i;
for (i = 0; i < p->vexnum; i++)
Visited[i] = 0;//初始化访问数组
for (i = 0; i < p->vexnum; i++)
{
if (!Visited[i])
{
AdjDFS(p, i);
}
}
}
void CreateGraphlist(p_Graphlist p)
{
int i, j, k;
Edgenode e;
cout << "输入顶点数和边数" << endl;
cin >> p->vexnum >> p->edgenum; //输入边数和表数
for (i = 0; i < p->vexnum; i++) //初始化顶点表
{
cout << "输入顶点数据" << endl;
cin >> p->adjlist[i].data; //顶点数据赋值
p->adjlist[i].firstedge = NULL; //暂定邻接边表为空
}
for (i = 0; i < p->vexnum; i++)//二维数组模拟邻接矩阵|0 0 1|
{ //例如 |0 0 1|
for (k = 0; k < p->vexnum; k++) // |1 1 0|
{
AdjRectangle[i][k] = 0; //暂定初始化为全0
}
}
for (k = 0; k < p->edgenum; k++)//这个for循环用于输入edgenum个边
{
cout << "输入边(vi,vj)上的顶点序号" << endl; //vi为边尾，vj为边头
cin >> i >> j; //输入0，1则代表边尾为v0，边头尾v1
AdjRectangle[i][j] = 1; //对应的数组位置设置为1，代表有一个表
AdjRectangle[j][i] = 1; //矩阵是对称的，对应的位置也置为1
e = (Edgenode)malloc(sizeof(Adjvex)); //创建邻接顶点表指针
e->adjvex = j; //邻接表的顶点指向j
e->next = p->adjlist[i].firstedge; //这句话的作用是为了使得
p->adjlist[i].firstedge = e; //第一个边指向第一个边表
e = (Edgenode)malloc(sizeof(Adjvex)); //对称式结构
e->adjvex = i;
e->next = p->adjlist[j].firstedge;
p->adjlist[j].firstedge = e;
}
for (int i = 0; i < p->vexnum; i++) { //输出邻接矩阵
for (int j = 0; j < p->vexnum; j++)
{
cout << AdjRectangle[i][j] << " ";
}
cout << endl;
}
DFSTraverse(p);
AdjDFSTraverse(p);
}
int main()
{
p_Graphlist p;
p = (p_Graphlist)malloc(sizeof(Graphlist));
CreateGraphlist(p);
}