国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<center id="4y0wy"></center>

<td id="4y0wy"><object id="4y0wy"></object></td>

頭歌數(shù)據(jù)結(jié)構(gòu)——圖——課上課后練

2年前作者：Sherry_liangtang分類：Toy博客閱讀(157)違法舉報

這篇具有很好參考價值的文章主要介紹了頭歌數(shù)據(jù)結(jié)構(gòu)——圖——課上課后練。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

第1關(guān)：圖的鄰接矩陣存儲及圖初始化

本關(guān)任務(wù)：根據(jù)下面的描述和要求，完成圖的鄰接矩陣數(shù)據(jù)結(jié)構(gòu)定義，及圖初始化函數(shù)。

#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;
//鄰接矩陣數(shù)據(jù)結(jié)構(gòu) 
typedef  struct{
   int vcount;//頂點數(shù)
   int type ;//0 無向圖，1 有向圖
   char  vexs[N]  ;     // 頂點信息
   int  arcs[N][N]; //關(guān)系矩陣
} GraphMatrix;
 
//鄰接表數(shù)據(jù)結(jié)構(gòu)
struct EdgeNode { //邊表中的結(jié)點
      int  endvex;    //相鄰頂點在頂點表中下標(biāo)
      int  weight;  //邊的權(quán)
      struct EdgeNode  * nextedge;   //鏈字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //記錄頂點信息
   int degree;//用于記錄頂點的入度，在拓?fù)渑判驎r需使用
   EdgeList  edgelist;  //指向邊表的指針
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N個頂點
   int type ;//0 無向圖，1 有向圖
   int vcount;//頂點數(shù)
} GraphList; 

/*第一關(guān) 完成圖初始化
*/
void printGraph(GraphMatrix *G)
{//本函數(shù)輸出圖的鄰接矩陣
 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");
 }
}

/*第一關(guān) 完成圖初始化-鄰接矩陣
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
輸出鄰接矩陣，不需要考慮輸入的數(shù)字非法情況，不輸入頂點的信息*/
   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;
}
/*第二關(guān) 完成圖初始化-鄰接表,并完成輸出圖的鄰接表函數(shù)
*/
GraphList* initGraphList()
{
	/*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
  輸出鄰接表。不需考慮輸入的數(shù)字非法情況，輸入頂點的信息*/
	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);
	}
}
/*第三關(guān) 完成圖的廣度遍歷（周游），可根據(jù)需要添加自定義函數(shù)
*/
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;
			}
		}
	}
	
}
/*第四關(guān) 完成圖的深度遍歷（周游），可根據(jù)需要添加自定義函數(shù)
*/
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;
	}
	
}
/*第五關(guān) 生成圖的拓?fù)渑判?，可根?jù)需要添加自定義函數(shù)
*/
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;
		}
	}
}
/*第六關(guān) 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;
			}
	}
}
/*第七關(guān) Kruskal算法生成最小生成樹
*/

void Kruskal_list(GraphList *G)
{


}

/*第八關(guān) Dijistra算法求最短路徑
*/

void Dijkstra_list(GraphList *G)
{


}

第2關(guān)：圖的鄰接表存儲及圖初始化

本關(guān)任務(wù)：編寫一個能輸入圖的基本信息（含圖的類型，圖的頂點，邊等），并用鄰接表存儲圖的程序。

#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;
//鄰接矩陣數(shù)據(jù)結(jié)構(gòu) 
typedef  struct{
   int vcount;//頂點數(shù)
   int type ;//0 無向圖，1 有向圖
   char  vexs[N]  ;     // 頂點信息
   int  arcs[N][N]; //關(guān)系矩陣
} GraphMatrix;
 
