關於帶權無向圖的一些操作

題目：根據圖來建立它的鄰接矩陣，通過鄰接矩陣轉化為鄰接表，對鄰接表進行深度優先訪問和廣度優先訪問，最後用鄰接矩陣生成它的最小生成樹；

1．輸入一個帶權無向圖（如下面圖1和圖2）的頂點數、邊數、各條邊資訊（兩個頂點和權值），建立該圖的鄰接矩陣結構，輸出該鄰接矩陣。

圖1 圖2

2．將上述無向圖鄰接矩陣轉換為鄰接表結構，輸出該鄰接表；

3．根據該鄰接表對無向圖進行深度優先遍歷序列和廣度優先遍歷序列，並輸出遍歷結果；

4．用prim演算法實現構造該帶權無向圖的最小生成樹，並將該最小生成樹的各條邊資訊輸出。

一些注意

程式用文件讀入，使用前應寫好讀入文件；

初始工作（所有的結構體定義和函數聲明）

結構體定義

# include <stdio.h>
# include <stdlib.h>
# define MAX 20
#define  MAXV  20	//最大頂點個數
#define VertexType int //存放頂點資訊 
#define QElemType int
typedef  int  VetexType;
int visited[MAX];
typedef struct ArcNode		//弧結點類型定義 
{
	int  adjvex;		//該弧的弧頭
	int weight;
	struct  ArcNode  *nextarc;		//指向另一個弧結點的指針
}ArcNode;
typedef  struct  VNode		//鄰接表頭結點類型定義
{ 
	VetexType  data;		//頂點資訊
	int adv;
	ArcNode  *firstarc;		//指向第一個依附於該頂點的弧的指針
} AdjList[MAX];
typedef  struct		//圖定義 
{ 
	AdjList  vertices;		//鄰接表定義
	int  vexnum, arcnum;		//頂點數和弧數 
}ALGraph;

typedef  struct 
{
	int  adj;
	int weight;			//頂點關係(0或1)
//	InfoType  info;	//該弧或邊的相關資訊
} AdjMatrix[MAXV][MAXV]; 
typedef  struct		//圖的定義 
{
	AdjMatrix  arcs;				//鄰接矩陣 
	int  vexnum, arcnum;			//頂點數,弧數
	VertexType vexs[MAXV];		//存放頂點資訊 
} MGraph;
//隊列的定義
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
	QueuePtr front;
	QueuePtr rear;
}LinkQueue; 
//輔助數組定義
 struct mini{
	int adjvex;
	int lowcost;
}mini,closedge[MAXV];

函數聲明

void creatMG(MGraph *G);
void outMG(MGraph *G);
void Transition(MGraph *G1,ALGraph *G2);
void outALGraph(ALGraph *G);
void DFSTraverse(ALGraph *G);
void BFSTraverse(ALGraph G);
void DFS(ALGraph *G,int v);
void visit(int v,ALGraph *G);
void InitQueue(LinkQueue *Q);
void EnQueue(LinkQueue *Q,QElemType e);
void DeQueue(LinkQueue *Q,int *e);
int QueueEmpty(LinkQueue Q);
void MiniSpanTree(MGraph G,int u);

具體的函數實現

