邻接矩阵存储方式实现.zip

#include<iostream> #include<stdio.h> #include<string> #include<queue> #include<string.h> #define INFINITY 0X7fffffff #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 using namespace std; #define MAX_VERTEX_NUM 30 typedef char InfoType; typedef int Status; typedef int Boolean; typedef string VertexType; typedef enum {DG,DN,UDG,UDN} GraphKind; Boolean visited[MAX_VERTEX_NUM]; typedef struct ArcCell///弧(邻接矩阵) { int adj; InfoType *info; } ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct///图(邻接矩阵) { string vexs[MAX_VERTEX_NUM];///结点名 AdjMatrix arcs; ///邻接矩阵 int vexnum,arcnum; ///结点数，弧数 GraphKind kind; } MGraph; Status (*VisitFunc)(MGraph G,int v); 建图，以建立无向无权图为例： 首先输入该图的总结点数、总边数、是否包含信息 然后对于每个标号输入该标号(结点)的命名 Status CreateUDG(MGraph &G)///邻接矩阵(建立无权无向图) { int IncInfo; printf("建立无权无向图，请依次输入总结点数、总边数、是否包含信息:\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo); printf("请为从1至n个结点命名:\n"); for(int i=0; i<G.vexnum; i++)cin>>G.vexs[i]; for(int i=0; i<G.vexnum; i++) for(int j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY,G.arcs[i][j].info=NULL; string v1,v2; printf("请输入%d组相互依附的两结点:\n",G.arcnum); for(int k=0; k<G.arcnum; k++) { cin>>v1>>v2; int i=LocateVex(G,v1); int j=LocateVex(G,v2); G.arcs[i][j].adj=TRUE;///无权 if(IncInfo)scanf("%s",G.arcs[i][j].info); G.arcs[j][i]=G.arcs[i][j];///无向图,结构体赋值 } return OK; } 对图的基本操作：根据结点名获取结点的存储位置(邻接矩阵中的标号) Status LocateVex(MGraph G,string name)///获取结点标号 { for(int i=0; i<G.vexnum; i++) if(name==G.vexs[i])return i; return -1; } 利用DFS(深度优先搜索)遍历顺序遍历图 输入一个起始搜索点作为遍历的起点，若是一个连通图，一遍搜索即可 否则对于剩下未被标记的结点，作为一个新的连通图进行搜索 void DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v)) { VisitFunc=Visit; printf("请输入深度优先搜索起始结点:\n"); for(int v=0; v<G.vexnum; v++)visited[v]=FALSE; string st; cin>>st; int tmp=LocateVex(G,st); printf("深度优先搜索遍历序列:\n"); DFS(G,tmp); for(int v=0; v<G.vexnum; v++)if(!visited[v])DFS(G,v); printf("\n"); } void DFS(MGraph G,int v)///邻接矩阵DFS { visited[v]=TRUE; VisitFunc(G,v); for(int w=0; w<G.vexnum; w++) if(G.arcs[v][w].adj!=INFINITY&&!visited[w])DFS(G,w); } 利用BFS(广度优先搜索)顺序遍历图 利用队列，遍历每个当前结点可以到达的结点，将下一个可以到达的结点放入队列中作为搜索的候选项，这样不断放入可以达到的结点，不短弹出队首结点以连接投入新的可到达节点放入队列中 void BFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v))///邻接矩阵BFS { for(int v=0; v<G.vexnum; v++)visited[v]=FALSE; queue<int>Q; printf("请输入广度优先搜索起始结点:\n"); string st; cin>>st; printf("广度优先搜索遍历序列:\n"); int temp=LocateVex(G,st); Visit(G,temp); Q.push(temp); visited[temp]=TRUE; while(!Q.empty()) { int tmp=Q.front(); Q.pop(); for(int w=0; w<G.vexnum; w++) { if(!visited[w]&&G.arcs[tmp][w].adj!=INFINITY) { visited[w]=TRUE; Visit(G,w); Q.push(w); } } } for(int v=0; v<G.vexnum; v++)///剩余连通分量 { if(!visited[v]) { visited[v]=TRUE; Visit(G,v); Q.push(v); while(!Q.empty()) { int tmp=Q.front(); Q.pop(); for(int w=0; w<G.vexnum; w++) { if(!visited[w]&&G.arcs[tmp][w].adj!=INFINITY) { visited[w]=TRUE; Visit(G,w); Q.push(w); } } } } } printf("\n"); } 遍历(以输出结点名为例)图 Status visit(MGraph G,int v)///邻接矩阵遍历 { cout<<G.vexs[v]<<' '; } 完整代码，数据结构作业模板，存档用 #include<iostream> #include<stdio.h> #include<string> #include<queue> #include<string.h> #define INFINITY 0X7fffffff #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 using namespace std; #define MAX_VERTEX_NUM 30 typedef char InfoType; typedef int Status; typedef int Boolean; typedef string VertexType; typedef enum {DG,DN,UDG,UDN} GraphKind; Boolean visited[MAX_VERTEX_NUM]; typedef struct ArcCell///弧(邻接矩阵) { int adj; InfoType *info; } ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct///图(邻接矩阵) { string vexs[MAX_VERTEX_NUM];///结点名 AdjMatrix arcs; ///邻接矩阵 int vexnum,arcnum; ///结点数，弧数 GraphKind kind; } MGraph; Status (*VisitFunc)(MGraph G,int v); Status LocateVex(MGraph G,string name)///获取结点标号 { for(int i=0; i<G.vexnum; i++) if(name==G.vexs[i])return i; return -1; } Status CreateDG(MGraph &G)///邻接矩阵(建立无权有向图) { int IncInfo; printf("建立无权有向图，请依次输入总结点数、总边数、是否包含信息:\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo); printf("请为从1至n个结点命名:\n"); for(int i=0; i<G.vexnum; i++)cin>>G.vexs[i]; for(int i=0; i<G.vexnum; i++) for(int j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY,G.arcs[i][j].info=NULL; string v1,v2; printf("请输入%d组由左指向右的有向边:\n",G.arcnum); for(int k=0; k<G.arcnum; k++) { cin>>v1>>v2; int i=LocateVex(G,v1); int j=LocateVex(G,v2); G.arcs[i][j].adj=TRUE;///无权 if(IncInfo)scanf("%s",G.arcs[i][j].info); } return OK; } Status CreateDN(MGraph &G)///邻接矩阵(建立带权有向网) { int IncInfo; printf("建立带权有向网，请依次输入总结点数、总边数、是否包含信息:\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo); printf("请为从1至n个结点命名:\n"); for(int i=0; i<G.vexnum; i++)cin>>G.vexs[i]; for(int i=0; i<G.vexnum; i++) for(int j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY,G.arcs[i][j].info=NULL; string v1,v2; int w; printf("请输入%d组由左指向右的有向边与边权:\n",G.arcnum); for(int k=0; k<G.arcnum; k++) { cin>>v1>>v2>>w; int i=LocateVex(G,v1); int j=LocateVex(G,v2); G.arcs[i][j].adj=w;///带权 if(IncInfo)scanf("%s",G.arcs[i][j].info); } return OK; } Status CreateUDG(MGraph &G)///邻接矩阵(建立无权无向图) { int IncInfo; printf("建立无权无向图，请依次输入总结点数、总边数、是否包含信息:\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo); printf("请为从1至n个结点命名:\n"); for(int i=0; i<G.vexnum; i++)cin>>G.vexs[i]; for(int i=0; i<G.vexnum; i++) for(int j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY,G.arcs[i][j].info=NULL; string v1,v2; printf("请输入%d组相互依附的两结点:\n",G.arcnum); for(int k=0; k<G.arcnum; k++) { cin>>v1>>v2; int i=LocateVex(G,v1);