//鄰接表數(shù)據(jù)結(jié)構(gòu)
struct EdgeNode { //邊表中的結(jié)點
      int  endvex;    //相鄰頂點在頂點表中下標(biāo)
      int  weight;  //邊的權(quán)
      struct EdgeNode  * nextedge;   //鏈字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //記錄頂點信息
   int degree;//用于記錄頂點的入度，在拓?fù)渑判驎r需使用
   EdgeList  edgelist;  //指向邊表的指針
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N個頂點
   int type ;//0 無向圖，1 有向圖
   int vcount;//頂點數(shù)
} GraphList; 
/*第二關(guān) 完成圖初始化-鄰接表,并完成輸出圖的鄰接表函數(shù)
*/
GraphList *initGraphList()
{
  /*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
輸出鄰接表。不需考慮輸入的數(shù)字非法情況，輸入頂點的信息*/
 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關(guān)：圖的廣度遍歷

本關(guān)任務(wù)：完成程序能實現(xiàn)圖的廣度遍歷。

#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;
//鄰接矩陣數(shù)據(jù)結(jié)構(gòu) 
typedef  struct{
   int vcount;//頂點數(shù)
   int type ;//0 無向圖，1 有向圖
   char  vexs[N]  ;     // 頂點信息
   int  arcs[N][N]; //關(guān)系矩陣
} GraphMatrix;
 
//鄰接表數(shù)據(jù)結(jié)構(gòu)
struct EdgeNode { //邊表中的結(jié)點
      int  endvex;    //相鄰頂點在頂點表中下標(biāo)
      int  weight;  //邊的權(quán)
      struct EdgeNode  * nextedge;   //鏈字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //記錄頂點信息
   int degree;//用于記錄頂點的入度，在拓?fù)渑判驎r需使用
   EdgeList  edgelist;  //指向邊表的指針
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N個頂點
   int type ;//0 無向圖，1 有向圖
   int vcount;//頂點數(shù)
} GraphList; 
/*第一關(guān) 完成圖初始化-鄰接矩陣
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
輸出鄰接矩陣，不需要考慮輸入的數(shù)字非法情況，不輸入頂點的信息*/
   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;
}
/*第二關(guān) 完成圖初始化-鄰接表,并完成輸出圖的鄰接表函數(shù)
*/
GraphList *initGraphList()
{
  /*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
輸出鄰接表。不需考慮輸入的數(shù)字非法情況，輸入頂點的信息*/
 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);
	}
}
/*第三關(guān) 完成圖的廣度遍歷（周游），可根據(jù)需要添加自定義函數(shù)
*/
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關(guān)：圖的深度遍歷

本關(guān)任務(wù)：完成程序能實現(xiàn)圖的深度遍歷。

#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;
//鄰接矩陣數(shù)據(jù)結(jié)構(gòu) 
typedef  struct{
   int vcount;//頂點數(shù)
   int type ;//0 無向圖，1 有向圖
   char  vexs[N]  ;     // 頂點信息
   int  arcs[N][N]; //關(guān)系矩陣
} GraphMatrix;
 
//鄰接表數(shù)據(jù)結(jié)構(gòu)
struct EdgeNode { //邊表中的結(jié)點
      int  endvex;    //相鄰頂點在頂點表中下標(biāo)
      int  weight;  //邊的權(quán)
      struct EdgeNode  * nextedge;   //鏈字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //記錄頂點信息
   int degree;//用于記錄頂點的入度，在拓?fù)渑判驎r需使用
   EdgeList  edgelist;  //指向邊表的指針
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N個頂點
   int type ;//0 無向圖，1 有向圖
   int vcount;//頂點數(shù)
} GraphList; 
/*第一關(guān) 完成圖初始化-鄰接矩陣
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
輸出鄰接矩陣，不需要考慮輸入的數(shù)字非法情況，不輸入頂點的信息*/
   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;
}
/*第二關(guān) 完成圖初始化-鄰接表,并完成輸出圖的鄰接表函數(shù)
*/
GraphList *initGraphList()
{
  /*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
輸出鄰接表。不需考慮輸入的數(shù)字非法情況，輸入頂點的信息*/
 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);
	}
}
/*第三關(guān) 完成圖的廣度遍歷（周游），可根據(jù)需要添加自定義函數(shù)
*/
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;
			}
		}
	}
	
}
/*第四關(guān) 完成圖的深度遍歷（周游），可根據(jù)需要添加自定義函數(shù)
*/
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關(guān)：拓?fù)渑判?/h4>

