///////////////////////////////////////////////////////////////
//图的邻接表表示法以及DFS和BFS
///////////////////////////////////////////////////////////////
#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;
//图的邻接表表示法
#define MaxVertexNum 100
enum GraphType{DG, UG, DN, UN};//有向图，无向图，有向网图，无向网图 typedef struct node
{
int AdjV; //邻接点域
struct node *Next; //指向下一个邻接点的指针域
//若要表示边上的权值信息，则应增加一个数据域Weight
}EdgeNode; //边表节点 typedef char VertexType; //顶点用字符表示
typedef struct Vnode
{
VertexType Vertex; //顶点域
EdgeNode *FirstEdge; //边表头指针
}VertexNode; typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct
{
AdjList adjlist; //邻接表
int n, e; //顶点数和边数
enum GraphType GType; //图的类型
}ALGraph; //ALGraph是以邻接表方式存储的图类型 void CreateALGraph(ALGraph *G)
{
int i, j, k;
EdgeNode *edge;
G->GType = UG; //有向图
cout << "请输入顶点数和边数（输入格式为：顶点数，边数）:\n" << endl;
cin >> G->n >> G->e; //读入顶点数和边数
cout << "请输入顶点信息（输入格式为：顶点号<CR>):\n";
for (i = ; i < G->n; i++)
{//建立有n个顶点的顶点表
cin >> &G->adjlist[i].Vertex; //读入顶点信息
G->adjlist[i].FirstEdge = NULL; //顶点的边表头指针设为空
}
cout << "请输入边的信息(输入格式为：i,j<CR>):\n";
for (k = ; k < G->e; k++) //建立边表
{
cin >> i >> j;
edge = new EdgeNode;
edge->AdjV = j;
edge->Next = G->adjlist[i].FirstEdge;
//将新边表节点edge插入到顶点vi的边表头部
G->adjlist[i].FirstEdge = edge;
//若是无向图，还要生成一个节点，用来表示边<vj, vi>
EdgeNode *edge2 = new EdgeNode;
edge2->AdjV = i;
edge2->Next = G->adjlist[j].FirstEdge;
G->adjlist[j].FirstEdge = edge2;
}
} //邻接表存储的图--DFS
//visited[]为全局变量，已经初始化为false
bool Visited[MaxVertexNum] = { false };
void DFS(ALGraph *G, int i)
{
//以vi为出发点对邻接表存储的图G进行DFS搜索
EdgeNode *W;
cout << "visit vertex:" << G->adjlist[i].Vertex << " ";
//相当于访问顶点vi
Visited[i] = true;
for (W = G->adjlist[i].FirstEdge; W; W = W->Next)
if (!Visited[W->AdjV])
DFS(G, W->AdjV);
} //邻接表存储的图--DFS
//visited[]为全局变量，已经初始化为false
void BFS(ALGraph *G ,int i)
{
queue<VertexNode> Q;
Q.push(G->adjlist[i]);
Visited[i] = true; //依次入队列,每次取出下一个要访问的节点
while (!Q.empty())
{
VertexNode tmp = Q.front();
cout << tmp.Vertex << " ";
Q.pop();
EdgeNode *p = tmp.FirstEdge;
while (p != NULL)
{
if (Visited[p->AdjV] != true)
{
Q.push(G->adjlist[p->AdjV]);
Visited[p->AdjV] = true;
}
p = p->Next;
}
}
} void Print(ALGraph *G)
{
for (int i = ; i < G->n; i++)
{
EdgeNode *p = G->adjlist[i].FirstEdge;
cout << G->adjlist[i].Vertex << " ";
while (p != NULL)
{
cout << p->AdjV << " ";
p = p->Next;
}
cout << endl;
}
} int main()
{
ALGraph *G = new ALGraph;
CreateALGraph(G);
Print(G);
//DFS(G, 0);
BFS(G, );
system("pause");
return ;
}
测试结果：
