发布时间 : 2024/4/30 0:31:09 星期二 文章数据结构课程设计-图的遍历和构建更新完毕开始阅读2964e7a0f524ccbff1218486

{

scanf(\ /* 读入边（Vi,Vj） */

s=(enode*)malloc(sizeof(enode)); /* 生成邻接点序号为j的表结点*s */ s->adjvex=j; s->next=a[i].link;

a[i].link=s; /* 将*s插入顶点Vi的边表头部 */

s=(enode*)malloc(sizeof(enode)); /* 生成邻接点序号为i的边表结点*s */ s->adjvex=i; s->next=a[j].link;

a[j].link=s; /* 将*s插入顶点Vj的边表头部 */ }

printf(\输出的邻接表为：\\n\ for(i=0;i

printf(\ \ s=a[i].link; while(s) {

printf(\

s=s->next; }

} /* 邻接表的输出 */

printf(\输出邻接表Vi顶点的度为：\\n\ for(i=0;i

s=a[i].link; sum=0; while(s) {

sum++;

13

}

s=s->next;

printf(\的度为：%d\\n\

} /* 各顶点的度 */ }

int visited1[max]={0}; /* 定义布尔向量visited1为全程量 */

void dfs1(graph *G,int i) /* 从Vi+1出发深度优先搜索图G，G用邻接矩阵表示 */

{ int j;

printf(\ /* 访问出发点Vi+1 */ visited1[i]=1; /* 标记Vi+1已被访问 */

for(j=0;jvexsnum;j++) /* 依次搜索Vi+1的邻接点 */ if((G->arcs[i][j])&&(!visited1[j]))

dfs1(G,j);/* 若Vi+1的邻接点Vi+1未曾访问过，则从Vi+1出发进行深度优先搜索 */

}

#define maxsize 80 typedef int datatype; typedef struct {

datatype data[maxsize]; int front,rear;

}sequeue; /* 顺序队列的类型 */ sequeue *p; /* p是顺序队列类型的指针 */ void setnull() /* 置队列p为空对 */ { }

int empty() /* 判别p是否为空 */

14

p->front=maxsize-1; p->rear=maxsize-1;

{ }

int front() /* 取p的队头元素 */ {

if(empty()) {

printf(\if(p->front==p->rear)

return 1;

else return 0;

return 0; }

else return p->data[(p->front+1)%maxsize]; }

int enqueue(int x) /* 将新元素x插入队列p的队尾 */ { }

int dequeue() /* 删除队列p的头元素，并返回该元素 */ {

15

if((p->rear+1)%maxsize==p->front) { } else {

p->rear=(p->rear+1)%maxsize; p->data[p->rear]=x; return x; }

printf(\return 0;

}

if(empty()) {

printf(\return 0; } else{ }

p->front=(p->front+1)%maxsize; return (p->data[p->front]);

int visited2[max]={0};

void bfs1(graph *G,int k)/*从Vi+1出发广度优先搜索图G，G用邻接矩阵表示*/

{

int i,j; setnull();

printf(\ /* 访问出发点Vk+1 */ visited2[k]=1; enqueue(k);

while(!empty()) /* 队非空时执行 */ {

i=dequeue();

for(j=0;jvexsnum;j++)

if((G->arcs[i][j])&&(!visited2[j])) {

printf(\ /* 访问Vi+1的未曾访问的邻接点Vj+1 */ visited2[j]=1;

enqueue(j); /* 访问过的顶点入队 */

}

}

}

16