图的构建及遍历,邻接表,BFS,DFS

代码:

#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;
}

输出结果:图的构建及遍历,邻接表,BFS,DFS

上一篇:Redis配置文件详解


下一篇:K8S 存储卷