#include<iostream> #include<string> #include<fstream> using namespace std; const int MAXL = 20; //结点信息 struct Node { string data;//结点值 int no;//结点编号 Node(string data):data(data),no(0){} Node() { data = ""; no = 0; } }; //边结点 struct EdgeNode { Node nextnode;//终止结点信息 EdgeNode* nextedge;//下一条邻接边 EdgeNode(string s) { this->nextnode.data = s; this->nextnode.no = 0; this->nextedge = NULL; } EdgeNode() { this->nextnode.data = ""; this->nextnode.no = 0; this->nextedge = NULL; } }; //表头结点 struct HNode { Node hnode;//起始结点信息 EdgeNode* firstedge;//第一条邻接边 HNode(string s) { hnode.data = s; hnode.no = 0; firstedge = NULL; } HNode() { hnode.data = ""; hnode.no = 0; firstedge = NULL; } }; //邻接表 struct ALGraph { int n, e;//分别表示顶点数和边数 HNode hnode[MAXL];//头结点数组 ALGraph() { n = e = 0; for (int i = 0; i < MAXL; i++) hnode[i].firstedge = NULL; } };
时间: 2024-02-14 08:23:20 浏览: 66
好的,下面是一个使用邻接表实现的图的遍历算法,可以参考一下:
//深度优先遍历DFS
void DFS(ALGraph& G, int v, bool visited[])
{
visited[v] = true;//标记结点v已被访问
cout << G.hnode[v].hnode.data << " ";//输出结点v的值
EdgeNode* e = G.hnode[v].firstedge;//获取结点v的第一条邻接边
while (e != NULL)//访问结点v的所有邻接点
{
int w = e->nextnode.no;//获取终止结点的编号
if (!visited[w])//若终止结点未被访问,则继续递归遍历
DFS(G, w, visited);
e = e->nextedge;//获取结点v的下一条邻接边
}
}
//广度优先遍历BFS
void BFS(ALGraph& G, int v, bool visited[])
{
queue<int> Q;//定义队列Q
visited[v] = true;//标记结点v已被访问
cout << G.hnode[v].hnode.data << " ";//输出结点v的值
Q.push(v);//将结点v入队
while (!Q.empty())//当队列不为空时进行遍历
{
int w = Q.front();//获取队首结点w
Q.pop();//将队首结点w出队
EdgeNode* e = G.hnode[w].firstedge;//获取结点w的第一条邻接边
while (e != NULL)//访问结点w的所有邻接点
{
int u = e->nextnode.no;//获取终止结点的编号
if (!visited[u])//若终止结点未被访问,则标记已访问并入队
{
visited[u] = true;
cout << G.hnode[u].hnode.data << " ";//输出结点u的值
Q.push(u);//将结点u入队
}
e = e->nextedge;//获取结点w的下一条邻接边
}
}
}
阅读全文