目录

1 前奏（邻接表）

2 深度遍历

3 广度遍历

1 前奏（邻接表）

图作为种比较繁琐的数据结构，在进行图的操作之前，首先应该用合适的数据类型来存储图的信息。

我们使用邻接表来存储，它是一种链式的存储结构。所谓邻接表就是对途中的每个顶点建立一个单链表。看一下下面的定义就明白了。

邻接表的定义如下：

//边
typedef struct ArcNode
{
	int adjvex;//该边所指向的节点的位置
	struct ArcNode* nextarc;//指向下一条边的指针
	int info;//存储边的相关信息，比如权重
}ArcNode;
//顶点
typedef struct VNode
{
	char data;//顶点信息
	ArcNode* firstarc;//指向第一条边的指针
}VNode；
//邻接表的定义
typedef struct AGraph
{
	VNode adjlist[MAXSIZE];//邻接表，里面存储着图种的所有顶点
	int n;//顶点的个数
	int e;//边的个数
}AGraph;

2 深度遍历

图的深度优先搜索遍历（DFS）类似于二叉树的先序遍历。它的基本思想是，从访问节点v出发，并将其标为已访问过，然后选取与v邻接的未被访问过的任何一个顶点w，并访问它，再选取与w邻接的未被访问的任一顶点并访问，以重复进行。当一个顶点所有的邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一个顶点并重复上述访问过程，直至所有的顶点都被访问过为止。

我们假设从顶点A出发开始访问，那么可能的访问序列有：

• A,D,C,E,B
• A,D,E,C,V
• A,C,D,B,E

不限于以上三种，这与图的邻接表有关。

接下来是代码的实现：

首先我们看一个连通图的深度优先搜索遍历：

int vist[MAXSIZE];//用于记录访问过的节点，0代表未访问，1代表已访问
//G为邻接表，v为起始节点
void DFS(AGraph* G, int v)
{
	ArcNode* p;
	vist[v] = 1;
	cout << v << endl;
	p = G->adjlist[v].firstarc;//p指向v节点的第一条边。
	while (p != NULL)
	{
		if (visit[p->adjvex] == 0)
			DFS(G, p->adjvex);//递归的进行访问
		p = p->nextarc;//指向下一条边
	}
}

上述的代码只适合连通图，如果一个图中有孤立的节点，即当这个图不是连通图的时，就应该从所有的节点开始进行遍历，如下：

void dfs(AGraph* g)
{
	for (int i = 0; i < g->n; ++i)
            if(visit[i]==0)
		DFS(g, i);
}

3 广度遍历

图的广度优先搜索遍历类似于树的层次遍历。它的基本思想是：首先访问起始顶点v,然后选取与v邻接的全部顶点进行访问，再依次访问邻接顶点的邻接顶点，以此类推，直至所有的顶点都被访问。

上述图从A出发，我们假设D,C,B分别是A指向的第一个、第二个和第三个节点,那么广度遍历的序列为：

A,D,C,B,E

连通图的广度遍历的代码如下所示：

void BFS(AGraph* G, int v, int visti[MAXSIZE])
{
	ArcNode* p;
	queue<int> que;
	cout << v << endl;
	visit[v] = 1;
	que.push(v);
	while (!que.empty())
	{
		int j = que.top();//得到队头元素
		que.pop();//出队
		p = G->adjlist[j].firstaec;
		while (p != NULL)
		{
			if (visit[] p->adjvex == 0)
			{
				cout << p->adjvex << endl;
				visit[p->adjvex] = 1;
				que.push(p->adjvex);
			}
			p = p->nextarc;//指向下一条边
		}
		
	}
}

上述代码是针对连通图的，那么对于非连通图，需要从不同的节点开始进行访问，充分考虑到孤立节点：

void bfs(AGraph* g)
{
	for (int i = 0; i < g->n; ++i)
            if(visit[i]==0)
		BFS(g, i);
}