图算法实现及其应用C++

数据结构课程设计之图算法实现及其应用

实现了三个图的主要算法：

1.深度优先搜索遍历和广度优先搜索遍历

2.最小生成树

3.AOE网的关键路径（其中包含利用拓扑排序判断有向网是否存在环）

在实现图的遍历的代码中，我们使用邻接矩阵来存储无向图，以完成图的深度优先搜索遍历和广度优先搜索遍历。

在广度优先搜索遍历中，我们需要使用到队列的数据结构，但为了突出图的算法以及代码整体的简洁性，我们在头文件中#include。使得整体代码更加简洁。

//采用邻接矩阵表示无向图的深度优先搜索遍历和广度优先遍历 

#include 
#include 
#define MAXQSIZE 100						//最大队列长度
#define MAX 100						     	//最大顶点数
using namespace std;

typedef char VerTexType;					//顶点数据类型为char 
typedef int ArcType;                 		//权值数据类型为int 


typedef struct{ 
	VerTexType vexs[MAX];            		//顶点表 
	ArcType arcs[MAX][MAX];      		    //邻接矩阵 
	int vexnum,arcnum;                		//图的当前点数和边数 
}Graph;

bool visited[MAX];           				//访问标志数组，其初值为"false" 
int FirstAdjVex(Graph G , int v);			//返回v的第一个邻接点
int NextAdjVex(Graph G , int v , int w);	//返回v相对于w的下一个邻接点

int LocateVex(Graph G , VerTexType v){
	//确定点v在G中的位置
	for(int i = 0; i < G.vexnum; ++i)
		if(G.vexs[i] == v)
			return i;
		return -1;
}//LocateVex

void CreateUDN(Graph &G){ 
    //采用邻接矩阵表示法，创建无向网G 
	int i , j , k;
	cout <<"请输入总顶点数，总边数，以空格隔开:";
    cin >> G.vexnum >> G.arcnum;							//输入总顶点数，总边数
	cout << endl;
	
	cout << "输入点的名称，如a" <> G.vexs[i];                        			//依次输入点的信息 
	}	
	cout << endl;

    for(i = 0; i < G.vexnum; ++i)                			//初始化邻接矩阵，边的权值均置为0 
		for(j = 0; j < G.vexnum; ++j)   
			G.arcs[i][j] = 0;  
	cout << "输入边依附的顶点，如a b" << endl;
	for(k = 0; k < G.arcnum;++k){							//构造邻接矩阵 
		VerTexType v1 , v2;
		cout << "请输入第" << (k + 1) << "条边依附的顶点:";
		cin >> v1 >> v2;									//输入一条边的始点和终点 
		i = LocateVex(G, v1);  j = LocateVex(G, v2);		//确定v1和v2在G中的位置，即顶点数组的下标 
		G.arcs[j][i] = G.arcs[i][j] = 1;					//设置这条边的始点和终点的权值为1 
	}//for
}//CreateUDN 

void DFS(Graph G, int v){        		
	//图G为邻接矩阵类型 
	int w;
	cout << G.vexs[v] << "    ";  visited[v] = true;  		//访问第v个顶点，并置访问标志数组相应分量值为true 
	for(w = 0; w < G.vexnum; w++)  							//依次检查邻接矩阵v所在的行  
		if((G.arcs[v][w] != 0)&& (!visited[w]))  DFS(G, w); //G.arcs[v][w]!=0表示w是v的邻接点，如果w未访问，则递归调用DFS 
}//DFS
void BFS (Graph G, int v){ 
    //按广度优先非递归遍历连通图G 
	queue que;
	ArcType u;
	ArcType w;

    cout << G.vexs[v] << "  ";    visited[v] = true;     						//访问第v个顶点，并置访问标志数组相应分量值为true       
    que.push(v);            													//v进队 
    while(!que.empty()){   													//队列非空 
		int u=que.front();
		que.pop();       													//队头元素出队并置为u
		for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)){
			//依次检查u的所有邻接点w ，FirstAdjVex(G, u)表示u的第一个邻接点 
			//NextAdjVex(G, u, w)表示u相对于w的下一个邻接点，w≥0表示存在邻接点 
			if(!visited[w]){	           										//w为u的尚未访问的邻接顶点 
				cout << G.vexs[w] << "  ";   visited[w] = true;					//访问w，并置访问标志数组相应分量值为true 
				que.push(w);											//w进队 
			}//if 
		}//for
    }//while 
}//BFS 
int FirstAdjVex(Graph G , int v){
	//返回v的第一个邻接点
	int i;
	for(i = 0 ; i < G.vexnum ; ++i){
		if(G.arcs[v][i] == 1 && visited[i] == false)
			return i;
	}
	return -1;
}//FirstAdjVex

