邻接矩阵、邻接表表示图时的深度优先序列、广度优先序列
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/07/13 20:18:31
邻接矩阵、邻接表表示图时的深度优先序列、广度优先序列
已知一个图的顶点集V各边集G如下:
V = {0,1,2,3,4,5,6,7,8,9};
E = {(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3 ,8),(5,6),(5,8),(5,9),(6,7),(7,8),(8,9)}
当它用邻接矩阵表示和邻接表表示时,分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列.
假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的.
图 深度优先序列 广度优先序列
邻接矩阵表示时
邻接表表示时
已知一个图的顶点集V各边集G如下:
V = {0,1,2,3,4,5,6,7,8,9};
E = {(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3 ,8),(5,6),(5,8),(5,9),(6,7),(7,8),(8,9)}
当它用邻接矩阵表示和邻接表表示时,分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列.
假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的.
图 深度优先序列 广度优先序列
邻接矩阵表示时
邻接表表示时
#include
#include
#include
#include
#define maxsize 64
#define TRUE 1
#define FALSE 0
#define n 10
#define e 13
typedef 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;ivexs[i]);
for(i=1;iarcs[j][i]=1;
}
return ga;
}
void PRINT()
{
int i,j;
system("cls");
printf("\n对应的邻接矩阵是:\n\n");
for(i=1;iadjvex=i;
s->next=gl[j].link;
gl[j].link=s;
}
}
void PRINTL()
{
int i;
edgenode *s;
system("cls");
printf("\n对应的邻接表是:\n");
for(i=1;iadjvex);
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;jarcs[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;jarcs[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);
}
}
}
#include
#include
#include
#define maxsize 64
#define TRUE 1
#define FALSE 0
#define n 10
#define e 13
typedef 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;ivexs[i]);
for(i=1;iarcs[j][i]=1;
}
return ga;
}
void PRINT()
{
int i,j;
system("cls");
printf("\n对应的邻接矩阵是:\n\n");
for(i=1;iadjvex=i;
s->next=gl[j].link;
gl[j].link=s;
}
}
void PRINTL()
{
int i;
edgenode *s;
system("cls");
printf("\n对应的邻接表是:\n");
for(i=1;iadjvex);
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;jarcs[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;jarcs[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);
}
}
}
邻接矩阵、邻接表表示图时的深度优先序列、广度优先序列
求一个源代码要求显示图的邻接矩阵图的邻接表,深度广度优先遍历最小生成树PRIM算法KRUSCAL算法图的连通分
已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是
已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是
已知一个有向图如图,请分别写出从顶点a出发进行深度优先遍历和广度优先遍历所得到的顶点序列及生成树.
用邻接表表示的图进行广度优先遍历时,通常是采用()来实现算法的.
dijkstra算法是深度优先还是广度优先?
1.用邻接表表示图 广度优先搜索 通常采用什么实现算法 a 栈 b 队列 c 树 d图
深度优先搜索和广度优先搜索、A星算法三种算法的区别和联系?
已知二维数组表示的图的邻接矩阵如下图所示.试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优
请给位大虾帮忙给这个图的邻接矩阵做个深度优先遍历算法
2、设某个图的邻接表如图2,根据该临界表执行从顶点A出发的广度优先搜索算法,则经历的