欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图之深搜与广搜

程序员文章站 2022-03-25 14:02:12
...

邻接矩阵的定义:

#define MAXVEX 100
typedef char VertexType;
typedef int EdgeType;
struct GraphStruct;
typedef struct GraphStruct *Graph;
struct GraphStruct{
    VertexType vexs[MAXVEX]; /*顶点,下标从0开始*/
    EdgeType edge[MAXVEX][MAXVEX]; /*邻接矩阵*/
    int vertexNum,edgeNum;
};
邻接表的定义:
#define MAXVEX 100 /*最大顶点数*/
typedef char VertexType;
struct GraphStruct;
typedef struct GraphStruct *Graph;

typedef struct ENode{
    int adjVertex;  /*该边所指的顶点的位置*/
    int weight;     /*边的权*/
    struct ENode *nextEdge;  /*指向下一条边的指针*/
}ENode;

typedef struct VNode{
    VertexType data;   /*顶点信息*/
    ENode *firstEdge; /*指向第一条依附该顶点的边的弧指针*/
}VNode;

struct GraphStruct{
    VNode vexs[MAXVEX];
    int vertexNum,edgeNum; /*图的当前顶点数和弧数*/
};


无向带权图(邻接表)

完成void BFS(Graph g,int k)函数,该函数从第k个点开始广度优先遍历图g,遍历过程中把访问过的顶点的visited设置为1(初始为0)。请注意,在测试代码中已经完成int locateVertex(Graph g, VertexType v);函数(在图g中查找顶点v的序号,不存在返回-1),你可以直接调用。

我们这里怎么实现图的深搜:

void DFS(Graph g,int v0)
{
	ENode* p; 
	int w;
	g->vexs[v0].visited=1;
	p=g->vexs[v0].firstEdge;
	while(p!=NULL){//每一个while循环,都是同一个节点的边。 
		w=p->adjVertex;
		if(g->vexs[w].visited==0){
			DFS(g,w);//每一次DFS都是更进一层的循环 
		}
		p=p->nextEdge;
	}
}

实现图的广搜:

void BFS(Graph g,int k)
{
	queue<int> q;
	ENode *p;
	g->vexs[k].visited=1;
	q.push(k);
	int v,w;
	while(q.size()){//循环一次,访问一个节点的所有边
		v=q.front();
		q.pop();
		p=g->vexs[v].firstEdge;
		while(p!=NULL){
			w=p->adjVertex;
			if(g->vexs[w].visited==0){
				g->vexs[w].visited=1;
				q.push(w);//将边对应的节点放到队列里面
			}
		p=p->nextEdge;
		}
	}
} 

无向带权图(邻接矩阵)

在这里我们怎么实现图的深搜:

void DFS(Graph g, int i)  
{  
   
    g->visited[i] = 1;  
    for(int j = 0; j < g->vertexNum; j ++){
    	if(g->edge[i][j] == 1 && g->visited[j] == 0) {
    		 DFS(g,j); 
    	}      
    }           
}  

在这里我们怎么实现图的广搜:

void BFS(Graph g,int i)
{
    queue<int> q;
    q.push(i);
    int v;
    while(q.size()){
	i=q.front();
	q.pop();
	for(int j=0;j<g->vertexNum;j++){
	    if(g->edge[i][j]==1 && g->visited[j]==0){
	        g->visited[j]=1;
                q.push(j);
	    }	
        }                                                                                                    
    }
} 

深搜:

图之深搜与广搜

广搜:
图之深搜与广搜

相关标签: 深搜