int NextAdjVex(Graph G , int v , int w){
	//返回v相对于w的下一个邻接点
	int i;
	for(i = w ; i < G.vexnum ; ++i){
		if(G.arcs[v][i] == 1 && visited[i] == false)
			return i;
	}
	return -1;
}//NextAdjVex

int main(){
	cout << "************采用邻接矩阵表示图的深度优先搜索遍历和广度优先搜索遍历**************" << endl << endl;
	Graph G;
	CreateUDN(G);
	cout << endl;
	cout << "无向图G创建完成！" << endl << endl;
	
	cout << "请输入遍历无向图G的起始点：";
	VerTexType c;
	cin >> c;

	int i;
	for(i = 0 ; i < G.vexnum ; ++i){
		if(c == G.vexs[i])
			break;
	}
	cout << endl;
	while(i >= G.vexnum){
		cout << "该点不存在，请重新输入！" << endl;
		cout << "请输入遍历连通图的起始点：";
		cin >> c;
		for(i = 0 ; i < G.vexnum ; ++i){
			if(c == G.vexs[i])
				break;
		}
	}
	int choice;
	cout<<"请选择进行深度优先搜索遍历还是广度优先搜索遍历，1为深度，0为广度"<>choice;
	if(choice) {
	cout << "深度优先搜索遍历无向图G结果：" << endl;
	DFS(G , i);	
	}else{
	cout << "广度优先搜索遍历无向图G结果：" << endl;
	BFS(G , i);
	}




	cout < 
 
在实现求最小生成树的代码中，我们使用的是克鲁斯卡尔算法，用以求解无向网G的最小生成树。（无向网是带权的无向图） 
 
在这里我们同样采用邻接矩阵的存储方式来存储无向网。
 
求最小生成树的步骤：
 
第一步是将无向网中的所有边按照权值大小做升序排序。
 
第二步是构造最小生成树 。
 
 
第一步，在对无向网中的所有边的权值按照大小做升序排序的时候，我们利用了冒泡排序。正常情况下冒泡排序的时间复杂度最好、平均、最坏均为O（n^2）。但我们在算法中加入了一个flag标记，可以使得在已经排好序的情况下，最好的时间复杂度为O(n）。
 
 
第二步，我们利用辅助数组给每一个顶点赋一个连通分量，然后依次查看排好序的数组Edge中的边是否在同一连通分量上，若边的始点和终点若不是同一连通分量，那么说明两个点不是连通的。那么我们就可以输出此边，然后将该边的两个点的连通分量设为同一个，即两个点已经连通。 
 
//克鲁斯卡尔算法求无向网G的最小生成树 
//第一步：将无向网中的所有边按照权值大小做升序排序。
//第二步：构造最小生成树 
 

#include 
using namespace std;

typedef char VerTexType;              		//顶点数据类型为char
typedef int ArcType;                        //权值数据类型为int 
#define MAX 100                       	    //最大顶点数
#define MaxInt 32767                    	//表示极大值，即∞

 
typedef struct{ 
	VerTexType vexs[MAX];            		//顶点表 
	ArcType arcs[MAX][MAX];      		    //邻接矩阵 
	int vexnum,arcnum;                		//图的当前点数和边数 
}AMGraph;

//辅助数组Edges的定义
struct{
	VerTexType Head;						//边的始点
	VerTexType Tail;						//边的终点
	ArcType lowcost;						//边上的权值
}Edge[(MAX * (MAX - 1)) / 2];

int Vexset[MAX];							//辅助数组Vexset的定义（连通分量） 

int LocateVex(AMGraph G , VerTexType v){
	//确定点v在G中的位置
	for(int i = 0; i < G.vexnum; ++i)
		if(G.vexs[i] == v)
			return i;
		return -1;
}//LocateVex

void CreateUDN(AMGraph &G){ 
    //采用邻接矩阵表示法，创建无向网G 
	int i , j , k;
	cout <<"请输入总顶点数，总边数，以空格隔开:";
    cin >> G.vexnum >> G.arcnum;						//输入总顶点数，总边数
	cout << endl;
	
	cout << "输入点的名称，如a" << endl;

    for(i = 0; i < G.vexnum; ++i){   
		cout << "请输入第" << (i+1) << "个点的名称:";
		cin >> G.vexs[i];                        		//依次输入点的信息 
	}
	cout << endl;
	for(i = 0; i < G.vexnum; ++i)                		//初始化邻接矩阵，边的权值均置为极大值MaxInt 
		for(j = 0; j < G.vexnum; ++j) 
			G.arcs[i][j] = MaxInt; 
	cout << "输入边依附的顶点及权值，如a b 6" << endl;
	for(k = 0; k < G.arcnum;++k){						//构造邻接矩阵 
		VerTexType v1 , v2;
		ArcType w;
		cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:";
		cin >> v1 >> v2 >> w;                           //输入一条边的两个顶点以及对应的权值
		i = LocateVex(G, v1);  j = LocateVex(G, v2);	//确定两个顶点v1和v2在G中的位置，即顶点数组的下标 
		G.arcs[i][j] = w;								//将边的权值置为w 
		G.arcs[j][i] = G.arcs[i][j];					//置的对称边的权值为w （无向网的邻接矩阵关于对线线对称）
		//给Edge数组赋值 
		Edge[k].lowcost = w;
		Edge[k].Head = v1;
		Edge[k].Tail = v2;
	}//for
}//CreateUDN 

//对图G中的边Edge进行冒泡排序 
//这里的冒泡排序在算法中加入了flag标记,在已经排好序的情况下，最好的时间复杂度为O(n). 
void Sort(AMGraph G){
	int m = G.arcnum - 2;//边数-2 
	int flag = 1;
	while((m > 0) && flag == 1){
		flag = 0;
		for(int j = 0 ; j <= m ; j++){
			//如果边[j]的权值大于边[j+1]的权值 
			if(Edge[j].lowcost > Edge[j+ 1].lowcost){
				flag = 1;
                //那么就交换两条边的始点，终点以及权值 
				VerTexType temp_Head = Edge[j].Head;
				Edge[j].Head = Edge[j+ 1].Head;
				Edge[j + 1].Head = temp_Head;
				

				VerTexType temp_Tail = Edge[j].Tail;
				Edge[j].Tail = Edge[j+ 1].Tail;
				Edge[j + 1].Tail = temp_Tail;
				
				ArcType temp_lowcost = Edge[j].lowcost;
				Edge[j].lowcost = Edge[j+ 1].lowcost;
				Edge[j + 1].lowcost = temp_lowcost;
			}//if
		}//for
		--m;
	}//while
}//Sort
//求最小生成树的函数 
void MiniSpanTree_Kruskal(AMGraph G){ 
    //无向网G以邻接矩阵形式存储，构造G的最小生成树T，输出T的各条边     
    int i , j , v1 , v2 , vs1 , vs2;
    //第一步将连通网中的所有边按照权值大小做升序排序 
	Sort(G);                 							//升序排序Edge数组。 
	for(i = 0; i < G.vexnum; ++i)     					//辅助数组，给每个顶点赋一个连通分量 
        Vexset[i] = i;
    for(i = 0; i < G.arcnum; ++i){      
		//依次查看排好序的数组Edge中的边是否在同一连通分量上     
		v1 =LocateVex(G, Edge[i].Head);     			//边的始点的下标 
		v2 =LocateVex(G, Edge[i].Tail);     			//边的终点的下标 
		vs1 = Vexset[v1];       						//边的始点的连通分量vs1 
		vs2 = Vexset[v2];       						//边的终点的连通分量vs2 
		if(vs1 != vs2){         						//边的始点和终点若不是同一连通分量，那么说明两个点不是连通的。 
			cout << Edge[i].Head << "-->" << Edge[i].Tail << endl;		//输出此边 
			for(j = 0; j < G.vexnum; ++j)      			//
				if(Vexset[j] == vs2) Vexset[j] = vs1;	//将两个点的连通分量设为同一个，即两个点已经连通。 
		}
    }
}

int main(){
	cout << "克鲁斯卡尔算法求无向网的最小生成树" << endl << endl;
	AMGraph G;
	CreateUDN(G);
	
	cout < 
 
 
在实现求AOE网（AOE网，即有向无环带权的网）的关键路径的代码中，我们采用邻接表和逆邻接表的存储方式来存储有向网（之所以采用邻接表和逆邻接表的存储方式来存储有向网，是因为采用邻接表和逆邻接表的存储方式存储，可以更加轻松地计算出有向网中各个顶点的入度，这样有利于拓扑排序） 。
 
 
求AOE网的关键路径的步骤：
 第一步：求出有向网中各顶点的入度并存入数组indegree中 。
 
第二步：进行拓扑排序，获得拓扑序列，判断有向网是否存在回路
 
1）选择一个 没有前驱（即入度为0）的顶点并输出。
 2）删除该顶点和所有以它为起点的有向边，即把该顶点的每一个邻接点的入度减1。 
 3）重复1和2直到当前的图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
 
第三步：求AOE网的关键路径，
 
1）我们调用拓扑排序，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR。
 
2）按拓扑次序求每个事件的最早发生时间，按逆拓扑次序求每个事件的最迟发生时间。
 
3）判断每一活动是否是关键活动。在这里我们需要计算活动的最早开始时间 和活动的最迟开始时间 ，当活动的最早开始时间等于活动的最迟开始时间，则说明该活动为关键活动，输出 。
 
//aoe网求关键路径    aoe网（有向无环带权的网）   利用拓扑排序判断是否有环    
//邻接表（计算出度），逆邻接表（计算入度） 

#include 
#include
using namespace std;

#define MVNum 100                       	//最大顶点数
#define BDNum MVNum * (MVNum - 1)			//最大边数
#define OK 1	
#define ERROR 0 

typedef char VerTexType;

//邻接表 
typedef struct ArcNode{                		//边结点 
    int adjvex;                          	//该边所指向的顶点的位置
	int weight;								//权值
    struct ArcNode *nextarc;          		//指向下一条边的指针 
}ArcNode; 

typedef struct VNode{ 
    VerTexType data;                    	//顶点信息
    ArcNode *firstarc;                		//指向第一条依附该顶点的边的指针 
}VNode, AdjList[MVNum];               		//AdjList表示邻接表类型 

typedef struct{ 
    AdjList vertices;                 		//邻接表 
	AdjList converse_vertices;				//逆邻接表
    int vexnum, arcnum;              		//图的当前顶点数和边数 
}ALGraph;
//- - - - - - - - - - - - - - - -
int indegree[MVNum];						//数组indegree存放个顶点的入度
int ve[BDNum];								//事件vi的最早发生时间
int vl[BDNum];								//事件vi的最迟发生时间
int topo[MVNum];							//记录拓扑序列的顶点序号
int LocateVex(ALGraph G , VerTexType v){
	//确定点v在G中的位置
	for(int i = 0; i < G.vexnum; ++i)
		if(G.vertices[i].data == v)
			return i;
		return -1;
}//LocateVex
int CreateUDG(ALGraph &G){ 
	//创建有向图G的邻接表、逆邻接表
	int i , k;
	
	cout <<"请输入总顶点数，总边数，以空格隔开:";
	cin >> G.vexnum >> G.arcnum;				//输入总顶点数，总边数 
    cout << endl;

	cout << "输入点的名称，如a" << endl;
	
	for(i = 0; i < G.vexnum; ++i){          		//输入各点，构造表头结点表
		cout << "请输入第" << (i+1) << "个点的名称:";
		cin >> G.vertices[i].data;           		//输入顶点信息 
		G.converse_vertices[i].data = G.vertices[i].data;
		//初始化表头结点的指针域为NULL 
		G.vertices[i].firstarc=NULL;			
		G.converse_vertices[i].firstarc=NULL;
    }//for
	cout << endl;

	cout << "输入边依附的顶点及其权值，如a b 3" << endl;

	for(k = 0; k < G.arcnum;++k){        			//输入各边，构造邻接表
		VerTexType v1 , v2;
		int i , j , w;
		cout << "请输入第" << (k + 1) << "条边依附的顶点及其权值:";
		cin >> v1 >> v2 >> w;                		//输入一条边依附的两个顶点
		i = LocateVex(G, v1);  j = LocateVex(G, v2);
		//确定v1和v2在G中位置，即顶点在G.vertices中的序号 

		ArcNode *p1=new ArcNode;               		//生成一个新的边p1 
		p1->adjvex=j;                   			//邻接点序号为j
		p1->nextarc = G.vertices[i].firstarc;  
		G.vertices[i].firstarc=p1;
		p1->weight = w;
		//将新结点*p1插入顶点vi的边表头部

		ArcNode *p2=new ArcNode;               		//生成一个新的边结点*p2 
		p2->adjvex=i;                   			//逆邻接点序号为i
		p2->nextarc = G.converse_vertices[j].firstarc;  
		G.converse_vertices[j].firstarc=p2;
		p2->weight = w;
		//将新结点*p2插入顶点vi的边表头部
    }//for 
    return OK; 
}//CreateUDG

//求出各顶点的入度存入数组indegree中 
void FindInDegree(ALGraph G){
	
	int i , count;
    //遍历图中各顶点，求出各顶点的入度（利用逆邻接表） 
	for(i = 0 ; i < G.vexnum ; i++){
		count = 0;
		ArcNode *p = G.converse_vertices[i].firstarc;
		if(p){
			while(p){
				p = p->nextarc;
				count++;
			}
		}
		indegree[i] = count;
	}
}




//拓扑排序：判断是否存在回路 
//1.选择一个 没有前驱（即入度为0）的顶点并输出。
//2.删除该顶点和所有以它为起点的有向边，即把该顶点的每一个邻接点的入度减1。 
//3.重复1和2直到当前的图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。


//伪代码：
//        第一步，把入度为0的顶点的位置压入栈中。
//        第二步，依次拿出入度为0的顶点的位置，删除该顶点，并求该顶点的邻接点的入度为0的个数，并且压入栈中。直到该顶点的邻接点为空。
//        重复第二步。 
int TopologicalOrder(ALGraph G , int topo[]){ 
    //有向图G采用邻接表存储结构 
    //若G无回路，则生成G的一个拓扑序列topo[]并返回OK，否则ERROR 
	int i , m;
    FindInDegree(G);              				//求出各顶点的入度存入数组indegree中 
    stack st;                          		//栈S初始化为空 
    for(i = 0; i < G.vexnum; ++i)
		if(!indegree[i]) st.push(i);     		//入度为0者进栈 
	m = 0;                               		//对输出顶点计数，初始为0 
	while(!st.empty()){                		//栈S非空 
		i=st.top();  
		st.pop();                                //将栈顶顶点vi出栈
		topo[m]=i;                         		//将vi保存在拓扑序列数组topo中 
		++m;                             		//对输出顶点计数 
		ArcNode *p = G.vertices[i].firstarc;    //p指向vi的第一个邻接点 
		while(p){
			int k = p->adjvex;					//vk为vi的邻接点   
			--indegree[k];                   	//vi的每个邻接点的入度减1，即删除该顶点。 
			if(indegree[k] ==0)  st.push(k);	//若入度减为0，则入栈 
			p = p->nextarc;                		//p指向顶点vi下一个邻接结点 
		}//while 
	}//while
	
	if(m < G.vexnum)  return ERROR;    			//该有向图有回路 
	else return OK;
}//TopologicalOrder
//求关键路径 
int CriticalPath(ALGraph G){ 
    //G为邻接表存储的有向网，输出G的各项关键活动
	int n , i , k , j , e , l;
    if (!TopologicalOrder(G, topo))  return ERROR; 
    //调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR 
    n = G.vexnum;                  				//n为顶点个数 
    for(i = 0; i < n; i++)               		//给每个事件的最早发生时间置初值0 
		ve[i] = 0; 


   //按拓扑次序求每个事件的最早发生时间
    for(i = 0;i < n; i++){                 
		k = topo[i];                   			//取得拓扑序列中的顶点序号k             
		ArcNode *p = G.vertices[k].firstarc;    //p指向k的第一个邻接顶点  
		while(p != NULL){            			//依次更新k的所有邻接顶点的最早发生时间   
			j = p->adjvex;               		//j为邻接顶点的序号                   
			if(ve[j] < ve[k] + p->weight)    	//更新顶点j的最早发生时间ve[j] 
				ve[j] = ve[k] + p->weight;     
			p = p->nextarc;              		//p指向k的下一个邻接顶点  
		} //while 
    } //for 

    for(i=0;i= 0; i--){               
		k = topo[i];                   			//取得拓扑序列中的顶点序号k             
		ArcNode *p = G.vertices[k].firstarc;    //p指向k的第一个邻接顶点  
		while(p != NULL){            			//根据k的邻接点，更新k的最迟发生时间   
			j = p->adjvex;              		//j为邻接顶点的序号                   
			if(vl[k] > vl[j] - p->weight)    	//更新顶点k的最迟发生时间vl[k] 
				vl[k] = vl[j] - p->weight;       
			p = p->nextarc;              		//p指向k的下一个邻接顶点  
		}//while 
    }//for 

    
	cout << endl;
	cout << "关键活动路径为:";
    for(i = 0;i < n; i++){                		//每次循环针对vi为活动开始点的所有活动 
        ArcNode *p = G.vertices[i].firstarc;    //p指向i的第一个邻接顶点  
        while(p != NULL) {    
			j = p->adjvex;             			//j为i的邻接顶点的序号    
			e = ve[i];                 			//计算活动的最早开始时间 
			l = vl[j] - p->weight;      		//计算活动的最迟开始时间 
			if(e == l)               			//若为关键活动，则输出 
				cout << G.vertices[i].data << "-->" << G.vertices[j].data << " ";
			p = p->nextarc;              		//p指向i的下一个邻接顶点  
		} //while 
	} //for  
	return OK;
}//CriticalPath

int main(){
	cout << "************关键路径算法**************" << endl << endl;
	ALGraph G;
	CreateUDG(G);
	int *topo = new int [G.vexnum];
	
	cout << endl;
	cout << "有向图创建完成!" << endl << endl;
	
	if(!CriticalPath(G))
		cout << "网中存在环，无法进行拓扑排序！" <