有向图的邻接矩阵.cpp

数据结构课程设计 有向图的邻接矩阵 语言：C

#include <iostream.h>
#include "stdlib.h"
#define MAXvex 10
#define M   20
typedef char vextype;
typedef int  adjtype;
typedef struct {
	vextype vexs[MAXvex];
	adjtype arcs[MAXvex][MAXvex];
	int vexnum,arcnum;
}Graph;

//返回字符u的位置
int LocateVex(Graph G,char u)        
{	
	int i;
	int n=G.vexnum;
	for (i=0;i<n;i++)
	{
		if (u==G.vexs[i])
			return i;
	}
	if (i==n) 
	{  
		cout<<"Error u!"<<endl;
		exit(1);
	}
	return 0;
} 

//有向图的邻接矩阵
void createDG( Graph &G)
{
	int i,j,k,v3;
	vextype v1,v2;
	cout<<"请输入有向图的顶点数和弧数:"<<endl;
	cin>>G.vexnum>>G.arcnum;
	cout<<"请输入有向图的各顶点:"<<endl;
	for(i=0;i<G.vexnum;i++)
		cin>>G.vexs[i];
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
			G.arcs[i][j]=0;
		cout<<"请输入每条弧对应的两个顶点字符及权值:"<<endl;
		for(k=0;k<G.arcnum;k++)
		{
			cin>>v1>>v2>>v3;
			i=LocateVex(G,v1);
		    j=LocateVex(G,v2);
		    G.arcs[i][j]=v3;        
		}
}
//输出图的顶点和邻接矩阵 
void printG(Graph G)
{
	int i,j;
	cout<<"有向图的各顶点是："<<endl;
	for(i=0;i<G.vexnum;i++)
		cout<<G.vexs[i]<<" ";
	cout<<endl;
	cout<<"有向图的邻接矩阵是："<<endl;
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
			cout<< G.arcs[i][j]<<"  ";
		cout<<endl;
	}
}

//插入一条弧(v,w)
int Insert(Graph &G)
{ 
	int i,j;
	int x;
	char v,w;
	cin>>v>>w;
	cin>>x;
	if((i=LocateVex(G,v))<0) return -1; 
	if((j=LocateVex(G,w))<0) return -1; 
	else if(G.arcs[i][j]==0)
	{
		G.arcs[i][j]=x;
		G.arcnum++; 
	}
	return 1;
}

//删除一条弧(v,w) 
int Delete(Graph &G)
{ 
	int i,j;
	char v,w;
	cin>>v>>w;
	if((i=LocateVex(G,v))<0) return -1; 
	if((j=LocateVex(G,w))<0) return -1; 
	else if(G.arcs[i][j]) 
	{ 
		G.arcs[i][j]=0; 
		G.arcnum--; 
	} 
	return 1; 
}

//求各顶点的出度
int Outdegree(Graph &G,int outdegree[])
{
	int i,j;	
	for(i=0;i<G.vexnum;i++)
	{
		outdegree[i]=0;
		for(j=0;j<G.vexnum;j++)
			if(G.arcs[i][j]!=0)
				outdegree[i]++;
			cout<<"顶点"<<"  "<<"出度"<<endl;
			cout<<" "<<G.vexs[i]<<"     "<<outdegree[i]<<endl;
	}
	return 1;
}

//求各顶点的入度
int Indegree(Graph &G,int indegree[])
{
	int i,j;
	for(j=0;j<G.vexnum;j++)
	{ 
		indegree[j]=0;
		for(i=0;i<G.vexnum;i++)	
			if(G.arcs[i][j]!=0)
				indegree[j]++;
			cout<<"顶点"<<"  "<<"入度"<<endl;
			cout<<" "<<G.vexs[j]<<"     "<<indegree[j]<<endl;
	}
	return 1;
}

//队列
typedef struct QNode{
	int data;
	struct QNode  *next;
}QNode,*QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

//创建一个队列
int InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)
		exit(-1);
	Q.front->next=NULL;
	return 1;
}

//判断队列是否为空
int QueueEmpty(LinkQueue &Q)
{
	if(Q.front==Q.rear)
		return 1;
	else 
		return 0;
}

//入队操作
int EnQueue(LinkQueue &Q,int e)
{
    QueuePtr p;
	p=Q.front;
    p->data=e;
	p->next=NULL;
	Q.front->next=p;
	Q.rear=p;	
	return 1;
}

//出队操作
int DeQueue(LinkQueue &Q,int e)
{
    QueuePtr p;
	if(Q.front==Q.rear)
		return 0;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	free(p);
	return 1;
}


