头文件 Graph.h
//以数组形式构造图
#pragma once
#include <iostream>
#include <queue>
using namespace std;
#define INFINITY INT_MAX
#define NAX_VERTEX_NUM 20
#define VRtype int
//#define InfoType char*
#define VertexType char*
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INFEASIBLE -1
bool visited[NAX_VERTEX_NUM];
void(*VisitFunc)(VertexType);
typedef enum
{
DG,DN,UDG,UDN//有向图，有向网，无向图，无向网
}GraphKind;
typedef struct ArcCell
{
VRtype adj;//无权图，用0或1；带权图，即权值
//InfoType *info;
}ArcCell, AdjMatrix[NAX_VERTEX_NUM][NAX_VERTEX_NUM];
typedef struct //定义图的结构
{
VertexType vexs[NAX_VERTEX_NUM];//顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //定点数，边（弧）数
GraphKind kind; //图的种类标记
}MGraph;
int CreateDG(MGraph &G);//构造有向图
int CreateDN(MGraph &G);//构造有向网
int CreateUDG(MGraph &G);//构造无向图
int CreateUDN(MGraph &G);//构造无向网
int CreateGraph(MGraph &G)//采用数组（邻接矩阵）表示法，构造图G
{
int n;
cout<<"创建有向图（0），有向网（1），无向图（2），无向网（3）"<<endl;
cin>>n;
switch(n)
{
case DG:
G.kind = DG;
return CreateDG(G);//有向图
case DN:
G.kind = DN;
return CreateDN(G);//有向网
case UDG:
G.kind = UDG;
return CreateUDG(G);//无向图
case UDN:
G.kind = UDN;
return CreateUDN(G);//无向网
default:
return ERROR;
}
}
int LocateVex(MGraph G, VertexType V)//顶点V在图中的位置
{
int i;
for(i=0; i<G.vexnum; i++)
{
if(strcmp(G.vexs[i],V) == 0)
return i;
}
return -1;//不存在，返回-1
}
int CreateUDG(MGraph &G)//构造无向图
{
cout<<"输入顶点数，边数："<<endl;
cin>>G.vexnum>>G.arcnum;
int i,j,k;
for(i=0; i<G.vexnum; i++)//构造顶点向量
{
cout<<"输入第"<<i+1<<"个顶点的名称：";
G.vexs[i] = (VertexType)malloc( sizeof(char) );
cin>>G.vexs[i];
}
for(i=0; i<G.vexnum; i++)//初始化领接矩阵
{
for(j=0; j<G.vexnum; j++)
{
G.arcs[i][j].adj = 0;
//G.arcs[i][j].info = NULL;
}
}
char *v1, *v2;
v1 = (char*)malloc(sizeof(char));
v2 = (char*)malloc(sizeof(char));
for(k=0; k<G.arcnum; k++)//构造邻接矩阵
{
cout<<"输入相连的边（v1,v2）：";
cin>>v1>>v2;
i = LocateVex(G,v1);//定位顶点v1及v2在图中的位置
j = LocateVex(G,v2);
G.arcs[i][j].adj = 1;//权值
G.arcs[j][i] = G.arcs[i][j];//无向图中，邻接矩阵对称
}
G.kind = UDG;//无向图
return OK;
}
int CreateDG(MGraph &G)//构造有向图
{
cout<<"输入顶点数，边数："<<endl;
cin>>G.vexnum>>G.arcnum;
int i,j,k;
for(i=0; i<G.vexnum; i++)//构造顶点向量
{
cout<<"输入第"<<i+1<<"个顶点的名称：";
G.vexs[i] = (VertexType)malloc( sizeof(char) );
cin>>G.vexs[i];
}
for(i=0; i<G.vexnum; i++)//初始化领接矩阵
{
for(j=0; j<G.vexnum; j++)
{
G.arcs[i][j].adj = 0;
//G.arcs[i][j].info = NULL;
}
}
char *v1, *v2;
v1 = (char*)malloc(sizeof(char));
v2 = (char*)malloc(sizeof(char));
for(k=0; k<G.arcnum; k++)//构造邻接矩阵
{
cout<<"输入连接的边（v1,v2）：";
cin>>v1>>v2;
i = LocateVex(G,v1);//定位顶点v1及v2在图中的位置
j = LocateVex(G,v2);
G.arcs[i][j].adj = 1;//权值
}
G.kind = DG;//有向图
return OK;
}
int CreateUDN(MGraph &G)//采用数组（邻接矩阵）表示法，构造无向网
{
//int IncInfo;
cout<<"输入顶点数，边数："<<endl;
cin>>G.vexnum>>G.arcnum;
int i,j,k;
for(i=0; i<G.vexnum; i++)//构造顶点向量
{
cout<<"输入第"<<i+1<<"个顶点的名称：";
G.vexs[i] = (VertexType)malloc( sizeof(char) );
cin>>G.vexs[i];
}
for(i=0; i<G.vexnum; i++)//初始化领接矩阵
{
for(j=0; j<G.vexnum; j++)
{
G.arcs[i][j].adj = INFINITY;
//G.arcs[i][j].info = NULL;
}
}
char *v1, *v2;
v1 = (char*)malloc(sizeof(char));
v2 = (char*)malloc(sizeof(char));
int w;
for(k=0; k<G.arcnum; k++)//构造邻接矩阵
{
cout<<"输入边及其权重（v1,v2,w）：";
cin>>v1>>v2>>w;
i = LocateVex(G,v1);//定位顶点v1及v2在图中的位置
j = LocateVex(G,v2);
G.arcs[i][j].adj = w;//权值
G.arcs[j][i] = G.arcs[i][j];//无向网中，邻接矩阵对称
}
G.kind = UDN;//无向网
return OK;
}
int CreateDN(MGraph &G)//采用数组（邻接矩阵）表示法，构造有向网
{
//int IncInfo;
cout<<"输入顶点数，边数："<<endl;
cin>>G.vexnum>>G.arcnum;
int i,j,k;
for(i=0; i<G.vexnum; i++)//构造顶点向量
{
cout<<"输入第"<<i+1<<"个顶点的名称：";
G.vexs[i] = (VertexType)malloc( sizeof(char) );
cin>>G.vexs[i];
}
for(i=0; i<G.vexnum; i++)//初始化领接矩阵
{
for(j=0; j<G.vexnum; j++)
{
G.arcs[i][j].adj = INFINITY;
//G.arcs[i][j].info = NULL;
}
}
char *v1, *v2;
v1 = (char*)malloc(sizeof(char));
v2 = (char*)malloc(sizeof(char));
int w;
for(k=0; k<G.arcnum; k++)//构造邻接矩阵
{
cout<<"输入边及其权重（v1,v2,w）：";
cin>>v1>>v2>>w;
i = LocateVex(G,v1);//定位顶点v1及v2在图中的位置
j = LocateVex(G,v2);
G.arcs[i][j].adj = w;//权值
}
G.kind = DN;//有向网
return OK;
}
VertexType GetVex(MGraph G, int v)//返回图中第V个顶点
{
if(v<1 || v>G.vexnum)
return NULL;
else
return G.vexs[v-1];//顶点数组以标号0开始
}
int PutVex(MGraph &G, VertexType v, VertexType value)//修改图中顶点v的名称为value
{
int i = LocateVex(G,v);
if(i<0)
return ERROR;
else
strcpy(G.vexs[i],value);
return OK;
}
VertexType FirstAdjVex(MGraph G, VertexType v)//返回顶点V的第一个邻接点
{
int i,j,k;
k = LocateVex(G,v);//定位顶点v在图中的位置
if(k<0)
return NULL;
if(G.kind % 2 == 1)//网
j = INFINITY;
else
j = 0;//图
for(i=0; i<G.vexnum; i++)
{
if(G.arcs[k][i].adj != j)//邻接矩阵中该行第一个不为j的分量所在的列号
return GetVex(G,i+1);
}
return NULL;
}
VertexType NextAdjVex(MGraph G, VertexType v, VertexType w)//返回顶点V的(相对于w)下一个邻接点
{
int i,j,k,p;
i = LocateVex(G,v);
j = LocateVex(G,w);
if(i<0 || j<0)
return NULL;
if(G.kind % 2 == 1)//网
k = INFINITY;
else
k = 0;//图
for(p=j+1; p<G.vexnum; p++)
{
if(G.arcs[i][p].adj != k)
return GetVex(G,p+1);
}
return NULL;
}
void InsertVex(MGraph &G, VertexType v)//插入顶点
{
int j,i;
if(G.kind % 2 == 1)
j = INFINITY;//网
else
j = 0;//图
G.vexs[G.vexnum] = (VertexType)malloc(sizeof(VertexType));
strcpy(G.vexs[G.vexnum],v);
for(i=0; i<=G.vexnum; i++)
G.arcs[G.vexnum][i].adj = G.arcs[i][G.vexnum].adj = j;//初始化权值
G.vexnum++;
}
int DeleteVex(MGraph &G, VertexType v)//删除顶点
{
int i,j,k,p;
k = LocateVex(G,v);
if(k<0)
return ERROR;
if(G.kind % 2 == 1)
j = INFINITY;//网
else
j = 0;//图
for(i=0; i<G.vexnum; i++)//入弧（出度）
if(G.arcs[k][i].adj != j)
G.arcnum--;
if(G.kind < 2)//有向
for(i=0; i<G.vexnum; i++)
if(G.arcs[i][k].adj != j)
G.arcnum--;
for(i=k+1; i<G.vexnum; i++)//顶点向量第k个之后的都往前移
strcpy(G.vexs[i-1],G.vexs[i]);
//free(G.vexs[i-1]);
G.vexs[i-1] = NULL;
for(i=0; i<G.vexnum; i++)//邻接矩阵中每行从第k列之后的都往前移
{
for(p=k+1; p<G.vexnum; p++)
G.arcs[i][p-1] = G.arcs[i][p];
G.arcs[i][p-1].adj = j;
}
G.arcs[i-1][p-1].adj = j;
for(i=k+1; i<G.vexnum; i++)//邻接矩阵中每列从第k行之后的都往上移
{
for(p=0; p<G.vexnum-1; p++)
{ G.arcs[i-1][p] = G.arcs[i][p];
if(i == G.vexnum-1)
G.arcs[i][p].adj = j;
}
}
G.vexnum--;
return OK;
}
int InsertArc(MGraph &G, VertexType v, VertexType w)//插入一条边或弧
{
int i,j,weight;
i = LocateVex(G,v);//尾
j = LocateVex(G,w);//头
if(i<0 || j<0)
return ERROR;
G.arcnum++;
if(G.kind % 2 == 1)
{
cout<<"输入权值：";
cin>>weight;
}
else
weight = 1;
if(G.kind < 2)//有向
G.arcs[i][j].adj = weight;
else//无向
G.arcs[j][i].adj= G.arcs[i][j].adj=weight;
return OK;
}
int DeleteArc(MGraph &G, VertexType v, VertexType w)//删除一条边
{
int i,j,weight;
i = LocateVex(G,v);//尾
j = LocateVex(G,w);//头
if(i<0 || j<0)
return ERROR;
G.arcnum--;
if(G.kind % 2 == 1)//网
weight = INFINITY;
else//图
weight = 1;
if(G.kind < 2)//有向
G.arcs[i][j].adj = weight;
else
G.arcs[i][j].adj = G.arcs[j][i].adj = weight;
return OK;
}
void Display(MGraph G)//输出邻接矩阵
{
int i,j;
for(i=0; i<G.vexnum; i++)
{
for(j=0; j<G.vexnum; j++)
{
cout<<"("<<G.vexs[i]<<"->"<<G.vexs[j]<<",";
if(G.arcs[i][j].adj == INFINITY)
cout<<"oo";
else
cout<<G.arcs[i][j].adj;
cout<<")"<<" ";
}
cout<<endl;
}
}
void Visit(VertexType e)
{
cout<<e;
}
void DFS(MGraph G, int v)
{
visited[v] = TRUE;//访问第v个结点
VisitFunc(G.vexs[v]);
VertexType w;
for(w=FirstAdjVex(G,G.vexs[v]); w!=NULL; w=NextAdjVex(G,G.vexs[v],w) )//对第v个顶点尚未访问的邻接结点w递归调用DFS
{
if(!visited[LocateVex(G,w)])
DFS(G,LocateVex(G,w));
}
}
void DFSTraverse(MGraph G, void(*Visit)(VertexType))//深度优先遍历
{
int v;
VisitFunc = Visit;
for(v=0; v<G.vexnum; v++)
visited[v] = FALSE;//访问标志数组
for(v=0; v<G.vexnum; v++)
if(!visited[v])//对尚未访问的顶点调用DFS
DFS(G,v);
cout<<endl;
}
void BFSTraverse(MGraph G, void(*Visit)(VertexType))//广度优先搜索算法
{
int i,u;
VertexType w;
for(i=0; i<G.vexnum; i++)//访问标记数组初始化
visited[i] = FALSE;
queue<int> Q; //置空的辅助队列
for(i=0; i<G.vexnum; i++)
{
if(!visited[i])
{
visited[i] = TRUE;
Visit(G.vexs[i]);
Q.push(i);
while(!Q.empty())
{
u = Q.front();//对头元素出队并置为u
Q.pop();
for(w=FirstAdjVex(G,G.vexs[u]); w!=NULL; w=NextAdjVex(G,G.vexs[u],w))
{ //w为u的尚未访问的邻接顶点
if(!visited[LocateVex(G,w)])
{
visited[LocateVex(G,w)] = TRUE;
Visit(w);
Q.push(LocateVex(G,w));
}
}
}
}
}
cout<<endl;
}
// Minimum Cost Spanning Tree.cpp : Defines the entry point for the console application.
/*-----CODE FOR FUN---------------
-------CREATED BY Dream_Whui------
-------2015-2-12--------------------*/
#include "stdafx.h"
#include "Graph.h"
typedef struct //记录从顶点集U到V-U的代价最小的边的辅助数组定义
{
VertexType adjvex; //起始顶点的名称
VRtype lowcost; //边的权值
}closedge[NAX_VERTEX_NUM]; //例 closedge[0]:{adjvex = v2, lowcost = n} 表示顶点v2到顶点v1，边的权重为n
//closedge[1]...closedge[NAX_VERTEX_NUM]类同
int minimun(MGraph G, closedge closed_array)
{
int i;
int min = INFINITY;
int flag;
for(i=0; i<G.vexnum; i++)
{
if(closed_array[i].lowcost < min && closed_array[i].lowcost > 0)
{
min = closed_array[i].lowcost;
flag = i;
}
}
return flag;
}
void MiniSpanTree_PRIM(MGraph G, VertexType u)//用普里姆算法计算从第u个顶点出发构造网G的最小生成树T，输出T的各条边
{
int k;
k = LocateVex(G,u);//顶点u在网中的位置
int i,j;
closedge closed_array;//定义辅助数组
for(j=0; j<G.vexnum; j++)
{
closed_array[j].adjvex = (VertexType)malloc(sizeof(char));//分配边的起始顶点名称的空间
if(j!=k)
{
closed_array[j].adjvex = u;//起始顶点名称u
closed_array[j].lowcost = G.arcs[k][j].adj;//边的权值
}
}
closed_array[k].lowcost = 0; //初始，U={u}
cout<<"最小生成树"<<endl;
for(i=1; i<G.vexnum; i++)
{
k = minimun(G,closed_array); //在辅助数组中找到权值最小的那条边，且MIN{closed_array[vi].lowcost && closed_array[vi].lowcost>0}
cout<<closed_array[k].adjvex<<"->"<<G.vexs[k]<<endl;//输出树的边
closed_array[k].lowcost = 0; //第k个顶点并入U集
for(j=0; j<G.vexnum; j++)
if(G.arcs[k][j].adj < closed_array[j].lowcost)//新顶点并入后重新 选择最小边
{
closed_array[j].adjvex = G.vexs[k];
closed_array[j].lowcost = G.arcs[k][j].adj;
}
}
}
int main(int argc, char* argv[])
{
MGraph G;
CreateGraph(G);
MiniSpanTree_PRIM(G,G.vexs[0]);
return 0;
}
