#include <stdio.h>
#include <iostream>
#include <iomanip> //setw(int n)函数的头文件
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
#define MAXQSIZE 100
#define MaxInt 1000 // 最大值
#define MVNum 20 //最大顶点数
typedef char VertexType; //顶点类型
typedef int ArcType; //边（权）类型
typedef struct {
int kind; //图的类型：1-DG,2-DN,3-UDG,4-UDN
int vexnum,arcnum; //顶点数和边的数目
VertexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
}AMGraph;
//Prim算法的辅助数组
typedef struct
{
VertexType adjvex; //最小边在U中的那个顶点
ArcType lowcost; //最小边上的权值
}closedge[MVNum]; //用来记录从顶点集U到V-U的权值最小的边
typedef struct
{
int* base;
int front;
int rear;
}SqQueue;
Status InitQueue(SqQueue& Q)
{//构造一个空队列Q
Q.base = new int[MAXQSIZE];
if (!Q.base) exit(OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}
Status EnQueue(SqQueue& Q, int e)
{//插入元素e为Q的新的队列元素
if ((Q.rear + 1) % MAXQSIZE == Q.front)
return ERROR;
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue& Q, int& e)
{//删除Q的队头元素，用e返回其值
if (Q.front == Q.rear) return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
Status QueueEmpty(SqQueue Q)
{
if (Q.front == Q.rear)
return OK;
return ERROR;
}
//在G中找到v对应的顶点的位置
int LovateVex(AMGraph G ,VertexType v){
int i;
for ( i=0; i<G.vexnum; i++)
if (G.vexs[i]==v) return i;
return -1;
}
//网带权,图不带权
//CreateUDN 创建无向网
Status CreateUDN(AMGraph &G){
int i,j,k;
VertexType v1,v2;
int w;
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]=MaxInt; //矩阵初始化
cout<<endl<<"输入边的信息( v1, v2 , weight)"<<endl;
for (k=0;k<G.arcnum;k++) { //构造邻接矩阵
cout<<"\n第"<<k+1<<"条边：" ;
cin>>v1>>v2>>w;
i=LovateVex(G,v1); //确定i和j在矩阵中的位置
j=LovateVex(G,v2);
if (i==-1 ||j==-1) {
cout<<"\n顶点输入有误！";
return ERROR;
}
G.arcs[i][j]=w; //弧<v1,v2>的权值w
G.arcs[j][i]=G.arcs[i][j];
}//for k
return OK;
}
//CreateDN 创建有向网（带权）
Status CreateDN(AMGraph &G){
int i,j,k;
VertexType v1,v2;
int w;
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]=MaxInt; //矩阵初始化
cout<<endl<<"输入边的信息( v1, v2 , weight)"<<endl;
for (k=0;k<G.arcnum;k++) { //构造邻接矩阵
cout<<"\n第"<<k+1<<"条边：" ;
cin>>v1>>v2>>w;
i=LovateVex(G,v1); //确定i和j在矩阵中的位置
j=LovateVex(G,v2);
if (i==-1 ||j==-1) {
cout<<"\n顶点输入有误！";
return ERROR;
}
G.arcs[i][j]=w; //弧<v1,v2>的权值w
}//for k
return OK;
}
//CreateUDG 创建无向图
Status CreateUDG(AMGraph &G){
int i,j,k;
VertexType v1,v2;
int w;
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<<"输入边的信息( v1, v2 , weight)"<<endl;
for (k=0;k<G.arcnum;k++) { //构造邻接矩阵
cout<<"\n第"<<k+1<<"条边：" ;
cin>>v1>>v2>>w;
i=LovateVex(G,v1); //确定i和j在矩阵中的位置
j=LovateVex(G,v2);
if (i==-1 ||j==-1) {
cout<<"\n顶点输入有误！";
return ERROR;
}
G.arcs[i][j]=1; //1代表可达，0代表不可达
G.arcs[j][i]=G.arcs[i][j];
}//for k
return OK;
}
//CreateDG 创建有向图
Status CreateDG(AMGraph &G){
int i,j,k;
VertexType v1,v2;
int w;
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; //矩阵初始化为0
cout<<endl<<"输入边的信息( v1, v2 , weight)"<<endl;
for (k=0;k<G.arcnum;k++) { //构造邻接矩阵
cout<<"\n第"<<k+1<<"条边：" ;
cin>>v1>>v2>>w;
i=LovateVex(G,v1); //确定i和j在矩阵中的位置
j=LovateVex(G,v2);
if (i==-1 ||j==-1) {
cout<<"\n顶点输入有误！";
return ERROR;
}
G.arcs[i][j]=1; //1代表可达，0代表不可达
}//for k
return OK;
}
//创建图/网
Status CreateGraph(AMGraph &G){
int kind;
cout<<endl<<"输入图的类型(1:有向图DG,2:有向网DN,3:无向图UDG,4:无向网UDN)\n";
cin>>G.kind;
switch (G.kind){
case 1 :return CreateDG(G);
case 2 :return CreateDN(G);
case 3 :return CreateUDG(G);
case 4 :return CreateUDN(G);
default :return ERROR;
}
}
//输出图的基本信息
void PrintGraph(AMGraph G){
int i,j;
cout<<"\n图的顶点数和边数：";
cout<<setw(3)<<G.vexnum<<setw(3)<<G.arcnum; //setw()设置出的域宽
cout<<"\n图的顶点：";
for (i=0;i<G.vexnum;i++)
cout<<setw(3)<<G.vexs[i];
cout<<"\n图的邻接矩阵："<<endl;
for (i=0;i<G.vexnum;i++){
cout<<endl;
for (j=0;j<G.vexnum;j++)
if (G.arcs[i][j]==MaxInt) cout<<setw(5)<<"∞";
else cout<<setw(5)<<G.arcs[i][j];
}//for i
cout<<endl;
}
//计算有向图（网）的入度
void FindIndegree(AMGraph G,int indegree[]){
for(int i=0;i<G.vexnum;i++)
indegree[i]=0;
for(int i=0;i<G.vexnum;i++)
{
for(int j=0;j<G.vexnum;j++)
{
if(G.arcs[j][i]!=MaxInt||G.arcs[j][i]!=0)
++indegree[i];
}
}
}
//计算有向图（网）的出度
void FindOutdegree(AMGraph G,int outdegree[])
{
for(int i=0;i<G.vexnum;i++)
outdegree[i]=0;
for(int i=0;i<G.vexnum;i++)
{
for(int j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j]!=MaxInt&&G.arcs[i][j]!=0)
++outdegree[i];
}
}
}
//计算无向图（网）的度
void FindDegree(AMGraph G,int degree[]){
for(int i=0;i<G.vexnum;i++)
degree[i]=0;
for(int i=0;i<G.vexnum;i++)
{
for(int j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxInt)
++degree[i];
}
}
}
//计算每个顶点的度，对有向图(网),还需要计算入度和出度
void GraphDegree(AMGraph G){
int indegree[MVNum],outdegree[MVNum],degree[MVNum];
根据图的不同类型：1-DG,2-DN,3-UDG,4-UDN,计算顶点的度（入度/出度），并输出
switch (G.kind){
case 1 :
case 2 :
FindIndegree(G,indegree);
FindOutdegree(G,outdegree);
cout<<"有向网每个顶点的入度和出度："<<endl;
cout<<"\n--------------------------------------";
for(int i=0;i<G.vexnum;i++)
{
cout<<endl<<"顶点"<<G.vexs[i]<<"的入度："<<indegree[i]<<" ，出度："<<outdegree[i]<<endl;
}
cout<<"\n--------------------------------------";
break;
case 3 :
case 4 :FindDegree(G,degree);
cout<<"无向网每个顶点的入度和出度："<<endl;
cout<<"\n--------------------------------------";
for(int j=0;j<G.vexnum;j++)
{
cout<<endl<<"顶点"<<G.vexs[j]<<"的入度："<<degree[j]<<" ，出度："<<degree[j]<<endl;
}
cout<<"\n--------------------------------------";
break;
}
}//GraphDegree
//图的遍历：深度优先搜索
bool visited[MVNum];
void DFS(AMGraph G,int v)
{
//从顶点v出发，对图G进行深度优先搜索
visited[v]=true;
cout<<setw(3)<<G.vexs[v];
for(int w=0;w<G.vexnum;w++)
{
if(G.arcs[v][w]!=0&&(G.arcs[v][w]!=MaxInt)&&(!visited[w]))
DFS(G,w);
}
}
void DFSTraverse(AMGraph G){
//对图G进行深度优先搜索
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=false;
for(v=0;v<G.vexnum;v++)
{
if(!visited[v])
DFS(G,v);
}
}
//图的遍历：广度优先搜索
void BFS(AMGraph G,int v){
//从顶点v出发，对图G进行深度优先搜索
SqQueue Q;
int u,w;
InitQueue(Q);
visited[v]=true;
cout<<setw(3)<<G.vexs[v];
EnQueue(Q,v);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
for(w=0;w<G.vexnum;w++)
{
if(G.arcs[v][w]!=0&&(G.arcs[v][w]!=MaxInt)&&(!visited[w]))
{
visited[w]=true;
cout<<setw(3)<<G.vexs[w];
EnQueue(Q,w);
}
}
}
}//BFS
void BFSTraverse(AMGraph G)
{
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=false;
for(v=0;v<G.vexnum;v++)
{
if(!visited[v])
BFS(G,v);
}
}//BFSTraverse
int Min(AMGraph G,closedge close)
{
int min=MaxInt;
int mini=-1;
for(int i=0;i<G.vexnum;i++)
{
if(close[i].lowcost>0&&close[i].lowcost<min)
{
min=close[i].lowcost;
mini=i;
}
}
return mini;
}
//Prim算法
void MiniSpanTree(AMGraph G,VertexType u)
{
//u作为起点，从u出发构造G的最小生成树T，输出T的各条边
int k=LovateVex(G,u); //以k为顶点u的下标
for(int j=0;j<G.vexnum;++j) //对V—U的每一个顶点vj，初始化closedge[j]
{
if(j!=k)
closedge[j]={u,G.arcs[k][j]}; //{adjvex，lowcost}
}
closedge[k].lowcost=0; //初始，U={u}
for(int i=1;i<G.vexnum;++i) //选择其余n-1个顶点，生成n-1条边（n=G.vexnum）
{
k=Min(G,closedge); //求出最小生成树的下一个结点k
u0=closedge[k].adjvex; //u0为最小边的一个顶点，属于U
v0=G.vexs[k]; //v0为最小边的另一个顶点，v0属于V-U
cout<<u0<<v0; //输出当前最小边（u0，v0）
closedge[k].lowcost=0; //第k个顶点并入U
for(j=0;j<G.vexnum;++j)
{
if(G.arcs[k][j]<closedge[j].lowcost) //新顶点并入U后重新选择最小边
closedge[j]={G.vexs[k],G.arcs[k][j]};
}
}
}
//最短路径—Dijkstra算法
void ShortestPath_DIJ(AMGraph G,int v0)
{
//以v0为起点，求G中的最短路径
int n=G.vexnum; //n为G中顶点数
for(int v=0;v<n;++v) //n个顶点依次初始化
{
S[v]=false; //S初始化为空集，将v0到各个终点的最短路径长度初始化为弧的权值
D[v]=G.arcs[v0][v];
if(D[v]<MaxInt) //若v0和v之间有弧，则将v的前驱置为v0
Path[v]=v0;
else
Path[v]=-1; //若v0和v之间无弧，则将v的前驱置为-1
}
S[v0]=true; //将v0加入S
D[v0]=0; //源点到源点的距离为0
//初始化结束，开始主循环，依次求v0到某顶点v的最短路径，将v加到S集
for(i=1;i<n;++i) //对其余n-1个顶点依次计算
{
min=MaxInt;
for(w=0;w<n;++w)
{
if(!S[w]&&D[w]<min)
{
v=w; //选择一条当前的最短路径，终点为v
min=D[w];
}
}
S[v]=true; //将v加入S
for(w=0;w<n;++w) //更新从v0出发到集合V-S上所有顶点的最短路径长度
{
if(!S[w]&&(D[v]+G.arcs[v][w]<D[w]))
{
D[w]=D[v]+G.arcs[v][w]; //更新D[w]
Path[w]=v; //更改w的前驱为v
}
}
}
}
int main(){
AMGraph G;
int choice;
if (CreateGraph(G)==OK){//建立图的邻接矩阵
cout<<"图的邻接矩阵建立成功！！\n";
PrintGraph(G);
}
else {
cout<<"图的邻接矩阵建立失败，程序退出！！\n";
return 0;
}
do{ cout<<"\n\n 图的邻接矩阵存储表示及其应用 \n";
cout<<"=============================================\n";
cout<<" 1:计算顶点的度\n";
cout<<" 2:深度优先搜索\n";
cout<<" 3:广度优先搜索\n";
// cout<<" 4:连通无向网求解最小生成树的Prim算法\n";
// cout<<" 5:求解单源点最短路径的Dijkstra算法\n";
cout<<" 0:退出\n";
cout<<"=============================================\n";
cout<<"输入你的选择：";
cin>>choice;
switch (choice){
case 1: GraphDegree(G);
break;
case 2: cout<<"DFS的结果为："<<endl;
DFSTraverse(G);
break;
case 3: cout<<"BFS的结果为："<<endl;
BFSTraverse(G);
break;
// case 4:
// MiniSpanTree(G,u);
// break;
// case 5:
// ShortestPath_DIJ(G,v0);
// break;
default:break;
}
cout<<endl;system("pause") ;//按任意键继续
}while (choice);
return 0;
}