邻接表的深度优先搜索技术

邻接表的深度优先搜索技术 概述

承接上文的邻接矩阵深度优先遍历

细节描述

需要注意的是,如果你想遍历非连通图,那么普通的深度优先遍历是行不通的例如以下代码

void DFS_AL(ALGragh G, int v)
{
	int w;
	AdjNode* p;
	cout << G.Vex[v].data << " ";
	visited[v] = true;
	p = G.Vex[v].first;
	while (p)
	{
		w = p->v;
		if (!visited[w])
		{
			DFS_AL(G, w);
		}
		p = p->next;
	}
}

如果你用此代码遍历非连通图,会出现下列情况

可以看到,没有遍历完,出现下列的情况的原因很简单,因为v3的后面是空的,所以根据while循环,提前终止了代码

所以我们需要重载一个DFS的函数,遍历顶点集数组,查看是否有未被访问的节点,如果有,就立刻进行第一个版本的DFS

重载代码如下

void DFS_AL(ALGragh G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
		{
			DFS_AL(G, i);
		}
	}
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;

const int maxnum = 100;
bool visited[maxnum];
typedef char VexType;

struct AdjNode
{
	int v;
	AdjNode* next;
};

struct VexNode
{
	VexType data;
	AdjNode* first;
};

struct ALGragh
{
	VexNode Vex[maxnum];
	int edgenum, vexnum;
};

int locatevex(ALGragh G, VexType x)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (x == G.Vex[i].data)
		{
			return i;
		}
	}
	return -1;
}

void insertedge(ALGragh& G, int i, int j)
{
	AdjNode* s = new AdjNode;
	s->v = j;
	s->next = G.Vex[i].first;
	G.Vex[i].first = s;
}

void Print(ALGragh G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		AdjNode* t = G.Vex[i].first;
		cout << G.Vex[i].data << ": ";
		while (t != NULL)
		{
			cout << "[" << t->v << "] ";
			t = t->next;
		}
		cout << endl;
	}
}

void CreateALGraph(ALGragh& G)
{
	cout << "请输入顶点和边的个数" << endl;
	cin >> G.vexnum >> G.edgenum;
	cout << "请输入顶点的信息" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cin >> G.Vex[i].data;
		G.Vex[i].first = NULL;
	}
	cout << "请输入依次输入每条边所依附的两个顶点" << endl;
	while (G.edgenum--)
	{
		VexType u, v;
		cin >> u >> v;
		int i = locatevex(G, u);
		int j = locatevex(G, v);
		if (i != -1 && j != -1)
		{
			insertedge(G, i, j);
			//insertedge(G, j, i);
		}
		else
		{
			cout << "输入有误,重新输入" << endl;
			G.edgenum++;
		}

	}
}

void DFS_AL(ALGragh G, int v)
{
	int w;
	AdjNode* p;
	cout << G.Vex[v].data << " ";
	visited[v] = true;
	p = G.Vex[v].first;
	while (p)
	{
		w = p->v;
		if (!visited[w])
		{
			DFS_AL(G, w);
		}
		p = p->next;
	}
}

void DFS_AL(ALGragh G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
		{
			DFS_AL(G, i);
		}
	}
}

int main()
{

	ALGragh G;
	int v;
	VexType c;
	CreateALGraph(G);//创建有向图邻接表
	Print(G);//输出邻接表
	cout << "请输入遍历连通图的起始点：";
	cin >> c;
	v = locatevex(G, c);//查找顶点u的存储下标
	if (v != -1)
	{
		cout << "深度优先搜索遍历连通图结果：" << endl;
		DFS_AL(G, v);
	}
	else
		cout << "输入顶点信息错！请重新输入！" << endl;
	//DFS_AL(G);
	return 0;



	system("pause");
	return EXIT_SUCCESS;
}

非连通图的遍历