//广度优先遍历算法
void BFS(Graph G)
{
    LinkQueue q;
	int i,j;
	int visited[M];
	InitQueue(q);
    for(i=0;i<G.vexnum;i++)
		visited[i]=0;
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
		{
			visited[i]=1;
			EnQueue(q,i);
			cout<<G.vexs[i]<<"  ";
			while(!QueueEmpty(q))
			{
				DeQueue(q,i);
				for(i=0;i<G.vexnum;i++)
		        for(j=0;j<G.vexnum;j++)
				{
					if(G.arcs[i][j] && visited[j]==0)
						{
							visited[j]=1;
							cout<<G.vexs[j];
							EnQueue(q,j);
						}
				}

			}
		}
		cout<<endl;
}

//拓扑排序
void TopologicalSort(Graph G)       
{
	int i,j,count=0,k=0; 
	int arcs[MAXvex][MAXvex];                          //用数组表示有向图
	char t[MAXvex];                                    //输出拓扑序列的顶点                      
	int flag[MAXvex]={0,0,0,0,0};                      //标记顶点
	int indegree[M];
	Indegree(G,indegree);
//	cout<<"你输入的有向图如下:"<<endl;
//	for(i=0;i<G.vexnum;i++)
//		for(j=0;j<G.vexnum;j++)
//		{
//			if(G.arcs[i][j]!=0)
//				cout<<"("<<G.vexs[i]<<","<<G.vexs[j]<<")";
//			cout<<endl;
//		}
		cout<<"排序前indegree[M]中的内容:";               //输出有向图的入度
		for(i=0;i<G.vexnum;i++)
			cout<<indegree[i];
		cout<<endl;
                                                          
		for(i=0;i<G.vexnum;i++)                           //拓扑排序开始
			if((indegree[i]==0)&&(flag[i]==0))            //入度为0和标记为0的顶点输出到indegree[M]中
			{
				t[k++]=G.vexs[i];
				count++;                                      //计数器加 1
				for(j=0;j<G.vexnum;j++)
				if(arcs[i][j]!=0 && G.vexs[i] && indegree[j]!=0) //修改在indegree[M]中的入度
					indegree[j]--;
				flag[i]=1;                                //将该顶点的标记设为1
			}
			if(count==G.vexnum)
			{
				cout<<"它存在的拓扑序列的其中一个是：";   //输出拓扑序列
			    for(i=0;i<G.vexnum;i++) 
					if(i==G.vexnum)
						cout<<t[i];
					else 
						cout<<t[i]<<"  ";
					cout<<endl;
			}
			else
				cout<<"它不存在任何的拓扑序列!"<<endl;
			    cout<<"排序后indegree[M]中的内容:";
			    for(i=0;i<G.vexnum;i++)
					cout<<indegree[i];                   //输出排序后indegree[M]中的内容
				cout<<endl;
} 

void main()
{
	int  outdegree[M],indegree[M];
	int  FunNumber;
	Graph G1;
	cout<<"               "<<"************************************"<<endl;
    cout<<"               "<<"|学生基本信息管理系统主菜单界面|"<<endl;
	cout<<"               "<<"|    1.输出图的顶点和邻接矩阵  |"<<endl;
    cout<<"               "<<"|    2.求各顶点的出度          |"<<endl;
    cout<<"               "<<"|    3.求各顶点的入度          |"<<endl;
    cout<<"               "<<"|    4.插入一条弧              |"<<endl;
    cout<<"               "<<"|    5.删除一条弧              |"<<endl;
    cout<<"               "<<"|    6.广度优先遍历算法        |"<<endl;
    cout<<"               "<<"|    7.求拓扑排序序列          |"<<endl;
	cout<<"               "<<"|    8.安全退出系统            |"<<endl;
    cout<<"               "<<"|   ->学生基本信息管理程序<-   |"<<endl;
    cout<<"               "<<"************************************"<<endl;
	cout<<"请先创建图，否则无法完成以下要求!"<<endl;
	cout<<"开始创建图:"<<endl;
	createDG(G1);
	do{     
		cout<<"请输入选择号(1--8):";
		cin>>FunNumber;
		switch(FunNumber)
		{ 
		case 1:
			printG(G1);
			break;
        case 2:
			cout<<"各顶点的出度分别是:"<<endl;
            Outdegree(G1,outdegree);
			break;
        case 3:
			cout<<"各顶点的入度分别是:"<<endl;
            Indegree(G1,indegree);
		    break;
        case 4:
			cout<<"输入要插入的弧及权植:"<<endl;
            Insert(G1);
            printG(G1);
			break;
		case 5:
		    cout<<"输入要删除的弧:"<<endl;
            Delete(G1);
            printG(G1);
			break;
		case 6:
            cout<<"广度优先遍历序列是:"<<endl;
            BFS(G1);
			break;
		case 7:
            cout<<"拓扑排序:"<<endl;
            TopologicalSort(G1);
			break;
		case 8:
			break;
        default:
			cout<<"输入错误!";
			break;
		}
	}while(FunNumber!=8);
	cout<<"退出系统!";
}