图的深度和广度搜索算法

图是应用最为广泛的数据结构之一，图的搜索算法可以使我们发现图的很多结构信息。本文采用邻接表表示表，实现了图的深度和广度优先搜索算法（部分代码从网上参阅得来）。

第一步： 图的邻接表表示：

#include <iostream>
#include <stdlib.h>
#include <queue>

using namespace std;

// 邻接表表示
#define MAX_VERTEX_NUM 20   //最大顶点数
#define MAX_EDGE_NUM   40   //最大边数

int visited[MAX_VERTEX_NUM];

typedef int VertexType;           //顶点数据类型

typedef struct ArcNode
{
	int advex;                        //邻接点域
	int weight;                       //权值
	struct ArcNode *nextarc; //连接结点
	
}ArcNode;

typedef struct VNode
{
	VertexType data;
	ArcNode *firstarc;

}Vode, AdjList[MAX_VERTEX_NUM];

typedef struct
{
	AdjList vertices;
	int  vexnum, arcnum;
	int kind;
	
}ALGraph;

void CreateDG(ALGraph &G)
{

	int i, j, k;
	ArcNode *p;
	cout << "创建一个图: " << endl;
	cout << "顶点数: ";
	cin >> G.vexnum;
	cout << endl;

	cout << "边数: ";
	cin >> G.arcnum; 
	cout << endl;

	for (i = 0; i < G.vexnum; ++i)
	{

		G.vertices[i].data = i;
		G.vertices[i].firstarc = NULL;
	}

	for (k = 0; k < G.arcnum; ++k)
	{

		cout << "请输入第"<< k + 1 << "条边:";
		cin >> i >> j;

		p = new ArcNode();
		p->advex = j;
		
		p->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p;
	}

}

void Disp(ALGraph G)
{

	int i, j;
	ArcNode *p;
	cout << "输出图为:" << endl;
	
	for (i = 0; i < G.vexnum; ++i)
	{

		p = G.vertices[i].firstarc;
		j = 0;
		
		while(p != NULL)
		{

			cout << "(" << i << "," << p->advex << ")";
			p = p->nextarc;

			j = 1;

			
		}
		if (j == 1)

		cout << endl;
	}
}

 第二部分广度优先搜索和深度优先搜索

// 广度优先遍历图
void bfs(ALGraph G, int v)
{
   queue<VNode> q;
   q.push(G.vertices[v]);

   visited[v] = 1;

   VNode  vNode;   

   cout << v << " ";
   while (!q.empty())
   {
	  
		vNode = q.front();
		q.pop();

		ArcNode *p = vNode.firstarc;

		
		while(p != NULL)
		{
			if (visited[p->advex] == 0) 
			{
				cout << p->advex << " ";

				vNode.data = p->advex;
				vNode.firstarc = G.vertices[vNode.data].firstarc;
				q.push(vNode);
				
				visited[p->advex] = 1;

				p = p->nextarc;
			}
		}
   }


}
// 深度优先遍历图
void  dfs(ALGraph G, int v)
{
	ArcNode *p;

	cout << v << " ";
	visited[v] = 1;
	p = G.vertices[v].firstarc;

	while (p != NULL)
	{

		if (! visited[p->advex])
			dfs(G, p->advex);

		p = p->nextarc;
	}

	return;
}


void dfs1(ALGraph G)
{
	int i;

	for (i = 0; i < G.vexnum; ++i)
		if (visited[i] == 0)
			dfs(G, i);
}

 最后一步，代码测试：

void main()
{
        ALGraph G;
	CreateDG(G);

	int v;
	Disp(G);

	cout << "输入源顶点: ";
	cin >> v;
	
	cout << "选择遍历方式: " << endl;
	cout << "1 深度优先搜索 \t2 广度优先搜索" << endl;

	int flag;
	cin >> flag;
        if (flag == 1)
		dfs1(G);

	if (flag == 2)
		bfs(G, v);
  
       cout << endl;	
}

 就大功告成了。