数据结构 图的邻接表表示法 有向 + 无向图的深度优先搜索遍历（C 代码 + 终端输入内容）

 数据结构邻接表表示图的深度优先搜索遍历无向图

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
//下面三个结构体就是邻接表的结构体，完全一样的方式
typedef struct EdgeNode
{
	int adjvex;
	struct EdgeNode* next;
}EdgeNode;
typedef struct VertexNode
{
	char data;
	EdgeNode* firstedge;
}VertexNode;
typedef struct
{
	VertexNode adjlist[MAXVEX];
	int numVertexs;
	int numEdges;
}GraphAdjlist;
int visited[MAXVEX];//一个标记数组，记录遍历过的不会重复遍历
//创建邻接表
void CreateALGraph(GraphAdjlist* G)
{
	int i, j, k;
	EdgeNode* p;
	printf("请输入顶点数+边数\n");
	scanf("%d%d", &G->numVertexs, &G->numEdges);
	getchar();//接收scanf残留的换行符\n
	printf("请输入顶点的信息\n");
	for (i = 0; i < G->numVertexs; i++)
	{
		scanf("%c", &G->adjlist[i].data);
		G->adjlist[i].firstedge = NULL;//初始化指向边表的指针为null
	}
	for (k = 0; k < G->numEdges; k++)
	{
		printf("请输入(vi,vj)的头，尾,一共有%d条\n", G->numEdges);
		scanf("%d%d", &i, &j);
		//我们这里是实现深度遍历连通图的无向图
		p = (EdgeNode*)malloc(sizeof(EdgeNode));
		p->adjvex = j;
		p->next = G->adjlist[i].firstedge;
		G->adjlist[i].firstedge = p;

		p = (EdgeNode*)malloc(sizeof(EdgeNode));
		p->adjvex = i;
		p->next = G->adjlist[j].firstedge;
		G->adjlist[j].firstedge = p;
	}
	printf("邻接表创建成功\n");
}
void DFS(GraphAdjlist* G, int v)
{
	visited[v] = 1;
	printf("%c ", G->adjlist[v].data);
	EdgeNode* p = G->adjlist[v].firstedge;
	while (p!=NULL)
	{
		if (visited[p->adjvex] == 0)
		{
			DFS(G, p->adjvex);
		}
		p = p->next;
	}
}
void DFS_AL(GraphAdjlist* G)
{
	int i;
	for (i = 0; i < G->numVertexs; i++)
	{
		visited[i] = 0;//将顶点这个顺序存放的数组全部设为0
	}
	for (i = 0; i < G->numVertexs; i++)
	{
		if (visited[i] == 0)
		{
			DFS(G, i);
		}
	}
}
int main()
{
	GraphAdjlist G;
	CreateALGraph(&G);
	printf("邻接表的深度优先搜索遍历如下\n");
	DFS_AL(&G);
}

无向图终端输入内容: 

请输入顶点数+边数
5
6
请输入顶点的信息
01234
请输入(vi,vj)的头，尾,一共有6条
0 1
请输入(vi,vj)的头，尾,一共有6条
0 3
请输入(vi,vj)的头，尾,一共有6条
1 2
请输入(vi,vj)的头，尾,一共有6条
1 4
请输入(vi,vj)的头，尾,一共有6条
2 3
请输入(vi,vj)的头，尾,一共有6条
2 4
邻接表创建成功
邻接表的深度优先搜索遍历如下
0 3 2 4 1

 

数据结构邻接表表示图的深度优先搜索遍历有向图

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
//下面三个结构体就是邻接表的结构体，完全一样的方式
typedef struct EdgeNode
{
	int adjvex;
	struct EdgeNode* next;
}EdgeNode;
typedef struct VertexNode
{
	char data;
	EdgeNode* firstedge;
}VertexNode;
typedef struct
{
	VertexNode adjlist[MAXVEX];
	int numVertexs;
	int numEdges;
}GraphAdjlist;
int visited[MAXVEX];//一个标记数组，记录遍历过的不会重复遍历
//创建邻接表
void CreateALGraph(GraphAdjlist* G)
{
	int i, j, k;
	EdgeNode* p;
	printf("请输入顶点数+边数\n");
	scanf("%d%d", &G->numVertexs, &G->numEdges);
	getchar();//接收scanf残留的换行符\n
	printf("请输入顶点的信息\n");
	for (i = 0; i < G->numVertexs; i++)
	{
		scanf("%c", &G->adjlist[i].data);
		G->adjlist[i].firstedge = NULL;//初始化指向边表的指针为null
	}
	for (k = 0; k < G->numEdges; k++)
	{
		printf("请输入(vi,vj)的头，尾,一共有%d条\n", G->numEdges);
		scanf("%d%d", &i, &j);
		//我们这里是实现深度遍历连通图的无向图
		p = (EdgeNode*)malloc(sizeof(EdgeNode));
		p->adjvex = j;
		p->next = G->adjlist[i].firstedge;
		G->adjlist[i].firstedge = p;
	}
	printf("邻接表创建成功\n");
}
void DFS(GraphAdjlist* G, int v)
{
	visited[v] = 1;
	printf("%c ", G->adjlist[v].data);
	EdgeNode* p = G->adjlist[v].firstedge;
	while (p != NULL)
	{
		if (visited[p->adjvex] == 0)
		{
			DFS(G, p->adjvex);
		}
		p = p->next;
	}
}
void DFS_AL(GraphAdjlist* G)
{
	int i;
	for (i = 0; i < G->numVertexs; i++)
	{
		visited[i] = 0;//将顶点这个顺序存放的数组全部设为0
	}
	for (i = 0; i < G->numVertexs; i++)
	{
		if (visited[i] == 0)
		{
			DFS(G, i);
		}
	}
}
int main()
{
	GraphAdjlist G;
	CreateALGraph(&G);
	printf("邻接表的深度优先搜索遍历如下\n");
	DFS_AL(&G);
}

 有向图终端输入内容：

请输入顶点数+边数
4 4
请输入顶点的信息
0123
请输入(vi,vj)的头，尾,一共有4条
0 1
请输入(vi,vj)的头，尾,一共有4条
0 2
请输入(vi,vj)的头，尾,一共有4条
2 3
请输入(vi,vj)的头，尾,一共有4条
3 0
邻接表创建成功
邻接表的深度优先搜索遍历如下
0 2 3 1