图的深度优先遍历（递归与非递归C语言）_图的深度优先搜索递归和非递归算法

图的深度优先遍历（递归与非递归C语言）

递归：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define MaxVertexNum 10  /* 最大顶点数设为10 */
#define INFINITY 65535   /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex;      /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;  /* 边的权值设为整型 */

typedef struct GNode *PtrToGNode;
struct GNode{
	Vertex V[MaxVertexNum];//定义一个顶点数组，方便之后用数组下标来取顶点的数据 
    int Nv;  /* 顶点数 */
    int Ne;  /* 边数   */
    WeightType g[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
bool visited[MaxVertexNum]; /* 顶点的访问标记 */

MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */

void Visit( Vertex V )
{
    printf(" %d", V);
}

void DFS( MGraph G, Vertex V);


int main()
{
    MGraph G;
    Vertex V;
	
    G = CreateGraph();
    printf("请输入从哪一个顶点开始深度优先遍历");
    scanf("%d", &V);
    printf("DFS from %d:", V);
    
	for(int i = 0;i < G->Nv;i++){// 初始化visited，用来标识是否已经访问过
		visited[i] = false; 
	}
	for(int j = 0;j < G->Nv;j++){
		if(!(visited[j]))
		{
			DFS(G, V);
		}
	}
    

    return 0;
}
MGraph CreateGraph(){
	MGraph G;
	G = (MGraph)malloc(sizeof(GNode));
	G->Ne = 0;	//初始化一下 
	G->Nv = 0;
	int N; //表示图中顶点数 
	printf("输入图含有几个顶点"); 
	scanf("%d",&N);
	G->Nv = N;
	printf("输入这N个顶点是什么");
	for(int k = 0;k < N;k++){
		scanf("%d",&G->V[k]);
	}
	int tag;//来标识有没有边 
	for(int i = 0;i < N;i++){
		printf("输入邻接矩阵第%d行是什么",i);
		for(int j = 0;j < N;j++){
			scanf("%d",&tag);
			if(tag != 0){
				tag = 1;
				G->Ne  = G->Ne + 1;
			}
			G->g[i][j] = tag;
		}
	}
	return G;
}

void DFS( MGraph G, Vertex V){
	
	//找到V这个顶点的下标
	int j;
	for(j = 0;G->V[j] != V;j++);
	Visit(V);
	visited[j] = true;
	for(int k = 0;k < G->Nv;k++){
		if(visited[k] == false && G->g[j][k] == 1){
			DFS(G,G->V[k]);
		}
	}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

递归算法中的核心代码块我认为是visited[k] == false && G->g[j][k] == 1，这条语句套在if语句中来判断是不是要递归，这条语句的意思是，如果该行没有被访问过，并且存在边的时候，进行递归，因为图的邻接矩阵是一个方阵假设是A，假如从0到1有边，那么A(0,1)那个位置就是1，要是有权值A(0,1)就是权值，是无向图的话A(1,0)也是同理的，所以在判断点有没有访问过可以直接利用列上的值就可以，递归传回的顶点也是，例如是A(0,1)，则传回去1就可以，然后再用从1顶点继续递归。

非递归：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define MaxVertexNum 10  /* 最大顶点数设为10 */
#define INFINITY 65535   /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex;      /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;  /* 边的权值设为整型 */

typedef struct GNode *PtrToGNode;
struct GNode{
	Vertex V[MaxVertexNum];//定义一个顶点数组，方便之后用数组下标来取顶点的数据 
    int Nv;  /* 顶点数 */
    int Ne;  /* 边数   */
    WeightType g[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};

typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */

typedef struct{//定义一个栈 
	int index; //记录每个顶点的下标 
	int data; //记录值 
}stuck;
bool visited[MaxVertexNum]; /* 顶点的访问标记 */

MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */

void Visit( Vertex V )
{
    printf(" %d", V);
}

void DFS( MGraph G, Vertex V);


int main()
{
    MGraph G;
    Vertex V;
	
    G = CreateGraph();
    printf("请输入从哪一个顶点开始深度优先遍历");
    scanf("%d", &V);
    printf("DFS from %d:", V);
    
	for(int i = 0;i < G->Nv;i++){// 初始化visited，用来标识是否已经访问过
		visited[i] = false; 
	}
	for(int j = 0;j < G->Nv;j++){
		if(!(visited[j]))
		{
			DFS(G, V);
		}
	}
    return 0;
}
MGraph CreateGraph(){
	MGraph G;
	G = (MGraph)malloc(sizeof(GNode));
	G->Ne = 0;	//初始化一下 
	G->Nv = 0;
	int N; //表示图中顶点数 
	printf("输入图含有几个顶点"); 
	scanf("%d",&N);
	G->Nv = N;
	printf("输入这N个顶点是什么");
	for(int k = 0;k < N;k++){
		scanf("%d",&G->V[k]);
	}
	int tag;//来标识有没有边 
	for(int i = 0;i < N;i++){
		printf("输入邻接矩阵第%d行是什么",i);
		for(int j = 0;j < N;j++){
			scanf("%d",&tag);
			if(tag != 0){
				tag = 1;
				G->Ne  = G->Ne + 1;
			}
			G->g[i][j] = tag;
		}
	}
	return G;
}

void DFS( MGraph G, Vertex V){
	//栈初始化 
	stuck s[MaxVertexNum];
	int top = -1;
	//找这一点的下标
	int i; 
	for(i = 0;G->V[i] != V;i++);
	visited[i] = true;
	top = top + 1;
	s[top].data = V;
	s[top].index = i;
	Visit(s[top].data);
	int m;int k;
	while(top != -1){
		for(m = 0; m < G->Nv;m++){
			if((G->g[s[top].index][m] == 1)&&(visited[m] == false)){
				break;
			}
		}
		if(m == G->Nv){//相等说明遍历了一行没有1或者都遍历过了，要出栈 
			top = top -1;
		} 
		else{//不相等的话这个j就是下一个要遍历的下标 
			//入栈操作 
			top = top + 1;
			s[top].data = G->V[m];
			s[top].index = m;
			visited[m] = true;
			//访问
			Visit(s[top].data); 
			i = m;
			
		}		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

算法思想：递归算法都是用栈来完成的，所以非递归一定要创建一个栈，我的代码中创建了一个栈，栈中包含两个变量，一个是data（数据）一个是index（在数组中的下标），当有节点时就进栈，没有可访问节点时就出栈，该代码的核心代码我认为是((G->g[s[top].index][m] == 1)&&(visited[m] == false))其功能是为了找到顶点的下标，就这样一直循环，到栈空的时候循环结束

运行结果：