# 数据结构之C++实现图的遍历（无主函数）

``````#include <iostream>
using namespace std;
#include <queue>

#define SIZE 10
struct Edge
{
int destvalue;
};
struct Vertex
{
Vertex():list(NULL){}
char data;
Edge *list;
};
{
public:
{
MaxVertex = SIZE;
NumVertex = NumEdge = 0;
VertexTable = new Vertex[MaxVertex];
}
void InsertVertex(char v)
{
if(NumVertex >= MaxVertex)
return;
VertexTable[NumVertex++].data = v;
}
int GetVertexI(char v)
{
for(int i = 0;i<NumVertex;i++)
{
if(VertexTable[i].data == v)
return i;
}
return -1;
}
void InsertEdge(char v1,char v2)
{
int p1 = GetVertexI(v1);
int p2 = GetVertexI(v2);
if(p1 == -1 || p2 == -1)
return;
Edge *ed = new Edge(p2);
VertexTable[p1].list = ed;

ed = new Edge(p1);
VertexTable[p2].list = ed;
NumEdge++;
}
void Show()
{
Edge *ed = NULL;
for(int i = 0;i<NumVertex;i++)
{
cout<<i<<":"<<VertexTable[i].data<<"->";
ed = VertexTable[i].list;
while(ed)
{
cout<<ed->destvalue<<"->";
}
cout<<"nul"<<endl;
}
}//前面各函数可参照上一篇博客 中的图邻接表
void BFS(char value)//广度优先遍历
{
queue<int> q;
int v = GetVertexI(value);
bool *visited = new bool[NumVertex];//标记数组，改节点是否被访问
Edge *ed = NULL;
int w;
for(int i = 0;i<NumVertex;i++)
visited[i] = false;
if(v == -1)
return;
cout<<value<<" ";//先输出第一个顶点
visited[v] = true;//将该顶点标志位赋为true
q.push(v);//将该顶点入队
while(!q.empty())//如果队列不空
{
v = q.front();//获取队头元素
q.pop();//出队
ed = VertexTable[v].list;
while(ed)//如果ed不为空
{
w = ed->destvalue;
if(!visited[w])
{
cout<<VertexTable[w].data<<" ";
q.push(w);
visited[w] = true;
}
}
}
}
void DFS(char v)//深度优先遍历
{
bool *visited = new bool[NumVertex];//标记数组，该节点是否被访问
for(int i = 0;i<NumVertex;i++)
visited[i] = false;
DFS(GetVertexI(v),visited);//从当前v位置开始遍历，对标识数据visited进行操作
delete [] visited;
visited = NULL;
}
char GetVertex(int v)
{
return VertexTable[v].data;
}
void DFS(int v,bool *visited)
{
cout<<GetVertex(v)<<" ";//先输出该顶点
visited[v] = true;//将该顶点标识位赋值true
int w = GetFirstNeighbor(v);//获取v的邻接顶点
while(w != -1)
{
if(!visited[w])//如果该邻接顶点没有被访问，则调用DFS
{
DFS(w,visited);
}
w = GetNextNeighbor(v,w);
}
}
int GetFirstNeighbor(int v) //获取v的第一个邻接点
{
if(v == -1)
return -1;
Edge *p = VertexTable[v].list;
if(p)
return p->destvalue;
return -1;
}
int GetNextNeighbor(int v,int w)//获取v的邻接点w的下一个邻接点
{
if(v == -1 || w== -1)
return -1;
Edge *p = VertexTable[v].list;//p指针指向v的邻接表
while(p && p->destvalue != w)//查找第一个邻接顶点的位置