图的深度优先遍历（递归与非递归C语言）
递归：
#include
#include
#include
#define MaxVertexNum 10 /* 最大顶点数设为10 */
#define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex; /* 用顶点下标表示顶点,为整型 */
typedef int WeightType; /* 边的权值设为整型 */
typedef struct GNode *PtrToGNode;
struct GNode{
Vertex V[MaxVertexNum];//定义一个顶点数组，方便之后用数组下标来取顶点的数据
int Nv; /* 顶点数 */
int Ne; /* 边数 */
WeightType g[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
bool visited[MaxVertexNum]; /* 顶点的访问标记 */
MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */
void Visit( Vertex V )
{
printf(" %d", V);
}
void DFS( MGraph G, Vertex V);
int main()
{
MGraph G;
Vertex V;
G = CreateGraph();
printf("请输入从哪一个顶点开始深度优先遍历");
scanf("%d", &V);
printf("DFS from %d:", V);
for(int i = 0;i < G->Nv;i++){// 初始化visited，用来标识是否已经访问过
visited[i] = false;
}
for(int j = 0;j < G->Nv;j++){
if(!(visited[j]))
{
DFS(G, V);
}
}
return 0;
}
MGraph CreateGraph(){
MGraph G;
G = (MGraph)malloc(sizeof(GNode));
G->Ne = 0; //初始化一下
G->Nv = 0;
int N; //表示图中顶点数
printf("输入图含有几个顶点");
scanf("%d",&N);
G->Nv = N;
printf("输入这N个顶点是什么");
for(int k = 0;k < N;k++){
scanf("%d",&G->V[k]);
}
int tag;//来标识有没有边
for(int i = 0;i < N;i++){
printf("输入邻接矩阵第%d行是什么",i);
for(int j = 0;j < N;j++){
scanf("%d",&tag);
if(tag != 0){
tag = 1;
G->Ne = G->Ne + 1;
}
G->g[i][j] = tag;
}
}
return G;
}
void DFS( MGraph G, Vertex V){
//找到V这个顶点的下标
int j;
for(j = 0;G->V[j] != V;j++);
Visit(V);
visited[j] = true;
for(int k = 0;k < G->Nv;k++){
if(visited[k] == false && G->g[j][k] == 1){
DFS(G,G->V[k]);
}
}
}
递归算法中的核心代码块我认为是visited[k] == false && G->g[j][k] == 1，这条语句套在if语句中来判断是不是要递归，这条语句的意思是，如果该行没有被访问过，并且存在边的时候，进行递归，因为图的邻接矩阵是一个方阵假设是A，假如从0到1有边，那么A(0,1)那个位置就是1，要是有权值A(0,1)就是权值，是无向图的话A(1,0)也是同理的，所以在判断点有没有访问过可以直接利用列上的值就可以，递归传回的顶点也是，例如是A(0,1)，则传回去1就可以，然后再用从1顶点继续递归。
非递归：
#include
#include
#include
#define MaxVertexNum 10 /* 最大顶点数设为10 */
#define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex; /* 用顶点下标表示顶点,为整型 */
typedef int WeightType; /* 边的权值设为整型 */
typedef struct GNode *PtrToGNode;
struct GNode{
Vertex V[MaxVertexNum];//定义一个顶点数组，方便之后用数组下标来取顶点的数据
int Nv; /* 顶点数 */
int Ne; /* 边数 */
WeightType g[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
typedef struct{//定义一个栈
int index; //记录每个顶点的下标
int data; //记录值
}stuck;
bool visited[MaxVertexNum]; /* 顶点的访问标记 */
MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */
void Visit( Vertex V )
{
printf(" %d", V);
}
void DFS( MGraph G, Vertex V);
int main()
{
MGraph G;
Vertex V;
G = CreateGraph();
printf("请输入从哪一个顶点开始深度优先遍历");
scanf("%d", &V);
printf("DFS from %d:", V);
for(int i = 0;i < G->Nv;i++){// 初始化visited，用来标识是否已经访问过
visited[i] = false;
}
for(int j = 0;j < G->Nv;j++){
if(!(visited[j]))
{
DFS(G, V);
}
}
return 0;
}
MGraph CreateGraph(){
MGraph G;
G = (MGraph)malloc(sizeof(GNode));
G->Ne = 0; //初始化一下
G->Nv = 0;
int N; //表示图中顶点数
printf("输入图含有几个顶点");
scanf("%d",&N);
G->Nv = N;
printf("输入这N个顶点是什么");
for(int k = 0;k < N;k++){
scanf("%d",&G->V[k]);
}
int tag;//来标识有没有边
for(int i = 0;i < N;i++){
printf("输入邻接矩阵第%d行是什么",i);
for(int j = 0;j < N;j++){
scanf("%d",&tag);
if(tag != 0){
tag = 1;
G->Ne = G->Ne + 1;
}
G->g[i][j] = tag;
}
}
return G;
}
void DFS( MGraph G, Vertex V){
//栈初始化
stuck s[MaxVertexNum];
int top = -1;
//找这一点的下标
int i;
for(i = 0;G->V[i] != V;i++);
visited[i] = true;
top = top + 1;
s[top].data = V;
s[top].index = i;
Visit(s[top].data);
int m;int k;
while(top != -1){
for(m = 0; m < G->Nv;m++){
if((G->g[s[top].index][m] == 1)&&(visited[m] == false)){
break;
}
}
if(m == G->Nv){//相等说明遍历了一行没有1或者都遍历过了，要出栈
top = top -1;
}
else{//不相等的话这个j就是下一个要遍历的下标
//入栈操作
top = top + 1;
s[top].data = G->V[m];
s[top].index = m;
visited[m] = true;
//访问
Visit(s[top].data);
i = m;
}
}
}
算法思想：递归算法都是用栈来完成的，所以非递归一定要创建一个栈，我的代码中创建了一个栈，栈中包含两个变量，一个是data（数据）一个是index（在数组中的下标），当有节点时就进栈，没有可访问节点时就出栈，该代码的核心代码我认为是((G->g[s[top].index][m] == 1)&&(visited[m] == false))其功能是为了找到顶点的下标，就这样一直循环，到栈空的时候循环结束
运行结果：
发表评论