本關(guān)任務(wù)：編寫一個能輸出有向無環(huán)圖的拓?fù)渑判虻暮瘮?shù)。

#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;
//鄰接矩陣數(shù)據(jù)結(jié)構(gòu) 
typedef  struct{
   int vcount;//頂點數(shù)
   int type ;//0 無向圖，1 有向圖
   char  vexs[N]  ;     // 頂點信息
   int  arcs[N][N]; //關(guān)系矩陣
} GraphMatrix;
 
//鄰接表數(shù)據(jù)結(jié)構(gòu)
struct EdgeNode { //邊表中的結(jié)點
      int  endvex;    //相鄰頂點在頂點表中下標(biāo)
      int  weight;  //邊的權(quán)
      struct EdgeNode  * nextedge;   //鏈字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //記錄頂點信息
   int degree;//用于記錄頂點的入度，在拓?fù)渑判驎r需使用
   EdgeList  edgelist;  //指向邊表的指針
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N個頂點
   int type ;//0 無向圖，1 有向圖
   int vcount;//頂點數(shù)
} GraphList; 
/*第一關(guān) 完成圖初始化-鄰接矩陣
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
輸出鄰接矩陣，不需要考慮輸入的數(shù)字非法情況，不輸入頂點的信息*/
   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;
}
/*第二關(guān) 完成圖初始化-鄰接表,并完成輸出圖的鄰接表函數(shù)
*/
GraphList *initGraphList()
{
  /*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
輸出鄰接表。不需考慮輸入的數(shù)字非法情況，輸入頂點的信息*/
 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);
	}
}
/*第三關(guān) 完成圖的廣度遍歷（周游），可根據(jù)需要添加自定義函數(shù)
*/
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;
			}
		}
	}
	
}
/*第四關(guān) 完成圖的深度遍歷（周游），可根據(jù)需要添加自定義函數(shù)
*/
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;
	}
	
}
/*第五關(guān) 生成圖的拓?fù)渑判颍筛鶕?jù)需要添加自定義函數(shù)
*/
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關(guān)：prim算法生成最小生成樹

本關(guān)任務(wù)：實現(xiàn)prim算法生成最小生成樹。文章來源地址http://www.zghlxwxcb.cn/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;
//鄰接矩陣數(shù)據(jù)結(jié)構(gòu) 
typedef  struct{
   int vcount;//頂點數(shù)
   int type ;//0 無向圖，1 有向圖
   char  vexs[N]  ;     // 頂點信息
   int  arcs[N][N]; //關(guān)系矩陣
} GraphMatrix;
 
