图的存储形式——邻接矩阵(数组)

/************************************
图的邻接矩阵(数组)表示
by Rowandjj
2014/6/22
************************************/#include<iostream>
using namespace std;#define INFINTY_INT_MAX  0x7fffffff    //代表正无穷
#define MAX_VERTIEX_NUM 20    //最大顶点个数
#define MAX_INFO 20typedef enum{DG,DN,AG,AN}GraphKind;//有向图、有向网、无向图、无向网typedef struct
{int adj;//顶点关系类型char *info;//该弧的相关信息
}ArcCell,AdjMatrix[MAX_VERTIEX_NUM][MAX_VERTIEX_NUM];typedef struct 
{char vexs[MAX_VERTIEX_NUM];//顶点向量AdjMatrix arcs;//邻接矩阵int vexnum,arcnum;//顶点数、弧数GraphKind kind;//种类
}MGraph,*pMGraph;bool visited[MAX_VERTIEX_NUM];//访问标志数组(全局)
bool (*VisitFunc)(char);bool Visit(char v)
{cout<<v;    return true;
}
//----------------操作-------------------------------
int LocateVex(MGraph G,char u);//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
bool CreateDG(pMGraph G);//创建有向图
bool CreateDN(pMGraph G);//创建有向网
bool CreateAG(pMGraph G);//创建无向图
bool CreateAN(pMGraph G);//创建无向网bool CreateGraph(pMGraph G);//构造图
void DestroyGraph(pMGraph G);//销毁图G
char GetVex(MGraph G,int v);//初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值
bool PutVex(pMGraph G,char v,char iValue);//初始条件: 图G存在，v是G中某个顶点。操作结果: 对v赋新值value
int FirstAdjVex(MGraph G,char v);//返回v的第一个邻接顶点的序号
int NextAdjVex(MGraph G,char v,char w);//返回v的(相对于w的)下一个邻接顶点的序号,否则返回-1
void InsertVex(pMGraph G,char v);//在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)
bool DeleteVex(pMGraph G,char v);//删除G中顶点v及其相关的弧
bool InsertArc(pMGraph G,char v,char w);//在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
bool DeleteArc(pMGraph G,char v,char w);//在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>void DFSTravel(MGraph G,bool (*Visit)(char));//深度优先
void DFS(MGraph G,int v);
void BFSTravel(MGraph G,bool (*Visit)(char));//广度优先
void Display(MGraph G);//----------------辅助队列--------------------------typedef struct _QUEUENODE_
{int data;struct _QUEUENODE_ *next;
}QueueNode,*pQueueNode;typedef struct _QUEUE_
{int size;pQueueNode pHead;pQueueNode pTail;
}Queue,*pQueue;bool InitQueue(pQueue Q);
bool DestroyQueue(pQueue Q);
bool DeQueue(pQueue Q,int* e);
bool EnQueue(pQueue Q, int e);
bool QueueEmpty(Queue Q);
//------------------------------------------
bool InitQueue(pQueue Q)
{Q->pHead = Q->pTail = (pQueueNode)malloc(sizeof(QueueNode));if(!Q->pHead){return false;}Q->pHead->next = NULL;Q->size = 0;return true;
}bool DestroyQueue(pQueue Q)
{pQueueNode pTemp = Q->pHead->next;while(pTemp != NULL){Q->pHead->next = pTemp->next;free(pTemp);pTemp = Q->pHead->next;}free(Q->pHead);Q->size = 0;return true;
}
bool QueueEmpty(Queue Q)
{return Q.size == 0;
}bool DeQueue(pQueue Q,int* e)
{pQueueNode pDel = Q->pHead->next;if(pDel != NULL){*e = pDel->data;Q->pHead->next = pDel->next;if(Q->pTail == pDel){Q->pTail = Q->pHead;}free(pDel);Q->size--;}return true;
}
bool EnQueue(pQueue Q, int e)
{pQueueNode pNew = (pQueueNode)malloc(sizeof(QueueNode));if(!pNew){return false;}pNew->next = NULL;pNew->data = e;Q->pTail->next = pNew;Q->pTail = pNew;Q->size++;return true;
}
//------------------------------------------
int LocateVex(MGraph G,char u)
{int i = 0;for(i = 0; i < G.vexnum;i++){if(u == G.vexs[i]){return i;}}return -1;
}bool CreateDG(pMGraph G)
{int incInfo = 0;int i,j,k,l;char va,vb;char *info;char s[MAX_INFO] = {0};//存放弧信息cout<<"请输入有向图G的顶点数,弧数,弧是否含其它信息(是:1,否:0)"<<endl;cin>>G->vexnum;cin>>G->arcnum;cin>>incInfo;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].adj = 0;G->arcs[i][j].info = NULL;}}cout<<"请输入每条弧的弧头和弧尾"<<endl;for(k = 0; k < G->arcnum; k++){cin>>va;cin>>vb;i = LocateVex(*G,va);j = LocateVex(*G,vb);G->arcs[i][j].adj = 1;if(incInfo){cout<<"输入该弧的信息"<<endl;cin>>s;l = strlen(s);if(l){info = (char *)malloc(sizeof(char) * (l+1));strcpy(info,s);G->arcs[i][j].info = info;}}}G->kind = DG;return true;
}bool CreateDN(pMGraph G)
{int incInfo;int i,j,k,l,w;char s[MAX_INFO];cout<<"请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0)"<<endl;cin>>G->vexnum;cin>>G->arcnum;cin>>incInfo;char va,vb;//分别代表弧头、弧尾char *pInfo;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].adj = INFINTY_INT_MAX;//网G->arcs[i][j].info = NULL;}}cout<<"请输入弧的头、尾、权值"<<endl;for(k = 0; k < G->arcnum; k++){cout<<"弧头"<<endl;cin>>va;cout<<"弧尾"<<endl;cin>>vb;cout<<"权值"<<endl;cin>>w;i = LocateVex(*G,va);j = LocateVex(*G,vb);G->arcs[i][j].adj = w;if(incInfo){cout<<"请输入该弧的信息"<<endl;cin>>s;l = strlen(s);if(l){pInfo = (char *)malloc(sizeof(char)*(l+1));strcpy(pInfo,s);G->arcs[i][j].info = pInfo;}}}G->kind = DN;return true;
}bool CreateAG(pMGraph G)//创建无向图
{int incInfo;int i,j,k,l;char va,vb;cout<<"请输入无向图G的顶点数,边数,边是否含其它信息(是:1,否:0):"<<endl;cin>>G->vexnum;cin>>G->arcnum;cin>>incInfo;char s[MAX_INFO];char *info;//初始化顶点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].adj = 0;//图G->arcs[i][j].info = NULL;}}cout<<"请输入每条边的两个顶点"<<endl;for(k = 0; k < G->arcnum; k++){cin>>va;cin>>vb;i = LocateVex(*G,va);j = LocateVex(*G,vb);G->arcs[i][j].adj = G->arcs[j][i].adj = 1;if(incInfo){cin>>s;l = strlen(s);if(l){info = (char *)malloc(sizeof(char)*(l+1));strcpy(info,s);G->arcs[i][j].info = G->arcs[j][i].info = info;}}}G->kind = AG;return true;
}
bool CreateAN(pMGraph G)
{int incInfo;int i,j,k;char va,vb;int w;char s[MAX_INFO];char *info;cout<<"请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):";cin>>G->vexnum;cin>>G->arcnum;cin>>incInfo;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].adj = INFINTY_INT_MAX;G->arcs[i][j].info = NULL;}}cout<<"请输入每条边的两个顶点以及权值"<<endl;for(k = 0; k < G->vexnum; k++){cin>>va;cin>>vb;cin>>w;i = LocateVex(*G,va);j = LocateVex(*G,vb);G->arcs[i][j].adj = G->arcs[j][i].adj = w;if(incInfo){cout<<"请输入该边的相关信息"<<endl;cin>>s;w = strlen(s);if(w){info = (char *)malloc(sizeof(char)*(w+1));strcpy(info,s);G->arcs[i][j].info = G->arcs[j][i].info = info;}}}G->kind = AN;return true;
}
bool CreateGraph(pMGraph G)
{cout<<"请输入图G的类型(有向图:0,有向网:1,无向图:2,无向网:3):";scanf("%d",&(*G).kind);switch((*G).kind){case DG: return CreateDG(G); /* 构造有向图 */case DN: return CreateDN(G); /* 构造有向网 */case AG: return CreateAG(G); /* 构造无向图 */case AN: return CreateAN(G); /* 构造无向网 */default: return false;}
}
void DestroyGraph(pMGraph G)
{int i,j;if(G->kind < 2)//有向tu{for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++){if(G->kind == 0 && G->arcs[i][j].adj == 1 || G->kind == 1 && G->arcs[i][j].adj != INFINTY_INT_MAX){free(G->arcs[i][j].info);G->arcs[i][j].info = NULL;}}}}else{for(i = 0; i < G->vexnum; i++){for(j = i+1; j < G->vexnum; j++){if(G->kind == 2 && G->arcs[i][j].adj == 1 || G->kind == 3 && G->arcs[i][j].adj != INFINTY_INT_MAX){free(G->arcs[i][j].info);G->arcs[i][j].info = G->arcs[j][i].info =NULL;}}}}
}
char GetVex(MGraph G,int v)
{if(v > G.vexnum || v < 0){exit(0);}return G.vexs[v];
}
bool PutVex(pMGraph G,char v,char iValue)
{int k = 0;k = LocateVex(*G,v);if( k < 0){return false;}G->vexs[k] = iValue;return true;
}
int FirstAdjVex(MGraph G,char v)
{    int i,j = 0,k;k = LocateVex(G,v);if(G.kind == AN || G.kind == DN){j = INFINTY_INT_MAX;}for(i = 0; i < G.vexnum; i++){if(G.arcs[k][i].adj != j){return i;}}return -1;
}
int NextAdjVex(MGraph G,char v,char w)//返回v的(相对于w的)下一个邻接顶点的序号,若w是v的最后一个邻接顶点,则返回-1
{int k1,k2;int i,j = 0;k1 = LocateVex(G,v);k2 = LocateVex(G,w);if(G.kind == AN || G.kind == DN){j = INFINTY_INT_MAX;}for(i = k2+1; i < G.vexnum ; i++){if(G.arcs[k1][i].adj != j){return i;}}return -1;
}void Display(MGraph G)
{int i,j;cout<<"顶点:";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].adj<<" ";}cout<<endl;}
}
void InsertVex(pMGraph G,char v)
{int index = G->vexnum;G->vexnum+=1;G->vexs[index] = v;for(int i = 0; i <= index; i++){    if(G->kind % 2)//网{G->arcs[i][index].adj = G->arcs[index][i].adj = INFINTY_INT_MAX;}else{G->arcs[i][index].adj = G->arcs[index][i].adj = 0;}G->arcs[index][i].info = NULL;G->arcs[i][index].info = NULL;}}
bool DeleteVex(pMGraph G,char v)
{int k,m = 0;int i,j;//1.找到顶点v的序号k = LocateVex(*G,v);if(k < 0){return false;}if(G->kind == DN || G->kind == AN)//网{m = INFINTY_INT_MAX;}//2.更改弧数(分有向图和无向图)for(i = 0; i < G->vexnum; i++){if(G->arcs[i][k].adj != m){if(G->arcs[i][k].info)//释放相关信息{free(G->arcs[i][k].info);}G->arcnum--;}}if(G->kind == DG || G->kind == AG)//有向图{for(i = 0; i < G->vexnum; i++){if(G->arcs[k][i].adj != m){if(G->arcs[k][i].info)//释放相关信息{free(G->arcs[k][i].info);}G->arcnum--;}}}//3.更改顶点数组内容及大小for(i = k+1; i < G->vexnum; i++){G->vexs[i-1] = G->vexs[i];}//4.更改邻接矩阵for(i = 0; i < G->vexnum; i++){for(j = k+1;j < G->vexnum; j++){G->arcs[i][j-1] = G->arcs[i][j];}}for(i = 0; i < G->vexnum; i++){for(j = k+1;j < G->vexnum; j++){G->arcs[j-1][i] = G->arcs[j][i]; }}G->vexnum--;return true;
}
bool InsertArc(pMGraph G,char v,char w)
{int i,j,k,l;char s[MAX_INFO];char *pinfo;//1.找到v、w的序号i = LocateVex(*G,v);j = LocateVex(*G,w);if(i < 0 || j < 0){return false;}//2.如果是网，需输入权值.是图则更改邻接矩阵相应值if(G->kind == DN || G->kind == AN){cout<<"输入权值:";cin>>G->arcs[i][j].adj;}else{G->arcs[i][j].adj = 1;}//3.如果有相关信息，输入之cout<<"该弧是否有相关信息(0:否 1:是):"<<endl;cin>>k;if(k){cout<<"输入相关信息:";cin>>s;l = strlen(s);if(l){pinfo = (char *)malloc(sizeof(char)*(l+1));strcpy(pinfo,s);G->arcs[i][j].info = pinfo;}}//4.如果是无向的，添加对称弧if(G->kind == AG || G->kind == AN){G->arcs[j][i].adj = G->arcs[i][j].adj;G->arcs[j][i].info = G->arcs[i][j].info;}G->arcnum++;return true;
}
bool DeleteArc(pMGraph G,char v,char w)
{int i,j;//1.找到v、w的位置i = LocateVex(*G,v);j = LocateVex(*G,w);if(i < 0 || j < 0){return false;}//2.如果是图则将邻接矩阵对应位置的值改为0，否则改为INT_MAXif(G->kind == DG || G->kind == AG){G->arcs[i][j].adj = 0;}else{G->arcs[i][j].adj = INFINTY_INT_MAX;}    if(G->arcs[i][j].info){free(G->arcs[i][j].info);G->arcs[i][j].info = NULL;}//3.如果是无向的，需删除对称弧if(G->kind == AG || G->kind == AN){G->arcs[j][i].adj = G->arcs[i][j].adj;G->arcs[j][i].info = NULL;}G->arcnum--;return true;
}
void DFSTravel(MGraph G,bool (*Visit)(char))
{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(G,v);}}cout<<endl;
}
void DFS(MGraph G,int v)
{char w1,v1;int w;visited[v] = true;VisitFunc(G.vexs[v]);v1 = GetVex(G,v);for(w = FirstAdjVex(G,v1);w>=0;w = NextAdjVex(G,v1,w1=GetVex(G,w))){if(!visited[w]){DFS(G,w);}}
}
void BFSTravel(MGraph G,bool (*Visit)(char))
{Queue q;InitQueue(&q);char w1,u1;int i,u,w;for(i = 0; i < G.vexnum; i++){visited[i] = false;}for(i = 0; i < G.vexnum; i++){if(!visited[i]){visited[i] = true;Visit(G.vexs[i]);EnQueue(&q,i);while(!QueueEmpty(q)){DeQueue(&q,&u);u1 = GetVex(G,u);for(w = FirstAdjVex(G,u1);w>=0;w = NextAdjVex(G,u1,w1=GetVex(G,w))){if(!visited[w]){visited[w] = true;Visit(G.vexs[w]);EnQueue(&q,w);}}}}}DestroyQueue(&q);cout<<endl;
}
int main()
{MGraph G;CreateDG(&G);Display(G);cout<<"深度优先遍历"<<endl;DFSTravel(G,Visit);cout<<"广度优先遍历"<<endl;BFSTravel(G,Visit);return 0;
}