图的深度优先搜索遍历 -- c语言

﹏ヽ暗。殇╰゛Y 2022-11-21 09:28 181阅读 0赞

相比于我之前的邻接矩阵和邻接表的创建知识点多了个深度优先搜索函数。  
可以在两篇直接增加该函数，便是邻接矩阵或邻接表的深度优先搜索。  
首先是邻接矩阵的深度优先函数。  
都是书上的，只是多了几个变量的定义和初始化  
函数代码如下：

bool visited[MVNum];//访问标志数组 ,其初始值为false 
    void InitVisited(bool *visited)//标志数组初始化 
    { 
    	for(int i=0;i<MVNum;i++)
    		visited[i] = false;
    } 
    int w1;//定义一个全局变量 
    void DFS_AM(AMGraph G,int v)//深度优先搜索遍历邻接矩阵 
    { 
    	printf("%c",G.vexs[v]);//访问第v个顶点 
    	visited[v] = true;//并置访问标志数组相应分量值为true 
    	for(int w=0;w<G.vexnum;w++)//依次检查邻接矩阵v所在的行 
    	{ 
    		if(G.arcs[v][w] != 0&&visited[w] == false)//递归终止条件 
    		{ 
    			w1 = w;
    			DFS_AM(G,w1);//进入递归 
    		}
    	}		
    }

其次是邻接表的深度优先函数。  
代码如下：

bool visited[MVNum];//访问标志数组 ,其初始值为false 
    void InitVisited(bool *visited)//标志数组初始化 
    { 
    	for(int i=0;i<MVNum;i++)
    		visited[i] = false;
    } 
    int w;//定义一个全局变量 
    ArcNode *p3;
    void DFS_AL(ALGraph G,int v)//深度优先搜索遍历邻接表 
    { 
    	printf("%c",G.vertices[v].data);//访问第v个顶点 
    	visited[v] = true;//并置访问标志数组相应分量值为true 
    	p3 = G.vertices[v].firstarc;
    	while(p3 != NULL)
    	{ 
    		w = p3->adjvex;
    		if(visited[w] == false)//递归终止条件
    			DFS_AL(G,w);//进入递归 
    		p3 = p3->nextarc;
    	}		
    }