邻接表—深度优先遍历_基于邻接表的深度优先遍历

深度优先遍历和广度优先遍历的参考知识点：https://blog.csdn.net/a2217018103/article/details/90678830
下面是使用邻接表做出的深度优先遍历案例：

#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>
//图的邻接表类型定义
typedef char VertexType[4];
typedef char InfoPtr;
typedef int VRType;
#define MaxSize 50   //最大顶点个数 
typedef enum {DG,DN,UN,UG} GraphKind; //图的类型：有向图、有向网、无向图和无向网
typedef struct ArcNode{//边表结点的类型定义 
	int adjvex;// 弧（边）指向的顶点的位置
	InfoPtr *info;//与弧（边）相关的信息 
	struct ArcNode *nextarc;//指示下一个与该顶点相邻接的顶点 
} ArcNode; 
typedef struct VNode{ //表头结点的类型定义 
	VertexType data;//用于存储顶点
	ArcNode * firstarc;//指示第一个与该顶点邻接的顶点 
}VNode,AdjList[MaxSize];
typedef struct{	//图的类型定义 
	AdjList vertex;
	int vexnum,arcnum;//图的顶点的数目与弧的数目 
	GraphKind kind;//图的类型 
}AdjGraph;
//函数声明
int LocateVertex(AdjGraph G,VertexType v);
void CreateGraph(AdjGraph *G);
void DisplayGraph(AdjGraph G);
void DestroyGraph(AdjGraph *G);
//深度 
void DFSTraverse(AdjGraph G);
void DFS(AdjGraph G,int v) ;
int FirstAdjVertex(AdjGraph G,VertexType v);
int NextAdjVertex(AdjGraph G,VertexType v,VertexType w);

void BFSTraverse(AdjGraph G); 
void CreateGraph(AdjGraph *G){
	int i,j,k;
	VertexType v1,v2;//定义两个顶点v1和v2
	ArcNode *p;
	printf("请输入图的顶点数，边数（逗号分割）：");
	scanf("%d,%d",&(*G).vexnum,&(*G).arcnum) ;
	printf("请输入%d个顶点的值：\n",G->vexnum);
	for(i=0;i<G->vexnum;i++){
		scanf("%s",G->vertex[i].data);
		G->vertex[i].firstarc=NULL;
	}
	printf("请输入弧尾和弧头（以空格作为间隔）；\n");
	for(k=0;k<G->arcnum;k++){
		scanf("%s%s",v1,v2);
		i=LocateVertex(*G,v1);
		j=LocateVertex(*G,v2);
		//j为入边，i为出边 创建邻接表
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=j;//邻接点域 
		p->info=NULL;//数据域 
		p->nextarc=G->vertex[i].firstarc;//指针域
		G->vertex[i].firstarc=p;
		//i为入边，j为出边 创建邻接表
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=i;//邻接点域 
		p->info=NULL;//数据域 
		p->nextarc=G->vertex[i].firstarc;//指针域
		G->vertex[j].firstarc=p;
	}
	(*G).kind=UG;
}
//查找 
int LocateVertex(AdjGraph G,VertexType v){
	int i;
	for(i=0;i<G.vexnum;++i){
		if(strcmp(G.vertex[i].data,v)==0){
			return i; 
		}
	}
	return -1;
}
//销毁无向图 
void DestroyGraph(AdjGraph *G){
	int i;
	ArcNode *p,*q;
	for(i=0;i<(*G).vexnum;++i){//释放图中的边表结点 
		p=G->vertex[i].firstarc;//p指向边表的第一个结点 
		if(p!=NULL){//如果边表不为空，则释放边表的结点 
			q=p->nextarc;
			free(p);
			p=q;
		} 
	} 
	(*G).vexnum=0;//将顶点的数目为0 
	(*G).arcnum=0;//将边的数目为0 
}
//打印 
void DisplayGraph(AdjGraph G){
	int i;
	ArcNode *p;
	printf("%d个顶点：\n",G.vexnum);
	for(i=0;i<G.vexnum;i++){
		printf("%s",G.vertex[i].data);
	}
	printf("\n%d条边:\n",2*G.arcnum);
	for(i=0;i<G.vexnum;i++){
		p=G.vertex[i].firstarc;//将p指向边表的第一个结点
		while(p){
			printf("%s->%s  ",G.vertex[i].data,G.vertex[p->adjvex].data);
			p=p->nextarc;
		} 
		printf("\n");
	}
}
int visited[MaxSize]; 
//深度 
void DFSTraverse(AdjGraph G){
	int v;
	for(v=0;v<G.vexnum;v++){
		visited[v]=0;		//访问标志数组初始化为未被访问 
	}
	printf("\n深度优先遍历序列：\n");
	for(v=0;v<G.vexnum;v++){
		if(!visited[v]){	
			DFS(G,v);	//对未访问的顶点v进行深度优先遍历 
		}
	}
	printf("\n");
} 
//打印深度优先遍历的数据 
void Visit(VertexType v){
	printf("%s ", v);
}
//从顶点v出发递归深度优先遍历 
void DFS(AdjGraph G,int v) {
	int w;
	visited[v]=1;//访问标志设置为已访问 
	Visit(G.vertex[v].data);
	for(w=FirstAdjVertex(G,G.vertex[v].data);w>0;w=NextAdjVertex(G,G.vertex[v].data,G.vertex[w].data))
		if(!visited[w])
			DFS(G,w);//递归调用DFS对v的尚未访问的序号为w的邻接顶点 
}
//返回顶点v的第一个邻接顶点的序号 
int FirstAdjVertex(AdjGraph G,VertexType v){
	ArcNode *p;
	int v1;
	v1=LocateVertex(G,v);//v1为顶点v在图G中的序号 
	p=G.vertex[v1].firstarc;
	if(p)		//如果顶点v的第一个邻接点的存在，返回邻接点的序号，否则返回-1 
		return p->adjvex;
	else
	   return -1;
}
//返回v的相对于w的下一个临界顶点的序号 
int NextAdjVertex(AdjGraph G,VertexType v,VertexType w){
		ArcNode *p,*next;
		int v1,w1;
		v1=LocateVertex(G,v);	//v1为顶点v在图G中的序号 
		w1=LocateVertex(G,w);   //w1为顶点v在图G中的序号 
		for(next=G.vertex[v1].firstarc;next;){
			if(next->adjvex!=w1){
					
				}
		   next=next->nextarc;
		}
		p=next;			//p指向顶点v的邻接顶点w的结点 
		if(!p||p->nextarc){//如果w不存在或w是最后一个邻接点，则返回-1 
			return -1;
		}else{
			return p->nextarc->adjvex;//返回v的相对于w的下一个邻接点的序号 
		}
}
int main(){
	AdjGraph G;
	printf("采用邻接表创建无向图G:\n");
	CreateGraph(&G);
	printf("输出无向图G:");
	DisplayGraph(G); 
	DFSTraverse(G);
	DestroyGraph(&G);
	return 1;
} 

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

效果图：