//創造鄰接矩陣 
void creatMG(MGraph *G){	
	int i, j, k,n,w,e;
	FILE *fp1;
	fp1=fopen("text2.txt","r");//第一組數據打開text1, 第二組數據打開text2； 
	if(!fp1)
	{
		printf("can't open file\n");
		return ;
	}
//	printf("輸入頂點數和邊數\n"); 
	fscanf(fp1,"%d%d", &n, &e);	//輸入頂點數n，邊數e
	G->arcnum =e;G->vexnum=n;
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
		{
			G->arcs[i][j].adj=0;
			G->arcs[i][j].weight=1000;//假設最大權值不會超過一千 
		}
	for(k=1; k<=e; k++)	//勾畫各條邊
		{
		//	printf("輸入邊(vi, vj)的頂點號vi, vj以及權值w\n ");
			fscanf(fp1,"%d%d%d", &i, &j,&w);		//輸入一條邊的兩個頂點編號i,j 
			G->arcs[i][j].adj=1;
			G->arcs[j][i].adj=1;
			G->arcs[i][j].weight=w;
			G->arcs[j][i].weight=w;
		}	//若是網，可讓G[i][j]=w，w也需提前輸入
} //creat_Mg
void outMG(MGraph *G){//輸出鄰接矩陣 
	int i, j;
	for(i=1; i<=G->vexnum; i++)		//矩陣原樣輸出
	{
		printf("\n");
		for(j=1; j<=G->vexnum; j++)
			printf("%5d", G->arcs[i][j].adj);
	}
	//輸出所存在的邊
	for(i=1; i<=G->vexnum; i++)
	{
		for(j=1; j<=G->vexnum; j++)
		{
			if(G->arcs[i][j].adj!=0)
			//	printf("\n存在邊( %d, %d )",i,j);
				printf("\n存在邊( %d, %d )它的權值為%d",i,j,G->arcs[i][j].weight);
		}
	}
	printf("\n");
} //out_Mg
//鄰接矩陣轉化成鄰接表 
void Transition(MGraph *G1,ALGraph *G2){
	int i,j;
	ArcNode *p; 
	G2->arcnum=G1->arcnum;//點和邊的數值相同 
	G2->vexnum=G1->vexnum;
	for(i=1;i<=G2->vexnum;i++){
		G2->vertices[i].data=i;
		G2->vertices[i].adv=i;
		G2->vertices[i].firstarc =NULL;//每個結點是首地址指向NULL 
		for(j=1;j<=G2->vexnum;j++){
			if(G1->arcs[i][j].adj){
				p=(ArcNode *)malloc(sizeof(ArcNode));
				p->adjvex=j;
				p->weight=G1->arcs[i][j].weight;//保存權重 
				p->nextarc=G2->vertices[i].firstarc;//頭插入到後面 
				G2->vertices[i].firstarc =p;
			}
		}
	}
	
}
void outALGraph(ALGraph *G){ //輸出鄰接表 
	int i;
	ArcNode *p;
	for(i=1;i<=G->vexnum;i++){
		printf("%d",G->vertices[i].adv);
		p=G->vertices[i].firstarc;
		while(p){//依次輸出與該點相互鄰接的點 
			printf("->%d",p->adjvex);
			p=p->nextarc;
		}
		printf("\n");
	}
}
//DFS 
void DFSTraverse(ALGraph *G){
	int i;
	for(i=0;i<=G->vexnum;i++){
		visited[i]=0;
	}
	for(i=1;i<=G->vexnum;i++){//防止不是連通圖 
		if(!visited[i]){
			DFS(G,i);
		}
	}
}
void DFS(ALGraph *G,int v){//深度優先遍歷 
	ArcNode *p;
	visited[v]=1;
	visit(v,G);
	for(p=G->vertices[v].firstarc;p;p=p->nextarc){//依次經過每個結點 
		if(!visited[p->adjvex]) DFS(G,p->adjvex);//未訪問測訪問 
	} 
}
void BFSTraverse(ALGraph G) { //廣度優先遍歷 
	LinkQueue Q;
	ArcNode *p;
	int v,u;
	for(v=0;v<=G.vexnum;v++){
		visited[v]=0;//初始化 
	}
	InitQueue(&Q);
	for(v=1;v<=G.vexnum;v++){
		if(!visited[v]){
			visited[v]=1;
			visit(v,&G);
			EnQueue(&Q,v);
			while(QueueEmpty(Q)){
				DeQueue(&Q,&u);
				for(p=G.vertices[u].firstarc;p;p=p->nextarc){
					if(!visited[p->adjvex]){
						visited[p->adjvex]=1;//新訪問的點標記 
						visit(p->adjvex,&G);//訪問 
						EnQueue(&Q,p->adjvex);//新點入隊 
					}
				} 
			}
		}
	}
}
void visit(int v,ALGraph *G){//訪問點資訊的函數 
	printf("%d\n",G->vertices[v].data);
}
void InitQueue(LinkQueue *Q){//隊列初始化 
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
	Q->front->next=NULL;//首尾都指向NULL 
}
void EnQueue(LinkQueue *Q,int e){//入隊 
	QueuePtr p;
	p=(QueuePtr)malloc(sizeof(QNode));
	p->data=e;
	p->next=Q->rear->next;
	Q->rear->next=p;//插入隊中 
	Q->rear=p;
}
void DeQueue(LinkQueue *Q,int *e){//出隊 
	QueuePtr p;
	if(Q->front==Q->rear) return ;//隊列為空
	p=Q->front->next;
	*e=p->data;
	Q->front->next=p->next; 
	if(Q->rear==p) Q->rear=Q->front;//此時只有一個元素 
}
int QueueEmpty(LinkQueue Q){
	if(Q.front==Q.rear) return 0;//為空
	return 1; 
}
//構造最小生成樹 
void MiniSpanTree(MGraph G,int u){//u為頂點,表示從第幾個頂點開始構造最小生成樹 
	int j,i,k,a,min=1000;
	k=u;
	for(j=0;j<=G.vexnum;j++){
		closedge[j].lowcost=1000;
	}
	for(j=1;j<G.vexnum;j++){
		if(j!=k){
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j].weight;
		}
	}
	closedge[k].lowcost=0;
	for(i=2;i<=G.vexnum;i++){
		for(a=1;a<=G.vexnum;a++){
		if(closedge[a].lowcost<min&&closedge[a].lowcost!=0){
			min=closedge[a].lowcost;
			k=a;
			}
		}
		min=1000;
		printf("點%d到點%d,權值為%d\n",closedge[k].adjvex,k,closedge[k].lowcost);
		closedge[k].lowcost=0;
		for(j=1;j<=G.vexnum;j++){
			if(G.arcs[k][j].weight<closedge[j].lowcost){//printf("-");
				closedge[j].adjvex=k;
				closedge[j].lowcost=G.arcs[k][j].weight;
			}
		}
	}	
}

main函數

//主函數
int main(){ 
	MGraph G1;
	ALGraph G2;
	creatMG(&G1);
	printf("輸出鄰接矩陣\n");
	outMG(&G1);
	Transition(&G1,&G2);
	printf("輸出鄰接表\n");
	outALGraph(&G2);
	printf("輸出深度優先排序\n");
	DFSTraverse(&G2);
	printf("輸出廣度優先排序\n");
	BFSTraverse(G2);
	printf("輸出最小生成樹\n");
	MiniSpanTree(G1,1);
	return 0;
}