第1关:图的邻接矩阵存储及图初始化
本关任务:根据下面的描述和要求,完成图的邻接矩阵数据结构定义,及图初始化函数。
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define MAX 100
typedef struct {
int vex;
int shortweight;
}ShortWeight;
typedef struct QueueNode{
int val;
struct QueueNode* next;
}QueueNode;
typedef struct Queue{
QueueNode *head;
QueueNode *tail;
}Queue;
//邻接矩阵数据结构
typedef struct{
int vcount;//顶点数
int type ;//0 无向图,1 有向图
char vexs[N] ; // 顶点信息
int arcs[N][N]; //关系矩阵
} GraphMatrix;
//邻接表数据结构
struct EdgeNode { //边表中的结点
int endvex; //相邻顶点在顶点表中下标
int weight; //边的权
struct EdgeNode * nextedge; //链字段
};
typedef struct EdgeNode * EdgeList;
typedef struct
{
char vertex; //记录顶点信息
int degree;//用于记录顶点的入度,在拓扑排序时需使用
EdgeList edgelist; //指向边表的指针
} VexNode;
typedef struct{
VexNode *vexs[N]; //N个顶点
int type ;//0 无向图,1 有向图
int vcount;//顶点数
} GraphList;
/*第一关 完成图初始化
*/
void printGraph(GraphMatrix *G)
{//本函数输出图的邻接矩阵
int i,j;
for(i=0;i<G->vcount;i++)
{
// printf("%c ",G->vexs[i]);
for( j=0;j<G->vcount;j++)
printf("%d ",G->arcs[i][j]);
printf("\n");
}
}
/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
GraphMatrix *G;
G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
int t,v,s;
scanf("%d %d %d",&t,&v,&s);
G->vcount=v;
G->type=t;
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
G->arcs[i][j]=0;
}
}
int head,tail;
if(t==0)
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
G->arcs[tail][head]=1;
}
if(t==1){
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
}
}
return G;
}
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList* initGraphList()
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
GraphList* G = (GraphList*)malloc(sizeof(GraphList));
int t, v, s;
scanf("%d%d%d", &t, &v, &s);
G->vcount = v;
G->type = t;
int i, j, k, l;
char vex[N];
char ch = getchar();
for (i = 0; i < v; i++) {
scanf("%c", &vex[i]);
}
for (i = 0; i < v; i++) {
G->vexs[i] = (VexNode*)malloc(sizeof(VexNode));
G->vexs[i]->vertex = vex[i];
G->vexs[i]->edgelist = (EdgeList)malloc(sizeof(struct EdgeNode));
G->vexs[i]->edgelist->nextedge = NULL;
}
for (i = 0; i < s; i++) {
int head, tail,w;
scanf("%d %d %d", &head, &tail,&w);
if (t == 0) {
for (k = 0; k < v; k++) {
if (G->vexs[k]->vertex - '0' == head) {
EdgeList node1 = (EdgeList)malloc(sizeof(struct EdgeNode));
for (j = 0; j < v; j++) {
if (vex[j] - '0' == tail) {
node1->weight = w;
node1->endvex = j;
node1->nextedge = G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge = node1;
break;
}
}
for (j = 0; j < v; j++) {
if (G->vexs[j]->vertex - '0' == tail) {
EdgeList node2 = (EdgeList)malloc(sizeof(struct EdgeNode));
for (l = 0; l < v; l++) {
if (vex[l] - '0' == head) {
node2->weight = w;
node2->endvex = l;
node2->nextedge = G->vexs[j]->edgelist->nextedge;
G->vexs[j]->edgelist->nextedge = node2;
break;
}
}
}
}
}
}
}
}
return G;
}
void printGraphLit( GraphList *G)
{
/*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
int i;
for(i=0;i<G->vcount;i++){
printf("%c->",G->vexs[i]->vertex);
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d->",tp->endvex);
tp=tp->nextedge;
}
printf("%d\n",tp->endvex);
}
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
int i,j;
printf("%c ",G->vexs[0]->vertex);
visited[0]=1;
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
for(i=N-1;i>=0;i--){
if(visited[i]==1){
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL && visited[tp->endvex]==0){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
}
}
}
/*第四关 完成图的深度遍历(周游),可根据需要添加自定义函数
*/
int visited2[N];
void DFS_list(GraphList *G)
{
int i,j,k;
for(i=0;i<N;i++){
visited2[i]=0;
}
printf("%c ",G->vexs[0]->vertex);
visited2[0]=1;
EdgeList tp=G->vexs[0]->edgelist->nextedge;
printf("%d ",tp->endvex);
visited2[tp->endvex]=1;
int num=4;
while(1){
for(i=0;i<G->vcount;i++){
if(G->vexs[i]->vertex-'0'==tp->endvex){
EdgeList tp2=G->vexs[i]->edgelist->nextedge;
if(visited2[tp2->endvex]==0){
tp=tp2;
printf("%d ",tp2->endvex);
visited2[tp2->endvex]=1;
break;
}
else if(visited2[tp2->endvex]==1){
for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
if(visited2[tp2->endvex]==0){
tp=tp2;
printf("%d ",tp2->endvex);
visited2[tp2->endvex]=1;
break;
}
}
}
}
}
int count=0;
for(i=0;i<N;i++){
if(visited2[i]==1) count++;
}
if(count==G->vcount) break;
}
}
/*第五关 生成图的拓扑排序,可根据需要添加自定义函数
*/
void QueueInit(Queue* pq) {
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, int x) {
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->val = x;
newnode->next = NULL;
if (pq->tail == NULL) {
pq->head = pq->tail = newnode;
}
else {
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq) {
if (pq->head->next == NULL) {
pq->head = pq->tail = NULL;
}
else {
QueueNode* next = pq->head->next;
pq->head = next;
}
}
int QueueFront(Queue* pq) {
return pq->head->val;
}
int QueueEmpty(Queue* pq) {
return pq->head == NULL;
}
void Top_list(GraphList* G)
{
Queue* Q=(Queue *)malloc(sizeof(Queue));
QueueInit(Q);
int i;
int deg[N];
for (i = 0; i < N; i++) {
deg[i] = 0;
}
for (i = 0; i < N; i++) {
deg[i] = G->vexs[i]->degree;
}
for (i = 0; i < N; i++) {
if (deg[i] == 0) {
QueuePush(Q, i);
}
}
while (!QueueEmpty(Q)) {
int j = QueueFront(Q);
printf("%d ", j);
QueuePop(Q);
EdgeList p;
p = G->vexs[j]->edgelist->nextedge;
while (p != NULL) {
deg[p->endvex]--;
if (deg[p->endvex] == 0) {
QueuePush(Q, p->endvex);
}
p = p->nextedge;
}
}
}
/*第六关 prim算法生成最小生成树
*/
int GetShortWeight(GraphList* G,ShortWeight *shortw) {
int i;
int min = MAX;
int loc;
for (i = 1; i < G->vcount; i++) {
if (min > shortw[i].shortweight && shortw[i].shortweight != 0) {
min = shortw[i].shortweight;
loc = i;
}
}
return loc;
}
void Prim_list(GraphList* G)
{
int i, j, k;
ShortWeight shortw[10];
for (i = 0; i < 10; i++) {
shortw[i].shortweight = MAX;
}
k = 0;
EdgeList tp = G->vexs[k]->edgelist->nextedge;
while (tp) {
shortw[tp->endvex].shortweight= tp->weight;
shortw[tp->endvex].vex = k;
tp = tp->nextedge;
}
shortw[k].shortweight = 0;
for (i = 0; i < G->vcount - 1; i++) {
k = GetShortWeight(G, shortw);
printf("%d %d\n", shortw[k].vex, k);
shortw[k].shortweight = 0;
EdgeList tp2 = G->vexs[k]->edgelist->nextedge;
while (tp2) {
if (tp2->weight < shortw[tp2->endvex].shortweight) {
shortw[tp2->endvex].shortweight = tp2->weight;
shortw[tp2->endvex].vex = k;
}
tp2 = tp2->nextedge;
}
}
}
/*第七关 Kruskal算法生成最小生成树
*/
void Kruskal_list(GraphList *G)
{
}
/*第八关 Dijistra算法求最短路径
*/
void Dijkstra_list(GraphList *G)
{
}
第2关:图的邻接表存储及图初始化
本关任务:编写一个能输入图的基本信息(含图的类型,图的顶点,边等),并用邻接表存储图的程序。
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define MAX 100
typedef struct {
int vex;
int shortweight;
}ShortWeight;
typedef struct QueueNode{
int val;
struct QueueNode* next;
}QueueNode;
typedef struct Queue{
QueueNode *head;
QueueNode *tail;
}Queue;
//邻接矩阵数据结构
typedef struct{
int vcount;//顶点数
int type ;//0 无向图,1 有向图
char vexs[N] ; // 顶点信息
int arcs[N][N]; //关系矩阵
} GraphMatrix;
//邻接表数据结构
struct EdgeNode { //边表中的结点
int endvex; //相邻顶点在顶点表中下标
int weight; //边的权
struct EdgeNode * nextedge; //链字段
};
typedef struct EdgeNode * EdgeList;
typedef struct
{
char vertex; //记录顶点信息
int degree;//用于记录顶点的入度,在拓扑排序时需使用
EdgeList edgelist; //指向边表的指针
} VexNode;
typedef struct{
VexNode *vexs[N]; //N个顶点
int type ;//0 无向图,1 有向图
int vcount;//顶点数
} GraphList;
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList *initGraphList()
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
GraphList *G=(GraphList*)malloc(sizeof(GraphList));
int t,v,s;
scanf("%d%d%d",&t,&v,&s);
G->vcount=v;
G->type=t;
int i,j,k,l;
char vex[N];
char ch=getchar();
for(i=0;i<v;i++){
scanf("%c",&vex[i]);
}
for(i=0;i<v;i++){
G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
G->vexs[i]->vertex=vex[i];
G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
G->vexs[i]->edgelist->nextedge=NULL;
G->vexs[i]->degree=0;
}
for(i=0;i<s;i++){
int head,tail;
scanf("%d %d",&head,&tail);
if(t==0){
for(k=0;k<v;k++){
if(G->vexs[k]->vertex-'0'==head){
EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
for(j=0;j<v;j++){
if(vex[j]-'0'==tail){
node1->endvex=j;
node1->nextedge=G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge=node1;
break;
}
}
for(j=0;j<v;j++){
if(G->vexs[j]->vertex-'0'==tail){
EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
for(l=0;l<v;l++){
if(vex[l]-'0'==head){
node2->endvex=l;
node2->nextedge=G->vexs[j]->edgelist->nextedge;
G->vexs[j]->edgelist->nextedge=node2;
break;
}
}
}
}
}
}
}
else if(t==1){
for(k=0;k<v;k++){
if(G->vexs[k]->vertex-'0'==head){
EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
for(j=0;j<v;j++){
if(vex[j]-'0'==tail){
for(l=0;l<G->vcount;l++){
if(G->vexs[l]->vertex-'0'==tail){
G->vexs[l]->degree++;
}
}
node1->endvex=j;
node1->nextedge=G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge=node1;
break;
}
}
}
}
}
}
return G;
}
void printGraphLit( GraphList *G)
{
/*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
int i;
for(i=0;i<G->vcount;i++){
printf("%c->",G->vexs[i]->vertex);
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d->",tp->endvex);
tp=tp->nextedge;
}
printf("%d\n",tp->endvex);
}
}
第3关:图的广度遍历
本关任务:完成程序能实现图的广度遍历。
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define MAX 100
typedef struct {
int vex;
int shortweight;
}ShortWeight;
typedef struct QueueNode{
int val;
struct QueueNode* next;
}QueueNode;
typedef struct Queue{
QueueNode *head;
QueueNode *tail;
}Queue;
//邻接矩阵数据结构
typedef struct{
int vcount;//顶点数
int type ;//0 无向图,1 有向图
char vexs[N] ; // 顶点信息
int arcs[N][N]; //关系矩阵
} GraphMatrix;
//邻接表数据结构
struct EdgeNode { //边表中的结点
int endvex; //相邻顶点在顶点表中下标
int weight; //边的权
struct EdgeNode * nextedge; //链字段
};
typedef struct EdgeNode * EdgeList;
typedef struct
{
char vertex; //记录顶点信息
int degree;//用于记录顶点的入度,在拓扑排序时需使用
EdgeList edgelist; //指向边表的指针
} VexNode;
typedef struct{
VexNode *vexs[N]; //N个顶点
int type ;//0 无向图,1 有向图
int vcount;//顶点数
} GraphList;
/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
GraphMatrix *G;
G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
int t,v,s;
scanf("%d %d %d",&t,&v,&s);
G->vcount=v;
G->type=t;
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
G->arcs[i][j]=0;
}
}
int head,tail;
if(t==0)
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
G->arcs[tail][head]=1;
}
if(t==1){
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
}
}
return G;
}
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList *initGraphList()
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
GraphList *G=(GraphList*)malloc(sizeof(GraphList));
int t,v,s;
scanf("%d%d%d",&t,&v,&s);
G->vcount=v;
G->type=t;
int i,j,k,l;
char vex[N];
char ch=getchar();
for(i=0;i<v;i++){
scanf("%c",&vex[i]);
}
for(i=0;i<v;i++){
G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
G->vexs[i]->vertex=vex[i];
G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
G->vexs[i]->edgelist->nextedge=NULL;
G->vexs[i]->degree=0;
}
for(i=0;i<s;i++){
int head,tail;
scanf("%d %d",&head,&tail);
if(t==0){
for(k=0;k<v;k++){
if(G->vexs[k]->vertex-'0'==head){
EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
for(j=0;j<v;j++){
if(vex[j]-'0'==tail){
node1->endvex=j;
node1->nextedge=G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge=node1;
break;
}
}
for(j=0;j<v;j++){
if(G->vexs[j]->vertex-'0'==tail){
EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
for(l=0;l<v;l++){
if(vex[l]-'0'==head){
node2->endvex=l;
node2->nextedge=G->vexs[j]->edgelist->nextedge;
G->vexs[j]->edgelist->nextedge=node2;
break;
}
}
}
}
}
}
}
else if(t==1){
for(k=0;k<v;k++){
if(G->vexs[k]->vertex-'0'==head){
EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
for(j=0;j<v;j++){
if(vex[j]-'0'==tail){
for(l=0;l<G->vcount;l++){
if(G->vexs[l]->vertex-'0'==tail){
G->vexs[l]->degree++;
}
}
node1->endvex=j;
node1->nextedge=G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge=node1;
break;
}
}
}
}
}
}
return G;
}
void printGraphLit( GraphList *G)
{
/*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
int i;
for(i=0;i<G->vcount;i++){
printf("%c->",G->vexs[i]->vertex);
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d->",tp->endvex);
tp=tp->nextedge;
}
printf("%d\n",tp->endvex);
}
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
int i,j;
printf("%c ",G->vexs[0]->vertex);
visited[0]=1;
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
for(i=N-1;i>=0;i--){
if(visited[i]==1){
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL && visited[tp->endvex]==0){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
}
}
}
第4关:图的深度遍历
本关任务:完成程序能实现图的深度遍历。
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define MAX 100
typedef struct {
int vex;
int shortweight;
}ShortWeight;
typedef struct QueueNode{
int val;
struct QueueNode* next;
}QueueNode;
typedef struct Queue{
QueueNode *head;
QueueNode *tail;
}Queue;
//邻接矩阵数据结构
typedef struct{
int vcount;//顶点数
int type ;//0 无向图,1 有向图
char vexs[N] ; // 顶点信息
int arcs[N][N]; //关系矩阵
} GraphMatrix;
//邻接表数据结构
struct EdgeNode { //边表中的结点
int endvex; //相邻顶点在顶点表中下标
int weight; //边的权
struct EdgeNode * nextedge; //链字段
};
typedef struct EdgeNode * EdgeList;
typedef struct
{
char vertex; //记录顶点信息
int degree;//用于记录顶点的入度,在拓扑排序时需使用
EdgeList edgelist; //指向边表的指针
} VexNode;
typedef struct{
VexNode *vexs[N]; //N个顶点
int type ;//0 无向图,1 有向图
int vcount;//顶点数
} GraphList;
/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
GraphMatrix *G;
G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
int t,v,s;
scanf("%d %d %d",&t,&v,&s);
G->vcount=v;
G->type=t;
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
G->arcs[i][j]=0;
}
}
int head,tail;
if(t==0)
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
G->arcs[tail][head]=1;
}
if(t==1){
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
}
}
return G;
}
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList *initGraphList()
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
GraphList *G=(GraphList*)malloc(sizeof(GraphList));
int t,v,s;
scanf("%d%d%d",&t,&v,&s);
G->vcount=v;
G->type=t;
int i,j,k,l;
char vex[N];
char ch=getchar();
for(i=0;i<v;i++){
scanf("%c",&vex[i]);
}
for(i=0;i<v;i++){
G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
G->vexs[i]->vertex=vex[i];
G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
G->vexs[i]->edgelist->nextedge=NULL;
G->vexs[i]->degree=0;
}
for(i=0;i<s;i++){
int head,tail;
scanf("%d %d",&head,&tail);
if(t==0){
for(k=0;k<v;k++){
if(G->vexs[k]->vertex-'0'==head){
EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
for(j=0;j<v;j++){
if(vex[j]-'0'==tail){
node1->endvex=j;
node1->nextedge=G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge=node1;
break;
}
}
for(j=0;j<v;j++){
if(G->vexs[j]->vertex-'0'==tail){
EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
for(l=0;l<v;l++){
if(vex[l]-'0'==head){
node2->endvex=l;
node2->nextedge=G->vexs[j]->edgelist->nextedge;
G->vexs[j]->edgelist->nextedge=node2;
break;
}
}
}
}
}
}
}
else if(t==1){
for(k=0;k<v;k++){
if(G->vexs[k]->vertex-'0'==head){
EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
for(j=0;j<v;j++){
if(vex[j]-'0'==tail){
for(l=0;l<G->vcount;l++){
if(G->vexs[l]->vertex-'0'==tail){
G->vexs[l]->degree++;
}
}
node1->endvex=j;
node1->nextedge=G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge=node1;
break;
}
}
}
}
}
}
return G;
}
void printGraphLit( GraphList *G)
{
/*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
int i;
for(i=0;i<G->vcount;i++){
printf("%c->",G->vexs[i]->vertex);
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d->",tp->endvex);
tp=tp->nextedge;
}
printf("%d\n",tp->endvex);
}
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
int i,j;
printf("%c ",G->vexs[0]->vertex);
visited[0]=1;
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
for(i=N-1;i>=0;i--){
if(visited[i]==1){
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL && visited[tp->endvex]==0){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
}
}
}
/*第四关 完成图的深度遍历(周游),可根据需要添加自定义函数
*/
int visited2[N];
void DFS_list(GraphList *G)
{
int i,j,k;
for(i=0;i<N;i++){
visited2[i]=0;
}
printf("%c ",G->vexs[0]->vertex);
visited2[0]=1;
EdgeList tp=G->vexs[0]->edgelist->nextedge;
printf("%d ",tp->endvex);
visited2[tp->endvex]=1;
int num=4;
while(1){
for(i=0;i<G->vcount;i++){
if(G->vexs[i]->vertex-'0'==tp->endvex){
EdgeList tp2=G->vexs[i]->edgelist->nextedge;
if(visited2[tp2->endvex]==0){
tp=tp2;
printf("%d ",tp2->endvex);
visited2[tp2->endvex]=1;
break;
}
else if(visited2[tp2->endvex]==1){
for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
if(visited2[tp2->endvex]==0){
tp=tp2;
printf("%d ",tp2->endvex);
visited2[tp2->endvex]=1;
break;
}
}
}
}
}
int count=0;
for(i=0;i<N;i++){
if(visited2[i]==1) count++;
}
if(count==G->vcount) break;
}
}
第5关:拓扑排序
本关任务:编写一个能输出有向无环图的拓扑排序的函数。文章来源:https://www.toymoban.com/news/detail-760341.html
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define MAX 100
typedef struct {
int vex;
int shortweight;
}ShortWeight;
typedef struct QueueNode{
int val;
struct QueueNode* next;
}QueueNode;
typedef struct Queue{
QueueNode *head;
QueueNode *tail;
}Queue;
//邻接矩阵数据结构
typedef struct{
int vcount;//顶点数
int type ;//0 无向图,1 有向图
char vexs[N] ; // 顶点信息
int arcs[N][N]; //关系矩阵
} GraphMatrix;
//邻接表数据结构
struct EdgeNode { //边表中的结点
int endvex; //相邻顶点在顶点表中下标
int weight; //边的权
struct EdgeNode * nextedge; //链字段
};
typedef struct EdgeNode * EdgeList;
typedef struct
{
char vertex; //记录顶点信息
int degree;//用于记录顶点的入度,在拓扑排序时需使用
EdgeList edgelist; //指向边表的指针
} VexNode;
typedef struct{
VexNode *vexs[N]; //N个顶点
int type ;//0 无向图,1 有向图
int vcount;//顶点数
} GraphList;
/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
GraphMatrix *G;
G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
int t,v,s;
scanf("%d %d %d",&t,&v,&s);
G->vcount=v;
G->type=t;
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
G->arcs[i][j]=0;
}
}
int head,tail;
if(t==0)
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
G->arcs[tail][head]=1;
}
if(t==1){
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
}
}
return G;
}
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList *initGraphList()
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
GraphList *G=(GraphList*)malloc(sizeof(GraphList));
int t,v,s;
scanf("%d%d%d",&t,&v,&s);
G->vcount=v;
G->type=t;
int i,j,k,l;
char vex[N];
char ch=getchar();
for(i=0;i<v;i++){
scanf("%c",&vex[i]);
}
for(i=0;i<v;i++){
G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
G->vexs[i]->vertex=vex[i];
G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
G->vexs[i]->edgelist->nextedge=NULL;
G->vexs[i]->degree=0;
}
for(i=0;i<s;i++){
int head,tail;
scanf("%d %d",&head,&tail);
if(t==0){
for(k=0;k<v;k++){
if(G->vexs[k]->vertex-'0'==head){
EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
for(j=0;j<v;j++){
if(vex[j]-'0'==tail){
node1->endvex=j;
node1->nextedge=G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge=node1;
break;
}
}
for(j=0;j<v;j++){
if(G->vexs[j]->vertex-'0'==tail){
EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
for(l=0;l<v;l++){
if(vex[l]-'0'==head){
node2->endvex=l;
node2->nextedge=G->vexs[j]->edgelist->nextedge;
G->vexs[j]->edgelist->nextedge=node2;
break;
}
}
}
}
}
}
}
else if(t==1){
for(k=0;k<v;k++){
if(G->vexs[k]->vertex-'0'==head){
EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
for(j=0;j<v;j++){
if(vex[j]-'0'==tail){
for(l=0;l<G->vcount;l++){
if(G->vexs[l]->vertex-'0'==tail){
G->vexs[l]->degree++;
}
}
node1->endvex=j;
node1->nextedge=G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge=node1;
break;
}
}
}
}
}
}
return G;
}
void printGraphLit( GraphList *G)
{
/*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
int i;
for(i=0;i<G->vcount;i++){
printf("%c->",G->vexs[i]->vertex);
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d->",tp->endvex);
tp=tp->nextedge;
}
printf("%d\n",tp->endvex);
}
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
int i,j;
printf("%c ",G->vexs[0]->vertex);
visited[0]=1;
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
for(i=N-1;i>=0;i--){
if(visited[i]==1){
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL && visited[tp->endvex]==0){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
}
}
}
/*第四关 完成图的深度遍历(周游),可根据需要添加自定义函数
*/
int visited2[N];
void DFS_list(GraphList *G)
{
int i,j,k;
for(i=0;i<N;i++){
visited2[i]=0;
}
printf("%c ",G->vexs[0]->vertex);
visited2[0]=1;
EdgeList tp=G->vexs[0]->edgelist->nextedge;
printf("%d ",tp->endvex);
visited2[tp->endvex]=1;
int num=4;
while(1){
for(i=0;i<G->vcount;i++){
if(G->vexs[i]->vertex-'0'==tp->endvex){
EdgeList tp2=G->vexs[i]->edgelist->nextedge;
if(visited2[tp2->endvex]==0){
tp=tp2;
printf("%d ",tp2->endvex);
visited2[tp2->endvex]=1;
break;
}
else if(visited2[tp2->endvex]==1){
for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
if(visited2[tp2->endvex]==0){
tp=tp2;
printf("%d ",tp2->endvex);
visited2[tp2->endvex]=1;
break;
}
}
}
}
}
int count=0;
for(i=0;i<N;i++){
if(visited2[i]==1) count++;
}
if(count==G->vcount) break;
}
}
/*第五关 生成图的拓扑排序,可根据需要添加自定义函数
*/
void QueueInit(Queue* pq) {
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, int x) {
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->val = x;
newnode->next = NULL;
if (pq->tail == NULL) {
pq->head = pq->tail = newnode;
}
else {
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq) {
if (pq->head->next == NULL) {
pq->head = pq->tail = NULL;
}
else {
QueueNode* next = pq->head->next;
pq->head = next;
}
}
int QueueFront(Queue* pq) {
return pq->head->val;
}
int QueueEmpty(Queue* pq) {
return pq->head == NULL;
}
void Top_list(GraphList* G)
{
Queue* Q=(Queue *)malloc(sizeof(Queue));
QueueInit(Q);
int i;
int deg[N];
for (i = 0; i < N; i++) {
deg[i] = 0;
}
for (i = 0; i < N; i++) {
deg[i] = G->vexs[i]->degree;
}
for (i = 0; i < N; i++) {
if (deg[i] == 0) {
QueuePush(Q, i);
}
}
while (!QueueEmpty(Q)) {
int j = QueueFront(Q);
printf("%d ", j);
QueuePop(Q);
EdgeList p;
p = G->vexs[j]->edgelist->nextedge;
while (p != NULL) {
deg[p->endvex]--;
if (deg[p->endvex] == 0) {
QueuePush(Q, p->endvex);
}
p = p->nextedge;
}
}
}
第6关:prim算法生成最小生成树
本关任务:实现prim算法生成最小生成树。文章来源地址https://www.toymoban.com/news/detail-760341.html
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define MAX 100
typedef struct {
int vex;
int shortweight;
}ShortWeight;
typedef struct QueueNode{
int val;
struct QueueNode* next;
}QueueNode;
typedef struct Queue{
QueueNode *head;
QueueNode *tail;
}Queue;
//邻接矩阵数据结构
typedef struct{
int vcount;//顶点数
int type ;//0 无向图,1 有向图
char vexs[N] ; // 顶点信息
int arcs[N][N]; //关系矩阵
} GraphMatrix;
//邻接表数据结构
struct EdgeNode { //边表中的结点
int endvex; //相邻顶点在顶点表中下标
int weight; //边的权
struct EdgeNode * nextedge; //链字段
};
typedef struct EdgeNode * EdgeList;
typedef struct
{
char vertex; //记录顶点信息
int degree;//用于记录顶点的入度,在拓扑排序时需使用
EdgeList edgelist; //指向边表的指针
} VexNode;
typedef struct{
VexNode *vexs[N]; //N个顶点
int type ;//0 无向图,1 有向图
int vcount;//顶点数
} GraphList;
/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
GraphMatrix *G;
G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
int t,v,s;
scanf("%d %d %d",&t,&v,&s);
G->vcount=v;
G->type=t;
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
G->arcs[i][j]=0;
}
}
int head,tail;
if(t==0)
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
G->arcs[tail][head]=1;
}
if(t==1){
for(i=0;i<N;i++){
scanf("%d %d",&head,&tail);
G->arcs[head][tail]=1;
}
}
return G;
}
GraphList* initGraphList()
{
/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
GraphList* G = (GraphList*)malloc(sizeof(GraphList));
int t, v, s;
scanf("%d%d%d", &t, &v, &s);
G->vcount = v;
G->type = t;
int i, j, k, l;
char vex[N];
char ch = getchar();
for (i = 0; i < v; i++) {
scanf("%c", &vex[i]);
}
for (i = 0; i < v; i++) {
G->vexs[i] = (VexNode*)malloc(sizeof(VexNode));
G->vexs[i]->vertex = vex[i];
G->vexs[i]->edgelist = (EdgeList)malloc(sizeof(struct EdgeNode));
G->vexs[i]->edgelist->nextedge = NULL;
}
for (i = 0; i < s; i++) {
int head, tail,w;
scanf("%d %d %d", &head, &tail,&w);
if (t == 0) {
for (k = 0; k < v; k++) {
if (G->vexs[k]->vertex - '0' == head) {
EdgeList node1 = (EdgeList)malloc(sizeof(struct EdgeNode));
for (j = 0; j < v; j++) {
if (vex[j] - '0' == tail) {
node1->weight = w;
node1->endvex = j;
node1->nextedge = G->vexs[k]->edgelist->nextedge;
G->vexs[k]->edgelist->nextedge = node1;
break;
}
}
for (j = 0; j < v; j++) {
if (G->vexs[j]->vertex - '0' == tail) {
EdgeList node2 = (EdgeList)malloc(sizeof(struct EdgeNode));
for (l = 0; l < v; l++) {
if (vex[l] - '0' == head) {
node2->weight = w;
node2->endvex = l;
node2->nextedge = G->vexs[j]->edgelist->nextedge;
G->vexs[j]->edgelist->nextedge = node2;
break;
}
}
}
}
}
}
}
}
return G;
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
int i,j;
printf("%c ",G->vexs[0]->vertex);
visited[0]=1;
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
for(i=N-1;i>=0;i--){
if(visited[i]==1){
EdgeList tp=G->vexs[i]->edgelist->nextedge;
while(tp->nextedge!=NULL && visited[tp->endvex]==0){
printf("%d ",tp->endvex);
visited[tp->endvex]=1;
tp=tp->nextedge;
}
}
}
}
/*第四关 完成图的深度遍历(周游),可根据需要添加自定义函数
*/
int visited2[N];
void DFS_list(GraphList *G)
{
int i,j,k;
for(i=0;i<N;i++){
visited2[i]=0;
}
printf("%c ",G->vexs[0]->vertex);
visited2[0]=1;
EdgeList tp=G->vexs[0]->edgelist->nextedge;
printf("%d ",tp->endvex);
visited2[tp->endvex]=1;
int num=4;
while(1){
for(i=0;i<G->vcount;i++){
if(G->vexs[i]->vertex-'0'==tp->endvex){
EdgeList tp2=G->vexs[i]->edgelist->nextedge;
if(visited2[tp2->endvex]==0){
tp=tp2;
printf("%d ",tp2->endvex);
visited2[tp2->endvex]=1;
break;
}
else if(visited2[tp2->endvex]==1){
for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
if(visited2[tp2->endvex]==0){
tp=tp2;
printf("%d ",tp2->endvex);
visited2[tp2->endvex]=1;
break;
}
}
}
}
}
int count=0;
for(i=0;i<N;i++){
if(visited2[i]==1) count++;
}
if(count==G->vcount) break;
}
}
/*第五关 生成图的拓扑排序,可根据需要添加自定义函数
*/
void QueueInit(Queue* pq) {
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, int x) {
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->val = x;
newnode->next = NULL;
if (pq->tail == NULL) {
pq->head = pq->tail = newnode;
}
else {
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq) {
if (pq->head->next == NULL) {
pq->head = pq->tail = NULL;
}
else {
QueueNode* next = pq->head->next;
pq->head = next;
}
}
int QueueFront(Queue* pq) {
return pq->head->val;
}
int QueueEmpty(Queue* pq) {
return pq->head == NULL;
}
void Top_list(GraphList* G)
{
Queue* Q=(Queue *)malloc(sizeof(Queue));
QueueInit(Q);
int i;
int deg[N];
for (i = 0; i < N; i++) {
deg[i] = 0;
}
for (i = 0; i < N; i++) {
deg[i] = G->vexs[i]->degree;
}
for (i = 0; i < N; i++) {
if (deg[i] == 0) {
QueuePush(Q, i);
}
}
while (!QueueEmpty(Q)) {
int j = QueueFront(Q);
printf("%d ", j);
QueuePop(Q);
EdgeList p;
p = G->vexs[j]->edgelist->nextedge;
while (p != NULL) {
deg[p->endvex]--;
if (deg[p->endvex] == 0) {
QueuePush(Q, p->endvex);
}
p = p->nextedge;
}
}
}
/*第六关 prim算法生成最小生成树
*/
int GetShortWeight(GraphList* G,ShortWeight *shortw) {
int i;
int min = MAX;
int loc;
for (i = 1; i < G->vcount; i++) {
if (min > shortw[i].shortweight && shortw[i].shortweight != 0) {
min = shortw[i].shortweight;
loc = i;
}
}
return loc;
}
void Prim_list(GraphList* G)
{
int i, j, k;
ShortWeight shortw[10];
for (i = 0; i < 10; i++) {
shortw[i].shortweight = MAX;
}
k = 0;
EdgeList tp = G->vexs[k]->edgelist->nextedge;
while (tp) {
shortw[tp->endvex].shortweight= tp->weight;
shortw[tp->endvex].vex = k;
tp = tp->nextedge;
}
shortw[k].shortweight = 0;
for (i = 0; i < G->vcount - 1; i++) {
k = GetShortWeight(G, shortw);
printf("%d %d\n", shortw[k].vex, k);
shortw[k].shortweight = 0;
EdgeList tp2 = G->vexs[k]->edgelist->nextedge;
while (tp2) {
if (tp2->weight < shortw[tp2->endvex].shortweight) {
shortw[tp2->endvex].shortweight = tp2->weight;
shortw[tp2->endvex].vex = k;
}
tp2 = tp2->nextedge;
}
}
}
到了这里,关于头歌数据结构——图——课上课后练的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!