图的深度优先搜索-递归
图的深度优先搜索的过程：
(1)从图的某个顶点V出发，访问V.
(2)找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直到
刚顶点没有未bedi被访问的邻接点为止。
（3）返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该din
顶点的下一个未被访问的邻接点，访问该顶点。
(4)重复步骤（2）和（3），直到图中所有的顶点都被访问过，搜索结束。
例如，上图的深度遍历过程如下：
（1）从a顶点出发，访问a。
（2）从a出发，访问第一个未被访问的邻接点b，访问b。以b作为新的起点，重复此步骤，访问e，c，d。
对于图的邻接表和邻接矩阵有不同的实现方式：
当图采用邻接表表示时：
//采用邻接表表示的图的深度优先搜索
void DFS(ALGraph G,int v)
{//图G为邻接表类型cout<adjvex; //表示w是v的邻接点if(!visited[w]) DFS(G,w);//如果w未访问，递归p=p->nextarc;// p指向下一个边结点}
} 当图采用邻接矩阵表示时：
//采用邻接矩阵表示图的深度优先遍历
void DFS_AM(AMGraph &G, int v){cout<
代码的具体实现如下：
1.
#include
#include
#include
#define MAXSIZE 100
#define MaxInt 32767 //表示最大值，即正无穷大
#define MVNum 100 //定义最大顶点数
using namespace std;//========================使用邻接表法表示图============================
typedef char VerTexType; //定义顶点数据类型为字符型
typedef int ArcType; //定义边的权值类型为整型
//定义边结点
typedef struct ArcNode{int adjvex; //该边所指向顶点的位置struct ArcNode *nextarc; //指向下一条边的指针
}ArcNode;
//定义顶点结点信息
typedef struct VNode{VerTexType data; ArcNode *firstarc; //指向依附于该顶点的边的指针
}VNode, AdjList[MVNum];
//定义连接表结构
typedef struct{AdjList vertices;int vexnum, arcnum; //当前图的顶点数和边数
}ALGraph; bool visited[MVNum]; //访问标志数组,初试为false //==============================图的遍历和创建================================= //确定顶点vex在G.vertices中的序号
int LocateVex(ALGraph &G, VerTexType vex){for(int i=0;i>G.vexnum;printf("输入总边数:");cin>>G.arcnum;//输入各个顶点,构造邻接表的表头结点表for(int i=0;i>G.vertices[i].data;G.vertices[i].firstarc=NULL;} //输入各边，构造邻接表for(int k=0;k>v1;printf("请输入边依附的第2个顶点:");VerTexType v2;cin>>v2;//确定v1，v2在图G中的位置，即在G.vertices中的序号 int i=LocateVex(G, v1);int j=LocateVex(G, v2);struct ArcNode *p1, *p2;p1=new ArcNode; //生成一个新的边结点 p1->adjvex=j;p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;p2=new ArcNode; //生成另一个对称边结点p2 p2->adjvex=i;p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;}
} //遍历图的邻接表
void PrintfG(ALGraph &G){printf("遍历图的邻接表:\n");for(int i=0;iadjvex);p=p->nextarc;}}printf("\n");
}//采用邻接表表示的图的深度优先搜索
void DFS(ALGraph G,int v)
{//图G为邻接表类型cout<adjvex; //表示w是v的邻接点if(!visited[w]) DFS(G,w);//如果w未访问，递归p=p->nextarc;// p指向下一个边结点}
}int main(){ALGraph G;CreateUGD(G);PrintfG(G);//初始化访问数组for(int i=0;i 2.
#include
#include
#include
#define MAXSIZE 100
#define MaxInt 32767 //表示最大值，即正无穷大
#define MVNum 100 //定义最大顶点数
using namespace std;typedef char VerTexType;//假设顶点数据类型为字符型
typedef int ArcType;//假设边的权值为整型
typedef struct {VerTexType vexs[MVNum];//顶点表 ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum,arcnum;//图的当前顶点数和边数
}AMGraph;bool visited[MVNum]; //访问标志数组,初试为false //查找一个顶点在图G中的位置
int LocateVex(AMGraph &G, VerTexType vex){for(int i=0;i>G.vexs[i];}printf("\n");//初始化邻接矩阵 for(int i=0;i>v1; printf("请输入边的第二个顶点:");VerTexType v2;//scanf("%c", &v2);cin>>v2;printf("请输入边的权重:");ArcType weight;scanf("%d", &weight); //确定v1和v2在G中的位置，即顶点数组的下标int i=LocateVex(G, v1);printf("v1在图G中的位置:%d\n", i); int j=LocateVex(G, v2);printf("v2在图G中的位置:%d\n", j); G.arcs[i][j]=weight;G.arcs[j][i]=G.arcs[i][j];}
} //输出图的邻接矩阵
void PrintAM(AMGraph &G){printf("\n输出图的邻接矩阵:\n");for(int i=0;i
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！