1、深度优先搜索遍历过程
图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索是一个递归的过程
深度优先遍历特点是，选定一个出发点后进行遍历，能前进则前进，若不能前进，回退一步再前进，或再回退一步后继续前进。依此重复，直到所有与选定点相通的所有顶点都被遍历。
2、示例
对图7-25连通无向图采用深度优先搜索遍历可得到顶点访问序列：v0,v1,v3,v7,v4,v8,v2,v5,v6
对图7-26连通无向图采用深度优先搜索遍历可得到顶点访问序列：v0,v1,v3,v2,v4,v5,v6,v7
对图7-27连通无向图采用深度优先搜索遍历可得到顶点访问序列:v0,v1,v4,v3,v2或v2,v3,v0,v1,v4或v2,v1,v0,v4,v3
3、连通图的深度优先遍历
给定一图G=
，用visited[i]表示顶点i的访问情况，初值设为0，表示所有顶点未被访问过，当顶点被访问过时置1。则初始情况下所有的visited[i]都为0。假设从顶点V
4、代码
无向图，邻接矩阵存储：
对图7-25深度优先遍历：
#include
using namespace std; #define INFINITY 65535 /* 表示权值的无穷*/ typedef int EdgeType;//边上的权值类型 typedef int VertexType;//顶点类型 const int MaxSize=100; int visited[MaxSize];//全局标识数组 class MGraph//邻接矩阵类 { public: MGraph(){vertexNum=0;edgeNum=0;} MGraph(VertexType a[],int n);//构造函数，初始化具有n个顶点的零图 void CreateMGraph1(MGraph *Gp);//建立无向图的邻接矩阵 void DFS(int v);//从v出发深度优先遍历的递归函数 void DFS1(int v);//从v出发深度优先遍历的非递归函数 public: int vertexNum,edgeNum;//顶点数和边数 EdgeType adj[MaxSize][MaxSize];//邻接矩阵 VertexType vertex[MaxSize];//顶点表 }; //构造函数，初始化具有n个顶点的零图 MGraph::MGraph(VertexType a[],int n) { vertexNum=n;edgeNum=0; for(int i=0;i
> Gp->vertexNum >> Gp->edgeNum; cout << "请输入顶点信息（空格分隔）：" << endl; for (i = 0; i < Gp->vertexNum; i++) cin >> Gp->vertex[i]; for (i = 0; i < Gp->vertexNum; i++) { for (j = 0; j < Gp->vertexNum; j++) Gp->adj[i][j] = 0; } for (k = 0; k < Gp->edgeNum; k++) { cout << "请输入边（vi, vj)的上标i，下标j（空格分隔）:" << endl; cin >> i >> j; Gp->adj[i][j] = 1; Gp->adj[j][i] = 1;// 因为是无向图，矩阵对称 } } //从v出发深度优先遍历的递归函数 void MGraph::DFS(int v) { int n=vertexNum;//顶点数目 if(v<0||v>=n) throw "位置出错"; cout<
=n) throw "位置出错"; cout<
无向图，邻接表存储：
图7-25：
#include using namespace std; #define INFINITY 65535 /* 表示权值的无穷*/ typedef int EdgeType;//边上的权值类型 typedef int VertexType;//顶点类型 const int MaxSize=100; int visited[MaxSize];//全局标识数组 //无向图邻接表。边表结点结构 struct EdgeNode { int adjvex;//邻接点域 EdgeNode *next;//指向下一个边结点的指针 }; //无向图邻接表。表头结点结构 struct VexNode { VertexType vertex;//顶点 EdgeNode *firstedge;//边表的头指针 }; //邻接表类 class ALGraph { public: ALGraph()//无参构造函数 { vertexNum=0; edgeNum=0; for(int i=0;i adjvex=end;//邻接点 //p->weight=weight; p->next=adjlist[start].firstedge;//前插法插入边结点p adjlist[start].firstedge=p; } //打印存储的图 void ALGraph::displayGraph(int nodeNum) { int i,j; EdgeNode *p; for(i=0;i adjvex<<')'< next; } } } //从v出发深度优先遍历可达顶点递归函数 void ALGraph::DFSL(int v) { int n=vertexNum; int j; EdgeNode *p; if(v>=n||v<0) throw "位置出错"; cout< adjvex;//顶点 if(visited[j]==0) DFSL(j); p=p->next; } } //从v出发深度优先遍历可达顶点的非递归函数 void ALGraph::DFSL1(int v) { int S[MaxSize],top=-1,j,n=vertexNum; EdgeNode *p; if(v>=n||v<0) throw "位置出错"; cout< adjvex;//顶点 if(visited[j]==1) p=p->next; else { cout< 
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/218770.html原文链接：https://javaforall.net
