NOJ数据结构019——基于图的深度优先搜索策略

逃离我推掉我的手 2022-10-20 13:56 111阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

图有多种构造方法，本题要求采用邻接表表示法。

代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #define MAX_VERTEX_NUM 20//最多顶点数
    
    int visited[MAX_VERTEX_NUM];//遍历标志数组
    
    typedef enum {
         DG, DN, UDG, UDN }GraphKind;
    //图的种类，有向图，有向网，无向图，无向网
    
    typedef struct ArcNode {
        
    	int adjvex;//邻接点域
    	struct ArcNode* nextarc;//链域
    	//int weight;//边权（本题不需要）
    }ArcNode;//边表
    
    typedef struct VertexNode {
        
    	int vertexdata;   //顶点数据
    	ArcNode* firstarc;//指向该顶点第一条弧的指针
    }VertexNode;//表头结点表
    
    typedef struct {
        
    	VertexNode vertex[MAX_VERTEX_NUM];//顶点
    	int num_vex, num_arc;//定点数，弧数
    	GraphKind kind;    //图的种类
    }AdjList;
    
    int LocateVertex(AdjList A, int v1);   //找到顶点位置
    void CreateGraph(AdjList* A, int n, int m);   //创建图
    int DFS(AdjList A, int loc1, int loc2);   //深度优先搜索
    
    int main()
    {
        
    	int n, m;
    	scanf("%d%d", &n, &m);
    	AdjList* A;
    	A = (AdjList*)malloc(sizeof(AdjList));
    	if (A == NULL) return 0;
    	CreateGraph(A, n, m);
    	int v1, v2;
    	scanf("%d%d", &v1, &v2);
    	if (DFS(*A, LocateVertex(*A, v1), LocateVertex(*A, v2))) {
        
    		printf("yes");
    	}
    	else {
        
    		printf("no");
    	}
    	return 0;
    }
    
    int LocateVertex(AdjList A, int v1)
    {
           //找到顶点位置
    	for (int i = 0; i < A.num_vex; i++) {
        
    		if (A.vertex[i].vertexdata == v1) {
        
    			return i;
    		}
    	}
    	return -1;
    }
    
    void CreateGraph(AdjList *A, int n, int m)
    {
           //创建图
    	A->kind = DG;
    	A->num_vex = n;
    	A->num_arc = m;
    	for (int i = 0; i < A->num_vex; i++) {
        
    		//表头结点表
    		scanf("%d", &A->vertex[i].vertexdata);
    		A->vertex[i].firstarc = NULL;
    	}
    	int v1, v2, loc1;
    	for (int i = 0; i < A->num_arc; i++) {
        
    		//边表
    		scanf("%d%d", &v1, &v2);
    		loc1 = LocateVertex(*A, v1);
    		ArcNode *tmp;
    		tmp = (ArcNode*)malloc(sizeof(ArcNode));
    		tmp->adjvex = v2;
    		tmp->nextarc = A->vertex[loc1].firstarc;
    		A->vertex[loc1].firstarc = tmp;
    	}
    }
    
    int DFS(AdjList A, int loc1, int loc2)
    {
           //深度优先搜索
    	visited[loc1] = 1;
    	if (loc1 == loc2) {
        
    		return 1;
    	}
    	ArcNode* tmp = A.vertex[loc1].firstarc;
    	while (tmp) {
        
    		int next = LocateVertex(A, tmp->adjvex);
    		if (!(visited[next]) && DFS(A, next, loc2)) {
        //递归
    			return 1;
    		}
    		tmp = tmp->nextarc;
    	}
    	return 0;
    }

另外附上采用邻接矩阵表示的代码，两者思路并未有太大改变：

#include <stdio.h>
    #include <stdlib.h>
    #define MAX_VERTEX_NUM 20//最多顶点数
    
    int visited[MAX_VERTEX_NUM];//遍历标志数组
    
    typedef enum {
         DG, DN, UDG, UDN }GraphKind;
    //图的种类，有向图，有向网，无向图，无向网
    
    typedef struct {
        
    	int vertex[MAX_VERTEX_NUM];  //顶点向量
    	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    	//对无权图，1或0表示是否相邻；对带权图，为权值
    	int num_ver, num_arc;//图的顶点数、边数
    	GraphKind kind;//图的种类
    }AdjMatrix;
    
    int LocateVertex(AdjMatrix A, int v);   //找到顶点位置
    void CreateMatrix(AdjMatrix* A, int n, int m);   //邻接矩阵法创建图
    int NextVertex(AdjMatrix A, int tmp1);   //找到下一个未遍历的顶点
    int DFS(AdjMatrix* A, int v1, int v2);   //深度优先搜索
    
    int main()
    {
        
    	int n, m, v1, v2;
    	AdjMatrix* A;
    	scanf("%d%d", &n, &m);
    	A = (AdjMatrix*)malloc(sizeof(AdjMatrix));
    	CreateMatrix(A, n, m);
    	scanf("%d%d", &v1, &v2);
    	for (int i = 0; i < A->num_ver; i++) {
        
    		visited[i] = 0;
    	}
    	if (DFS(A, LocateVertex(*A, v1), LocateVertex(*A, v2)) == 1) {
        
    		printf("yes");
    	}
    	else {
        
    		printf("no");
    	}
    	return 0;
    }
    
    int LocateVertex(AdjMatrix A, int v)
    {
           //找到顶点位置
    	int tmp = -1;
    	for (int i = 0; i < A.num_ver; i++) {
        
    		if (A.vertex[i] == v) {
        
    			tmp = i;
    			break;
    		}
    	}
    	return tmp;
    }
    
    void CreateMatrix(AdjMatrix* A, int n, int m)
    {
           //邻接矩阵法创建图
    	A->kind = DG;
    	A->num_ver = n;
    	A->num_arc = m;
    	for (int i = 0; i < n; i++) {
         //输入顶点
    		scanf("%d", &A->vertex[i]);
    	}
    	for (int i = 0; i < A->num_ver; i++) {
        
    		for (int j = 0; j < A->num_arc; j++) {
        
    			A->arcs[i][j] = 0;
    		}
    	}
    	int v1, v2, loc1, loc2;
    	for (int i = 0; i < A->num_arc; i++) {
        
    		scanf("%d%d", &v1, &v2);
    		loc1 = LocateVertex(*A, v1);
    		loc2 = LocateVertex(*A, v2);
    		A->arcs[loc1][loc2] = 1;
    	}
    }
    
    int NextVertex(AdjMatrix A, int v1)
    {
           //找到下一个未遍历的顶点
    	for (int i = 0; i < A.num_ver; i++) {
        
    		if (A.arcs[v1][i] == 1
          && visited[i] == 0) {
        
    			return i;
    		}
    	}
    	return -1;
    }
    
    int DFS(AdjMatrix* A, int v1, int v2)
    {
           //深度优先搜索
    	visited[v1] = 1;
    	if (v1 == v2) {
        
    		return 1;
    	}
    	int next = NextVertex(*A, v1);
    	while (next != -1)
    	{
        
    		if (!visited[next] && DFS(A, next, v2)) {
        
    			return 1;
    		}
    		next = NextVertex(*A, v1);
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221020/96da7d43547e41afb85162c9b6cf244a.png