《数据结构(visualc++)用邻接矩阵表示给定无向图并进行深度遍历》由会员分享，可在线阅读，更多相关《数据结构(visualc++)用邻接矩阵表示给定无向图并进行深度遍历（27页珍藏版）》请在金锄头文库上搜索。
1、1.给定无向图，请用邻接矩阵表达法表达该图v4v5v3v2v1 #include#includeusing namespace std;#define MAX 20typedef int AdjMAXMAX;typedef structstring vexsMAX; /顶点表Adj arcs; /邻接矩阵int vexnum,arcnum; /图旳顶点和弧数MGraph;int LocateVex(MGraph &G,string u);int CreateUDN(MGraph &G) int i,k,j;string v1,v2;coutG.vexnumG.arcnum;cout输入顶点:;
2、for(i=0;iG.vexsi; /构造顶点数for(i=0;iG.vexnum;i+) /构造邻接矩阵for(j=0;jG.vexnum;j+)G.arcsij=0;for(k=0;kG.arcnum;k+)cout输入第k+1v1v2;i=LocateVex(G,v1); j=LocateVex(G,v2);G.arcsij=1;G.arcsji=1; /置旳对称弧return 0;int LocateVex(MGraph &G,string u) /确定u在G中序号 int i;for (i=0;iG.vexnum;i+)if (u=G.vexsi) return i;if (i=G.
3、vexnum) coutError u!endl; exit(1); return 0;void ShowG(MGraph &G)int i,j;for(i=0;iG.vexnum;i+)coutG.vexsi ;coutendl;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)coutG.arcsij ;coutendl;main()MGraph A;int a;a=CreateUDN(A);ShowG(A);2.分别使用邻接矩阵表达法和邻接表表达法，用深度优先搜索法遍历该图。#include# include # include # include us
4、ing namespace std;int visited30;# define MAX_VERTEX_NUM 30# define OK 1/typedef int VertexType;typedef int InfoType;typedef struct ArcNode /弧 int adjvex; struct ArcNode *nextarc;ArcNode;typedef struct VNode/表头 int data; ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct/图 AdjList vertices;
5、 int vexnum,arcnum; int kind;ALGraph;void CreateDG(ALGraph &G) int k,i,v1; coutendlG.vexnum; coutG.arcnum; for(i=1;i=G.vexnum;i+)/初使化表头 G.verticesi.data=i; G.verticesi.firstarc=NULL; for(k=1;k=G.vexnum;k+) /输入边 int v2; cout请输入与结点kv2; cout请输入与第kv1; ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode); if(!
6、p) exit(-1); p-adjvex=v1; p-nextarc=NULL; G.verticesk.firstarc=p; for(int i=1;iv2;i+) int m; cout请输入与第km; ArcNode *q; q=(ArcNode *)malloc(sizeof(ArcNode);/动态指针 if(!q) exit(-1); q-adjvex=m; /顶点给P q-nextarc=NULL; p-nextarc=q; p=q; /free(q); /free(p); void DFS (ALGraph G,int v )/深度搜索 visitedv=1; coutG.
7、verticesv.datanextarc) w=x-adjvex; if(visitedw=0) DFS(G,w); void DFSB (ALGraph G,int v)/深度搜索旳边集 visitedv=1; ArcNode *y; y=(ArcNode*)malloc(sizeof(ArcNode); if(!y) exit(-1); y=G.verticesv.firstarc; int u=G.verticesv.data; int w; for(;y;y=y-nextarc) w=y-adjvex; if(visitedw=0) coutuwnext=NULL;void EnQu
8、eue (LinkQueue &Q,int e)/进队 QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) exit(-1); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; /free(p);int DeQueue (LinkQueue &Q,int &e)/出队 if(Q.front=Q.rear) return -1; QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) exit(-1); p=Q.front-next; e=p-data; Q.fr
9、ont-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return e;int QueueEmpty (LinkQueue Q)/判断队列与否为空 if(Q.front=Q.rear) return 1; return 0; void BFS(ALGraph G,int v)/广度搜索 int u; LinkQueue Q; InitQueue(Q); if(visitedv=0) visitedv=1; coutG.verticesv.dataadjvex;w=0;w=z-nextarc-adjvex) if(visitedw=0) visitedw=1; coutwnextarc) w=z-adjvex; if(visitedw=0) visitedw=1; coutw ; EnQueue(Q,w); void BFSB (ALGraph G,int v)/广度搜索旳边集 int u; LinkQueue Q