//鄰接表數(shù)據(jù)結(jié)構(gòu)
struct EdgeNode { //邊表中的結(jié)點
      int  endvex;    //相鄰頂點在頂點表中下標(biāo)
      int  weight;  //邊的權(quán)
      struct EdgeNode  * nextedge;   //鏈字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //記錄頂點信息
   int degree;//用于記錄頂點的入度，在拓?fù)渑判驎r需使用
   EdgeList  edgelist;  //指向邊表的指針
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N個頂點
   int type ;//0 無向圖，1 有向圖
   int vcount;//頂點數(shù)
} GraphList; 
/*第一關(guān) 完成圖初始化-鄰接矩陣
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
輸出鄰接矩陣，不需要考慮輸入的數(shù)字非法情況，不輸入頂點的信息*/
   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()
{
	/*第一行輸入圖的類型、圖的頂點數(shù)和邊數(shù)，第二行輸入各條邊的兩頂點的編號，按頂點編號從小到大的順序輸入。
  輸出鄰接表。不需考慮輸入的數(shù)字非法情況，輸入頂點的信息*/
	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;
}
/*第三關(guān) 完成圖的廣度遍歷（周游），可根據(jù)需要添加自定義函數(shù)
*/
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;
			}
		}
	}
	
}
/*第四關(guān) 完成圖的深度遍歷（周游），可根據(jù)需要添加自定義函數(shù)
*/
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;
	}
	
}
/*第五關(guān) 生成圖的拓?fù)渑判?，可根?jù)需要添加自定義函數(shù)
*/
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;
		}
	}
}
/*第六關(guān) 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;
			}
	}
}

到了這里，關(guān)于頭歌數(shù)據(jù)結(jié)構(gòu)——圖——課上課后練的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進(jìn)行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

頭歌JAVA數(shù)據(jù)結(jié)構(gòu)答案
一、Java數(shù)據(jù)結(jié)構(gòu)-循環(huán)鏈表的設(shè)計與實現(xiàn) 第1關(guān) 單循環(huán)鏈表的實現(xiàn)—鏈表的添加、遍歷第2關(guān) 單循環(huán)鏈表的實現(xiàn)—鏈表的刪除第3關(guān) 雙向循環(huán)鏈表的實現(xiàn)—鏈表的插入第4關(guān)：雙向循環(huán)鏈表的實現(xiàn)—鏈表的刪除二、Java數(shù)據(jù)結(jié)構(gòu)-線性表的設(shè)計與實現(xiàn) 第1關(guān)：順序表的實現(xiàn)之增刪
2024年02月08日
瀏覽(24)
數(shù)據(jù)結(jié)構(gòu)頭歌實驗梳理
PS：該代碼塊表明了鏈接存儲線性表所有常見相關(guān)用法及性質(zhì)。對于初學(xué)者需要分成一小塊一小塊食用特別說明： “當(dāng)前位置”：當(dāng)前位置由curr指針給出，當(dāng)前位置的前一個位置由pre指針給出，當(dāng)前位置的編號由position給出。后面將定義的若干操作與當(dāng)前位置有關(guān)，例如：在
2023年04月12日
瀏覽(28)
【數(shù)據(jù)結(jié)構(gòu)實訓(xùn)】哈希表設(shè)計
[問題描述] 針對某個集體中人名設(shè)計一個哈希表，使得平均查找長度不超過2，并完成相應(yīng)的建表和查表程序。 [基本要求] 假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或
2024年02月11日
瀏覽(26)
頭歌實踐平臺（python數(shù)據(jù)結(jié)構(gòu)）(1-6)
第1關(guān)：棧抽象數(shù)據(jù)類型及其實現(xiàn) 任務(wù)描述相關(guān)知識棧抽象數(shù)據(jù)類型 List 的操作方法編程要求測試說明任務(wù)描述本關(guān)任務(wù)：編寫代碼實現(xiàn)棧的基本操作。相關(guān)知識為了完成本關(guān)任務(wù)，你需要掌握：棧抽象數(shù)據(jù)類型； Python 中 List 的操作方法。棧抽象數(shù)據(jù)類型抽象數(shù)據(jù)類
2024年02月07日
瀏覽(36)
數(shù)據(jù)結(jié)構(gòu)與算法-頭歌【1】順序線性表--課上練
? 本意是整理和復(fù)習(xí)，理解不深或者有錯誤的評論區(qū)提出即可。只有第一關(guān)的代碼里面有結(jié)構(gòu)體的定義，其余我只放了功能函數(shù)。任務(wù)描述本關(guān)要求按照完成順序表數(shù)據(jù)類型定義，并初始化一個順序線性表。編程要求順序線性表數(shù)據(jù)結(jié)構(gòu)定義如下：本關(guān)的編程任務(wù)是補(bǔ)全
2023年04月25日
瀏覽(32)
Java數(shù)據(jù)結(jié)構(gòu)之排序(頭歌平臺，詳細(xì)注釋)
目錄第1關(guān)：選擇排序任務(wù)描述相關(guān)知識代碼：?? ?第2關(guān)：插入排序任務(wù)描述相關(guān)知識插入排序代碼：?? 第3關(guān)：歸并排序任務(wù)描述相關(guān)知識歸并排序原理代碼：?? ?第4關(guān)：快速排序任務(wù)描述相關(guān)知識快速排序代碼：?? ?第5關(guān)：堆排序任務(wù)描述相關(guān)知識堆
2024年01月19日
瀏覽(26)
頭歌（C語言）-數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)組（共7關(guān)）
任務(wù)描述本關(guān)任務(wù):將十個數(shù)進(jìn)行從大到小的順序進(jìn)行排列。相關(guān)知識（略）編程要求根據(jù)提示，在右側(cè)編輯器 Begin-End 處補(bǔ)充代碼。輸入輸入十個整數(shù)。輸出以從大到小的順序輸出這個十個數(shù)。測試說明樣例輸入： 1 2 3 4 5 6 7 8 9 10 樣例輸出： 10 9 8 7 6 5 4 3 2 1 代碼：
2024年02月11日
瀏覽(31)
Java 數(shù)據(jù)結(jié)構(gòu)之棧、隊列(頭歌平臺，詳細(xì)注釋)
目錄第1關(guān)：實現(xiàn)基于數(shù)組的任務(wù)描述相關(guān)知識棧棧的數(shù)組表示 Java 泛型簡介泛型方法泛型類應(yīng)用場景示例代碼：? 第2關(guān)：實現(xiàn)基于鏈表的棧任務(wù)描述相關(guān)知識棧的鏈?zhǔn)酱鎯?入棧出棧代碼：? 第3關(guān)：基于數(shù)組的隊列任務(wù)描述相關(guān)知識隊列隊列的數(shù)組實現(xiàn) 循環(huán)隊列
2024年04月25日
瀏覽(46)
構(gòu)造哈夫曼樹(數(shù)據(jù)結(jié)構(gòu)實訓(xùn))(難度系數(shù)85)
構(gòu)造哈夫曼樹題目描述：根據(jù)給定的葉結(jié)點字符及其對應(yīng)的權(quán)值創(chuàng)建哈夫曼樹。輸入：第一行為葉子結(jié)點的數(shù)目n(1=n=100)。第二行為一個字符串，包含n個字符，每個字符對應(yīng)一個葉子結(jié)點，第三行為每個葉子結(jié)點的概率（即權(quán)值），要求根據(jù)各葉結(jié)點構(gòu)造哈夫曼樹。構(gòu)造哈
2024年02月03日
瀏覽(17)
【頭歌】 Python數(shù)據(jù)結(jié)構(gòu) Python案例實驗一python初探（1)
任務(wù)描述本關(guān)任務(wù)：編寫一個程序，依次輸入用戶的學(xué)號，姓名和手機(jī)號碼再依次輸出相關(guān)信息為了完成本關(guān)任務(wù)，你需要掌握： 1.如何輸入數(shù)據(jù) 2.如何輸出輸入語句變量 = input( 提示性文字 ) 語句功能：系統(tǒng)顯示提示性文字，等待用戶輸入。將用戶輸入的信息存儲在指定
2024年04月11日
瀏覽(73)

<blockquote id="wukey"><dl id="wukey"></dl></blockquote>

<button id="wukey"><pre id="wukey"></pre></button>

<code id="wukey"></code>

<code id="wukey"></code>

<source id="wukey"></source>

<button id="wukey"><tbody id="wukey"></tbody></button>

<table id="wukey"></table>

<code id="wukey"></code><blockquote id="wukey"><tr id="wukey"></tr></blockquote>

<td id="wukey"><kbd id="wukey"></kbd></td>