实验71.给定无向图，请用邻接矩阵表示法表示该图2.分别使用邻接矩阵表示法和邻接表表示法，用深度优先搜索法遍历该图3.对学生选课工程图进行拓扑排序.(算法 7.12 )v4v5v3v2v11.给定无向图，请用邻接矩阵表示法表示该图#include#includeusing namespace std;#define MAX 20typedef int Adj[MAX][MAX];typedef struct{ string vexs[MAX]; //顶点表 Adj arcs; //邻接矩阵 int vexnum,arcnum; //图的顶点和弧数}MGraph;int LocateVex(MGraph &G,string u);int CreateUDN(MGraph &G){ int i,k,j;string v1,v2; cout<<"请输入顶点数、弧数：";exnum>>G.arcnum; cout<<"输入顶点:"; for(i=0;i>G.vexs[i]; //构造顶点数 } for(i=0;i>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j]=1; G.arcs[j][i]=1; //置的对称弧 } return 0;}int LocateVex(MGraph &G,string u){ //确定u在G中序号 int i; for (i=0;i
include# include # include # include using namespace std;int visited[30];# 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,AdjList[MAX_VERTEX_NUM];typedef struct//图{ AdjList vertices; int vexnum,arcnum; int kind;}ALGraph;void CreateDG(ALGraph &G){ int k,i,v1; cout<>G.vexnum; cout<<"请输入弧的个数: "; cin>>G.arcnum; for(i=1;i<=G.vexnum;i++)//初使化表头 { G.vertices[i].data=i; G.vertices[i].firstarc=NULL; } for(k=1;k<=G.vexnum;k++) //输入边 { int v2; cout<<"请输入与结点"<>v2; cout<<"请输入与第"<>v1; ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode)); if(!p) exit(-1); p->adjvex=v1; p->nextarc=NULL; G.vertices[k].firstarc=p; for(int i=1;i>m; 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 )//深度搜索{ visited[v]=1; cout<nextarc) { w=x->adjvex; if(visited[w]==0) DFS(G,w); }}void DFSB (ALGraph G,int v)//深度搜索的边集{ visited[v]=1; ArcNode *y; y=(ArcNode*)malloc(sizeof(ArcNode)); if(!y) exit(-1); y=G.vertices[v].firstarc; int u=G.vertices[v].data; int w; for(;y;y=y->nextarc) { w=y->adjvex; if(visited[w]==0) { cout<"<next=NULL;}void EnQueue (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.front->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(visited[v]==0) { visited[v]=1; cout<adjvex;w>=0;w=z->nextarc->adjvex) { if(visited[w]==0) { visited[w]=1; cout<nextarc) { w=z->adjvex; if(visited[w]==0) { visited[w]=1; cout<nextarc) { w=r->adjvex; if(visited[w]==0) { visited[w]=1; cout<"<>x; cout<<"邻接表为："<adjvex<<" "; p=p->nextarc; } cout<>n; for( i=0;i<30;i++) visited[i]=0; cout<<"广度搜索："<#include#define MAX_VEXTEX_NUM 20#define M 20#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0typedef int ElemType;typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{int data;ArcNode *firstarc;}VNode,AdjList[MAX_VEXTEX_NUM];typedef struct{AdjList vertices;int vexnum, arcnum;}ALGraph;typedef struct //构件栈{ElemType *base;ElemType *top;int stacksize;}SqStack;void InitStack(SqStack *); //函数声明int Pop(SqStack *, ElemType *);void Push(SqStack *,ElemType );int StackEmpty(SqStack *);void CreatGraph(ALGraph *);void FindInDegree(ALGraph , int * );void TopologicalSort(ALGraph );void InitStack(SqStack *S)//初始化栈{S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S->base){printf("memory allocation failed, goodbye");exit(1);}S->top=S->base;S->stacksize=STACK_INIT_SIZE;}int Pop(SqStack *S,ElemType *e)//出栈操作{if(S->top==S->base){return ERROR;}*e=*--S->top;//printf("%d\n",e);// return e;return 0;}void Push(SqStack *S,ElemType e)//进栈操作{if(S->top-S->base>=S->stacksize){S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S->base){printf("memory allocation failed, goodbye");exit(1);}S->top = S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*S->top++=e;}int StackEmpty(SqStack *S)//判断栈是否为空{if(S->top==S->base)return OK;elsereturn ERROR;}void CreatGraph(ALGraph *G)//构件图{int m, n, i;ArcNode *p;printf("请输入顶点数和边数:");scanf("%d%d",&G->vexnum,&G->arcnum);for (i = 1; i <= G->vexnum; i++){G->vertices[i].data = i;G->vertices[i].firstarc = NULL;}for (i = 1; i <= G->arcnum; i++) //输入存在边的点集合{printf("\n请输入存在边的两个顶点的序号:");scanf("%d%d",&n,&m);while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum){printf("输入的顶点序号不正确 请重新输入:");scanf("%d%d",&n,&m);}p = (ArcNode*)malloc(sizeof(ArcNode));if (p == NULL){printf("memory allocation failed,goodbey");exit(1);}p->adjvex = m;p->nextarc = G->vertices[n].firstarc;G->vertices[n].firstarc = p;}printf("建立的邻接表为:\n"); //输出建立好的邻接表for(i = 1; i <= G->vexnum; i++){printf("%d",G->vertices[i].data);for(p = G->vertices[i].firstarc; p; p = p->nextarc)printf("%3d",p->adjvex);printf("\n");}}void FindInDegree(ALGraph G, int indegree[])//求入度操作{int i;for (i = 1; i <= G.vexnum; i++){indegree[i] = 0;}for (i = 1; i <= G.vexnum; i++){while (G.vertices[i].firstarc){indegree[G.vertices[i].firstarc->adjvex]++;G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;}}}void TopologicalSort(ALGraph G) //进行拓扑排序{int indegree[M];int i, k, n;int count = 0;ArcNode *p;SqStack S;FindInDegree(G, indegree);InitStack(&S);for (i = 1; i <= G.vexnum; i++){printf("第%d个点的入度为%d \n", i, indegree[i]);}printf("\n");for ( i = 1; i <= G.vexnum; i++){if (!indegree[i])Push(&S,i);}printf("进行拓扑排序输出顺序为:"); //输出结果while(!StackEmpty(&S)){Pop(&S,&n);printf("%4d",G.vertices[n].data);count++;for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc){k = p->adjvex;if (!(--indegree[k])){Push(&S,k);}}}printf("\n");if (count < G.vexnum){printf("出现错误\n");}else{printf("排序成功\n");}}int main(void) //主函数{ALGraph G;CreatGraph(&G);TopologicalSort(G);system("pause");return 0;}。