代码:
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
#define MaxInt 32767 //表示极大值
#define MAXVEX 100 //最大顶点数
#define OK 1
#define ERROR 0
typedef int status;
typedef int Boolean;//Boolean是布尔类型,其值是true或False
Boolean visited[MAXVEX];//访问标志的数组
typedef char VertextType;//顶点类型
typedef int EdgeType;//边上的权值类型
typedef struct EdgeNode{//边表结点
int adjvex;//邻接点域,存储该顶点对应的下标
EdgeType weight;//用于存储权值
struct EdgeNode *next;//链域,指向下一个邻接点
}EdgNode;
typedef struct VertextNode {//顶点表结点
VertextType data;//顶点域,存储顶点信息
EdgeNode *firstedge;//边表头指针
}VertexNode, AdjList[MAXVEX];
typedef struct {
AdjList adjList;
int numVertexes, numEdges;//图中当前顶点数和边数
}GraphAdjList;
//建立图的邻接表结构
void CreateALGraph(GraphAdjList *G){
int i, j, k, w;
EdgeNode *e;
cout << "请输入顶点数和边数:" << endl;
cin >> G->numVertexes >> G->numEdges;//输入顶点数和边数
cout << "输入顶点信息" << endl;
for (i = 0; i < G->numVertexes; i++){
cin >> G->adjList[i].data;//输入顶点信息
G->adjList[i].firstedge = NULL;//将边表置为空表
}//for
for (k = 0; k < G->numEdges; k++){
cout << "输入边(Vi,Vj)上的顶点序号及权重" << endl;
cin >> i >> j >> w;//输入边(vi,vj)上的顶点序号及权重
e = (EdgeNode *)malloc(sizeof(EdgeNode));//向内存申请空间生成边表结点
e->adjvex = j;
e->weight = w;
e->next = G->adjList[i].firstedge;//将e指针指向当前顶点指向的结点
G->adjList[i].firstedge = e;//将当前顶点的指针指向e--------头插法
e = (EdgeNode *)malloc(sizeof(EdgeNode));//向内存申请空间,生成边表结点
e->adjvex = i;//邻接序号为i
e->next = G->adjList[j].firstedge;//将e指针指向当前顶点指向的结点
G->adjList[j].firstedge = e;//将当前顶点的指针指向e
}//for
}
//邻接表的深度优先递归算法
void DFS(GraphAdjList GL, int i) {
EdgeNode *p;
visited[i] = 1;
cout << GL.adjList[i].data << " ";//打印顶点,也可以其他操作
p = GL.adjList[i].firstedge;
while (p) {
if (!visited[p->adjvex])
DFS(GL, p->adjvex);//对未访问的邻接顶点递归调用
p = p->next;
}
}
//邻接表的深度遍历操作
void DFSTraverse(GraphAdjList GL) {
int i;
for (i = 0; i < GL.numVertexes; i++) {
visited[i] = 0;//初始所有顶点状态都是未访问过状态
}
for (i = 0; i < GL.numVertexes; i++) {
if (!visited[i])//对未访问过的顶点调用DFS,若是连通图,只会执行一次
DFS(GL, i);
}
}
//邻接表的广度优先递归算法
void BFSTraverse(GraphAdjList GL) {
int i;
EdgeNode *p;
queue<int> Q;
for (i = 0; i < GL.numVertexes; i++)
visited[i] = 0;
for (i = 0; i < GL.numVertexes; i++) {
if (!visited[i]) {
visited[i] = 1;
cout << GL.adjList[i].data << " ";//打印顶点,也可以是其他操作
Q.push(i);
while (!Q.empty()) {
i = Q.front();
Q.pop();
p = GL.adjList[i].firstedge;//找到当前顶点边表链表头指针
while (p) {
if (!visited[p->adjvex])//若此顶点未被访问
{
visited[p->adjvex] = 1;
cout << GL.adjList[p->adjvex].data << " ";
Q.push(p->adjvex);//将此顶点入队列
}//if
p = p->next;//指针指向下一个邻接点
}//while
}//while
}//if
}//for
}//BFS
int main()
{
GraphAdjList *GL = (GraphAdjList*)malloc(sizeof(GraphAdjList));
char ch1,ch2;
ch1 = ‘y‘;
while (ch1 == ‘y‘)
{
cout << "----------图的构建和遍历----------" << endl;
cout << "------1.图的构建 ------" << endl;
cout << "------2.图的深度优先搜索遍历 ------" << endl;
cout << "------3.图的广度优先搜索遍历 ------" << endl;
cout << "------4.dijkstra‘s algorithm ------" << endl;
cout << "------0.退出 ------" << endl;
cout << "------请选择菜单号 ------" << endl;
cin >> ch2;
getchar();
cout << endl;
switch(ch2)
{
case‘1‘:
//图的构建
CreateALGraph(GL);;
break;
case‘2‘:
//图的深度优先搜索遍历
DFSTraverse(*GL);
cout << endl;
break;
case‘3‘:
//图的广度优先搜索遍历
BFSTraverse(*GL);
cout << endl;
break;
case ‘4‘:
//Dijkstra算法
break;
case‘0‘:
ch1 = ‘n‘;
break;
default:
cout << "输入有误" << endl;
}//switch
}//while
return 0;
}
输出结果: