数据结构题.假定无向图G有6个结点和9条边,.(1) 画出G的邻接距阵和邻接表(2) 根据邻接表从顶点3
来源:学生作业帮 编辑:神马作文网作业帮 分类:综合作业 时间:2024/09/20 06:12:19
数据结构题.假定无向图G有6个结点和9条边,.(1) 画出G的邻接距阵和邻接表(2) 根据邻接表从顶点3
假定无向图G有6个结点和9条边,并依次输入这9条边为(0,1)(0,2)(0,4)(0,5)(1,2)(2,3)(2,4)(3,4)(4,5) (1) 画出G的邻接距阵和邻接表.(2) 根据你的邻接表从顶点3出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列.
假定无向图G有6个结点和9条边,并依次输入这9条边为(0,1)(0,2)(0,4)(0,5)(1,2)(2,3)(2,4)(3,4)(4,5) (1) 画出G的邻接距阵和邻接表.(2) 根据你的邻接表从顶点3出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列.
#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<malloc.h>#define maxsize 64#define TRUE 1#define FALSE 0#define n 6#define e 9typedef char datatype ;typedef char vextype;typedef int adjtype; typedef struct { vextype vexs[maxsize]; adjtype arcs[maxsize][maxsize];}graph; typedef struct { datatype data[maxsize]; int front,rear;}sequeue; typedef struct node { int adjvex; struct node *next;}edgenode;typedef struct{ vextype vertex; edgenode *link;}vexnode; vexnode gl[maxsize];graph *ga;sequeue *Q; graph *CREATGRAPH(){ int i,j,k; char ch; system("cls"); scanf("%c",&ch); printf("\n请输入顶点信息(邻接矩阵): "); for(i=1;i<=n;i++) scanf("%c",&ga->vexs[i]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) ga->arcs[i][j]=0; printf("\n输入节点信息与权值:\n"); for(k=0;k<e;k++) { scanf("%d%d",&i,&j);//读入一条变得两端顶点序号i,j及边上的权值 ga->arcs[i][j]=1; ga->arcs[j][i]=1; } return ga;} void PRINT(){ int i,j; system("cls"); printf("\n对应的邻接矩阵是:\n\n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%5d",ga->arcs[i][j]); printf("\n"); }} void CREATADJLIST(){ int i,j,k; edgenode *s; char ch; system("cls"); printf("请输入顶点信息: "); scanf("%c",&ch); for(i=1;i<=n;i++) { gl[i].vertex=getchar(); gl[i].link=NULL; } printf("输入边表节点信息:\n"); for(k=1;k<=e;k++) { scanf("%d %d",&i,&j); s=(edgenode *)malloc(sizeof(edgenode)); s->adjvex=j; s->next=gl[i].link; gl[i].link=s; s=(edgenode *)malloc(sizeof(edgenode)); s->adjvex=i; s->next=gl[j].link; gl[j].link=s; }} void PRINTL(){ int i; edgenode *s; system("cls"); printf("\n对应的邻接表是:\n"); for(i=1;i<=n;i++) { s=gl[i].link; printf("%3c",gl[i].vertex); while(s!=NULL) { printf("%5d",s->adjvex); s=s->next; } printf("\n"); }} sequeue *SETNULL(sequeue *P){ P->front=maxsize-1; P->rear=maxsize-1; return P;} int EMPTY(sequeue *Q){ if(Q->rear==Q->front) return TRUE; else return FALSE;} sequeue *ENQUEUE(sequeue *Q,int k){ if(Q->front==(Q->rear+1)%maxsize) { printf("队列已满!\n"); return NULL; } else { Q->rear=(Q->rear+1)%maxsize; Q->data[Q->rear]=k; } return Q;}int DEQUEUE(sequeue *Q){ if(EMPTY(Q)) { printf("队列为空,无法出队!\n"); return FALSE; } else { Q->front=(Q->front+1)%maxsize; return Q->data[Q->front]; } return 1;}void BFS(int k){ int i,j; int visited[maxsize]={0}; printf("\n广度优先遍历后得到的序列是: "); Q=SETNULL(Q); printf("%3c",ga->vexs[k]); visited[k]=TRUE; Q=ENQUEUE(Q,k); while(!EMPTY(Q)) { i=DEQUEUE(Q); for(j=1;j<=n;j++) if((ga->arcs[i][j]==1)&&(!visited[j])) { printf("%3c",ga->vexs[j]); visited[j]=TRUE; Q=ENQUEUE(Q,j); } } printf("\n\n深度优先遍历后得到的序列是: "); } void BFSL(int k){ int i; int visited[maxsize]={0}; edgenode *p; Q=SETNULL(Q); printf("\n广度优先遍历后得到的序列是: "); printf("%3c",gl[k].vertex); visited[k]=TRUE; Q=ENQUEUE(Q,k); while(!EMPTY(Q)) { i=DEQUEUE(Q); p=gl[i].link; while(p!=NULL) { if(!visited[p->adjvex]) { printf("%3c",gl[p->adjvex].vertex); visited[p->adjvex]=TRUE; Q=ENQUEUE(Q,p->adjvex); } p=p->next; } } printf("\n\n深度优先遍历后得到的序列是: ");} void DFS(int i){ int j; static int visited[maxsize]={0}; printf("%3c",ga->vexs[i]); visited[i]=TRUE; for(j=1;j<=n;j++) if((ga->arcs[i][j]==1)&&(!visited[j])) DFS (j);}void DFSL(int k){ int j; edgenode *p; static int visited[maxsize]={0}; printf("%3c",gl[k].vertex); visited[k]=TRUE; p=gl[k].link; while(p) { j=p->adjvex; if(!visited[j]) DFSL(j); p=p->next; }}void main(){ int i,k; int ch; Q=malloc(sizeof(graph)); ga=malloc(sizeof(graph)); while(1) { printf("\n\n\n"); printf("输入你的选择: "); scanf("%d",&ch); switch(ch) { case 1: CREATADJLIST(); PRINTL(); printf("想从第几号结点开始: "); scanf("%d",&k); BFSL(k); DFSL(k);break; case 2: ga=CREATGRAPH(); PRINT(); printf("想从第几号结点开始: "); scanf("%d",&i); BFS(i); DFS(i);break; case 3:exit (0); } }} PS:下标从1开始的,输入矩阵的对应元素时要按你的顺序输入 输入表的顺序是要逆序输入 否则两者答案不匹配 因为表的选择要有大小要求的 你可以试一下.
数据结构题.假定无向图G有6个结点和9条边,.(1) 画出G的邻接距阵和邻接表(2) 根据邻接表从顶点3
设汁一个算法,建立无向图(n个顶点,e条边)的邻接表
对于一个具有N个顶点E条边的无向图的邻接表的表示,则表头向量大小为多少?邻接表的顶点总数为多少?(请给出详细的分析过程)
数据结构 :假设图G采用邻接表存储,试设计一个算法,求不带权无向连通图G中距离顶点v的最远的顶点?
在简单无向图G=中,如果V中的每个结点都与其余的结点邻接,则该图称为_____如果V有n个结点,那么他还是____度正则
设计一个算法,求无向图G(采用邻接表存储)的连通分量的个数
具体实现要求:1.通过键盘输入图的顶点和边信息,分别构造一个无向图的邻接矩阵和一个有向图的邻接表.2.分别对建立好的两个
已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是
无向带权图的邻接表怎么画
假设图G采用邻接表存储,设计一个算法,输出图G中从顶点u到v的所有简单路径.
2、设某个图的邻接表如图2,根据该临界表执行从顶点A出发的广度优先搜索算法,则经历的
在线急求熟悉图的两种常用的存储结构,邻接矩阵和邻接表.