目录

创建无向网(邻接矩阵存储)

打印邻接矩阵

Prim算法得最小生成树

BFS

DFS

示例

 相关定义(队列将在BFS用到) 

#include 
#include 
#include 
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define MaxVertexNum 100		//最大顶点数 
#define Infinity 65535		//表示 ∞ 
#define OK 1
#define ERROR 0
typedef int VertexType;	//顶点数据类型，数字为例 
typedef int EdgeType;
typedef int Status;
typedef struct{		//无向图的邻接矩阵 
	VertexType data[MaxVertexNum];		//顶点数据数组 
	EdgeType edge[MaxVertexNum][MaxVertexNum];		//邻接矩阵数组 
	int vertexnum, edgenum;		//顶点数，边数 
}MGraph;
typedef int QElemType;
typedef struct{
	QElemType data[MAXSIZE];
	int front, rear;
}SqQueue;
//初始化队列 
Status InitQueue(SqQueue *Q){
	Q->front=Q->rear=0;
	return OK;
}
//判断队列空否 
Status QueueEmpty(SqQueue *Q){
	if(Q->front == Q->rear)
	return TRUE;
	else	return FALSE;
}
//判断队列满否
 Status QueueFull(SqQueue *Q){
	if((Q->rear+1)%MAXSIZE == Q->front)
	return TRUE;
	else	return FALSE;
}
//入队 
Status EnQueue(SqQueue *Q, QElemType e){
	if((Q->rear+1)%MAXSIZE == Q->front){
		printf("队列满，无法入队！");
		return ERROR;
	}
	Q->data[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAXSIZE;
	return OK;
}
//出队
Status DeQueue(SqQueue *Q, QElemType *e){
	if(Q->front == Q->rear){
		printf("队列空，无法出队！");
		return ERROR;
	}
	*e = Q->data[Q->front];
	Q->front=(Q->front+1)%MAXSIZE;
	return OK;
}

创建无向网(邻接矩阵存储)

void CreateMGraph(MGraph *G){		//无向网
	int i, j, k=0;
	VertexType v1, v2;
	EdgeType w;
	printf("输入顶点数及边数（逗号隔开）：");
	scanf("%d,%d", &G->vertexnum, &G->edgenum);			//具体顶点数，边数 
	for(i=0;ivertexnum;i++){
		G->data[i]=i;
	}
	for(i=0;ivertexnum;i++)
		for(j=0;jvertexnum;j++)
			G->edge[i][j]=Infinity;		//初始化邻接矩阵（边全为∞） 
	printf("为顶点之间创造边(Vi,Vj)以及权重(空格隔开):n");
	for(;kedgenum;k++){
		scanf("%d,%d %d", &v1, &v2, &w);
	 	if(v1==-1||v2==-1)
		 {
		 	printf("图中无此顶点!n");
		 	return;
		  } 
		G->edge[v1-1][v2-1]=w;
		G->edge[v2-1][v1-1]=w;		//对称矩阵 
	}
}

---

打印邻接矩阵

void Display(MGraph G)
{
	int i,j;
	printf("n-------------------------------");
	printf("n 邻接矩阵：nn"); 	
	
		printf("t ");
		for(i=0;i 

 
Prim算法得最小生成树 
void MiniSpanTree_Prim(MGraph G){
	int min, i, j, k;
	int adjvex[MaxVertexNum];
	int lowcost[MaxVertexNum];
	lowcost[0]=0;
	adjvex[0]=0;
	for(i=0;i 

 
BFS 
//递归BFS
void BFS(MGraph G){
	int i, j;
	SqQueue Q;			InitQueue(&Q);
	for(i=0;i 

 
DFS 
enum{False,True} visited[MaxVertexNum];		//访问标志 
//递归DFS
void DFSM(MGraph G, int i){		 	//从Vi开始的DFS 
	int j;
	printf("%d", G.data[i]+1);	//访问 
	visited[i]=TRUE;		//标记已访问 
	for(j=0;j 

整体代码：
 
#include 
#include 
#include 
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define MaxVertexNum 100		//最大顶点数 
#define Infinity 65535		//表示 ∞ 
#define OK 1
#define ERROR 0
typedef int VertexType;	//顶点数据类型，数字为例 
typedef int EdgeType;
typedef int Status;
typedef struct{		//无向图的邻接矩阵 
	VertexType data[MaxVertexNum];		//顶点数据数组 
	EdgeType edge[MaxVertexNum][MaxVertexNum];		//邻接矩阵数组 
	int vertexnum, edgenum;		//顶点数，边数 
}MGraph;
typedef int QElemType;
typedef struct{
	QElemType data[MAXSIZE];
	int front, rear;
}SqQueue;
//初始化队列 
Status InitQueue(SqQueue *Q){
	Q->front=Q->rear=0;
	return OK;
}
//判断队列空否 
Status QueueEmpty(SqQueue *Q){
	if(Q->front == Q->rear)
	return TRUE;
	else	return FALSE;
}
//判断队列满否
 Status QueueFull(SqQueue *Q){
	if((Q->rear+1)%MAXSIZE == Q->front)
	return TRUE;
	else	return FALSE;
}
//入队 
Status EnQueue(SqQueue *Q, QElemType e){
	if((Q->rear+1)%MAXSIZE == Q->front){
		printf("队列满，无法入队！");
		return ERROR;
	}
	Q->data[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAXSIZE;
	return OK;
}
//出队
Status DeQueue(SqQueue *Q, QElemType *e){
	if(Q->front == Q->rear){
		printf("队列空，无法出队！");
		return ERROR;
	}
	*e = Q->data[Q->front];
	Q->front=(Q->front+1)%MAXSIZE;
	return OK;
}
void Display(MGraph G)
{
	int i,j;
	printf("n-------------------------------");
	printf("n 邻接矩阵：nn"); 	
	
		printf("t ");
		for(i=0;ivertexnum, &G->edgenum);			//具体顶点数，边数 
	for(i=0;ivertexnum;i++){
		G->data[i]=i;
	}
	for(i=0;ivertexnum;i++)
		for(j=0;jvertexnum;j++)
			G->edge[i][j]=Infinity;		//初始化邻接矩阵（边全为∞） 
	printf("为顶点之间创造边(Vi,Vj)以及权重(空格隔开):n");
	for(;kedgenum;k++){
		scanf("%d,%d %d", &v1, &v2, &w);
	 	if(v1==-1||v2==-1)
		 {
		 	printf("图中无此顶点!n");
		 	return;
		  } 
		G->edge[v1-1][v2-1]=w;
		G->edge[v2-1][v1-1]=w;		//对称矩阵 
	}
}

void MiniSpanTree_Prim(MGraph G){
	int min, i, j, k;
	int adjvex[MaxVertexNum];
	int lowcost[MaxVertexNum];
	lowcost[0]=0;
	adjvex[0]=0;
	for(i=0;i 
示例 
通过例子来说明算法操作的结果。
 
设有下图中给出的无向网
 
 
 
 

程序运行得到：
 
最小生成树
 
 
 BFS和DFS