深度优先遍历算法DFS:
邻接矩阵:
#include<iostream>
using namespace std;
typedef int Status;
#define MaxInt 999999 //表示无穷大
#define MVNum 100 //最大顶点数
//MAX Vertex Number
typedef char VertexType; //设顶点类型:字符型
typedef int ArcType; //设边的权值类型:int型
struct AMG
{
VertexType vex[MVNum]; //顶点表
ArcType arc[MVNum][MVNum]; //邻接矩阵
int VexNum, ArcNum; //(图)当前:顶点数和边数
}; //Adjacency Matrix Graph
//深度优先遍历算法(邻接矩阵)
int visited[MVNum] = {}; //未访问时元素全部为空
void DFS(AMG G, int v)
{
int w;
//访问第v个结点
cout << G.vex[v]; //输出顶点内容
//cout << v << endl;
visited[v] = 1;
//依次检查邻接矩阵v所在的行
for (w = 0; w < G.VexNum; w++)
//从邻接矩阵的第v行的第1个元素开始-遍历到该行第n个元素
{
if ((G.arc[v][w] != 0) && !visited[w])
//相连且未被访问过
DFS(G, w);
}
//算法时间复杂度O(n^2)
}
int main()
{
}
邻接表:
一开始我写的(第一版):
void DFS(ALG G, int v)
{
int w,i=0;
ArcNode* p=G.vex->firstarc;
//访问第v个结点
while (i < v)
{
p = p->nextarc;
i++;
}
cout << p->adjvex; //输出顶点内容位置
visited[v] = 1;
//依次检查邻接矩阵v所在的行
for (w = 0; w < G.vexnum; w++)
//从邻接矩阵的第v行的第1个元素开始-遍历到该行第n个元素
{
p = p->nextarc;
if ((p->adjvex) && !visited[w])
// if ((G.vex[v][w] != 0) && !visited[w])
//相连且未被访问过
DFS(G, w);
}
}
这里,我们犯(陷入)了许多个逻辑错误
问题:
(1):
我们写的函数:在一开始指向的,并不是第 i 个顶点,而是第一个顶点的第 i 个元素
更何况我们第一步要输出的,是一个顶点,而非一个边结点
(2):
在最后的判断语句最好还是新设立一个指针变量,要不然后面我感觉p容易变混乱了
哈哈哈扯淡的,后面其实根本不需要这个玩意
最终成品:
//深度优先遍历算法
int visited[MVNum] = {}; //未访问时元素全部为空
void DFS(ALG G, int v)
{
int w,i=0;
cout << G.vex[v].data;
visited[v] = 1;
ArcNode* p = G.vex[v].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] != 0)
DFS(G,p->adjvex);
p = p->nextarc;
}
}
By the way,复习一下链表【取第i个元素】:
Status 取第i个元素(LinkList L, int i, Elemtype e)
{// GetElem“i”
LinkList p;
p = L->next;
int j = 1;
while (p && i > j)
{
p = p->next;
j++;
}
if (i < 0 || i < j || !p)
return false;
e = p->data;
return true;
}
广度优先遍历算法BFS
breadth:宽度;(知识、兴趣等的)广泛
邻接表:
我写的:
int visited[MVNum] = {};
void BFS(ALG G, int v)
{
cout << G.vex[v].data;
visited[v] = 1;
SqQueue Q;
InitQueue(Q);
EnQueue(Q, G.vex[v].firstarc->adjvex);//从第一个顶点开始遍历
auto i = G.vex[v].firstarc;//指向(代表)链头
while (!QueneEmpty(Q))//直至队空结束
{
auto j = i;//用于指向访问各个元素节点
while (j != NULL)//当结点为空(链尾,结束了)结束循环
{
if (visited[j->adjvex] == 0)//入队【没被访问过的】元素
{
EnQueue(Q, j->adjvex);
}
j = j->nextarc;//指向下一轮循环
visited[j->adjvex] = 1;//别忘了
}
DeQueue(Q, i->adjvex);//出队队头
cout << j->adjvex;
//输出出队的元素,当然这里出队和输出在循环开始时操作也可以
}
}
详细学习过程以及整个过程中所有踩的坑,详见:
数据结构与算法基础(王卓)(24)附:邻接表的广度优先遍历算法BFS(学习过程记录)_宇 -Yu的博客-CSDN博客
邻接矩阵:
void BFS(AMG& G)
{
for (int v = 0; v < G.VexNum; ++v)
{
for (int w = 0; w < G.VexNum; ++w)
{
if ((G.arc[v][w] != 0) && visited[w] == 0)
{
cout << G.vex[w];
visited[w] = 1;
}
}
}
//算法时间复杂度O(n^2)
}
我感觉这个写的就是逐个访问输出
不过也无所谓了,这玩意不是很重要,而且总归是能写的