第11周项目3-图遍历算法实现（深度优先DFS）
分类:
文章
•
2023-04-01 23:16:01
-
/*
-
*Copyright(c)2017,烟台大学计算机学院
-
*All right reserved.
-
*文件名：sk.cpp btree.h btree.cpp
-
*作者：盛凯
-
*完成日期：2017年12月14日
-
*版本号：v1.0
-
*
-
*问题描述:图遍历算法实现
-
*输入描述：无
-
*程序输出：见运行结果
-
-
sk.cpp:
-
-
#include <stdio.h>
#include <malloc.h>
#include "graph.h"
int visited[MAXV];
void DFS(ALGraph *G, int v)
{
ArcNode *p;
int w;
visited[v]=1;
printf("%d ", v);
p=G->adjlist[v].firstarc;
while (p!=NULL)
{
w=p->adjvex;
if (visited[w]==0)
DFS(G,w);
p=p->nextarc;
}
}
int main()
{
int i;
ALGraph *G;
int A[5][5]=
{
{0,1,0,1,0},
{1,0,1,0,0},
{0,1,0,1,1},
{1,0,1,0,1},
{0,0,1,1,0}
};
ArrayToList(A[0], 5, G);
for(i=0; i<MAXV; i++) visited[i]=0;
printf(" 由2开始深度遍历:");
DFS(G, 2);
printf("\n");
for(i=0; i<MAXV; i++) visited[i]=0;
printf(" 由0开始深度遍历:");
DFS(G, 0);
printf("\n");
return 0;
}
-
程序运行结果如图所示：
-
-
反思总结：图的深度优先占内存较少但是速度较慢。
