xuhe无向图.cpp

this a map to you updata myself

//1.用邻接矩阵表示一个图。
//2.将邻接矩阵转换为邻接表。
//3.用邻接表实现图的深度优先遍历算法。

#include<stdio.h>
#include<stdlib.h>

#define MAX_size 1000
#define MAX_VERTEX_NUM 10
#define Error -1
#define OK 1
#define True 1
#define False 0
#define INFINITY 32768

/*邻接表* 类型定义 */
typedef enum {DG,DN,UDG,UDN} GraphKind;   //枚举类型，可以自己定义值没，
                          //若没有自定值，则C编译时自动赋值为0,1,2,...



typedef struct ArcNode 
{
	int adjvex;
	struct ArcNode *nextarc;
	//OtherInfo info;  //与该弧相关的信息    还不知道有什么用？？？
}ArcNode;

typedef struct VertexNode
{
	char data;
	ArcNode *firstarc;  //指向该顶点第一条弧的指针
	int visited;        //自己加上一个标志域
}VertexNode;

typedef struct
{
	VertexNode vertex[MAX_VERTEX_NUM];   //
	int vexnum,arcnum;    //图的顶点数和弧数
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
//  GraphKind kind;    //图的种类]
}Adjxuhe;	 
//求最小生成树时的辅助数组
struct better
{
	char adjvex;
	int lowcost;
	//char next_adjvex;   可用可不用
}closedge[MAX_VERTEX_NUM];
//已经定义一个数据结构，并声明了一个数组，下面可以直接应用


void CreateAdj(Adjxuhe *g);
int LocateVertex(Adjxuhe *g,char v);
void TraverseGraph(Adjxuhe *g);
void DepthFirstSearch(Adjxuhe *g,int v0);
int NextAdjVertex(Adjxuhe *g,int v0,int w);
int FirstAdjVertex(Adjxuhe *g,int v0);
void MiniSpanTree_Prim(Adjxuhe *g,char s);
int Minium(better closedge[],int k);
void print(char u0,char v0,int lowcost);
int CreateDN(Adjxuhe *g);

void main()
{
	int c;
	Adjxuhe g;
do{ 
        printf("*邻接表* 输入图（创建邻接链表）请按1\n"); 
        printf("*邻接表* 深度优先遍历请按 2\n");
		printf("*邻接表* 按普里姆算法生成最小生成树请按3\n");
		printf("*邻接表* 退出请按0\n"); 
        scanf("%d",&c); 
		getchar();
        switch(c) 
        { 
            case 1:     CreateAdj(&g);
				        break; 
            case 2:    	TraverseGraph(&g);
						break;
            case 3:    	MiniSpanTree_Prim(&g,g.vertex[0].data);
						//从第一个顶点开始
						break;
			case 4:		CreateDN(&g);
						break; 
			case 0:     break;
            default:    break; 
        } 
     
    }while(c!=0);      
    printf("*\n"); 
}



void CreateAdj(Adjxuhe *g)
//输入n个顶点的信息和 e条弧的信息，建立一个有向图的邻接表
{
	int n,e,i,j,k;
	char vt,vh;
	ArcNode *p;
	printf("请输入 n个顶点和 e条弧(例：4,4):\n");
	scanf("%d,%d",&n,&e);
	getchar();  //去除回车键
	g->vexnum=n;
	g->arcnum=e;
	printf("请输入所有顶点数据，如：ABCD\n");
	for(i=0;i<n;i++)
	{
		scanf("%c",&g->vertex[i].data);
		g->vertex[i].firstarc=NULL;
	}
    getchar(); //消去回车
	
	for(k=0;k<e;k++)       
	{
		printf("输入两个字符，若 A-->B,  则输入 A,B\n");
                      //回车符号是挺麻烦的事
		scanf("%c,%c",&vt,&vh);    //求顶点位置函数
		getchar(); 
		i=LocateVertex(g,vt);      // 书上 p.159
		j=LocateVertex(g,vh);
		printf("%c-%c之间(整数) size:\n ",vt,vh);
		scanf("%d",&g->arcs[i][j]);
		g->arcs[j][i]=g->arcs[i][j];
		getchar();
		p=(ArcNode *)malloc(sizeof(ArcNode));
		p->adjvex=j;
		p->nextarc=g->vertex[i].firstarc; g->vertex[i].firstarc=p;  
	}
	for(i=0;i<g->vexnum;i++)
		for(j=0;j<g->vexnum;j++)
		{
			if(g->arcs[i][j]<0)    //C++默认的数组未赋值时为负数？？？？
			{
				g->arcs[i][j]=MAX_size;
			}
		}
} 


int LocateVertex(Adjxuhe *g,char v)//求顶点位置函数 （下标）
{
	int j=Error,k;
	for(k=0;k<g->vexnum;k++)
	{
		if(g->vertex[k].data == v)
		{ j=k; break; }
	//	{ j=k; 	return(j); }  也行
	}
	return(j);
}


int CreateDN(Adjxuhe *g)
{
	int i,j,k,weight;
	char v1,v2;
	printf("请输入图的顶点数n和弧数e(ex:4,4):");
	scanf("%d,%d",&g->arcnum,&g->vexnum);//输入图的顶点数和弧数
	for(i=0;i<g->vexnum;i++)
		for(j=0;j<g->vexnum;j++)
			g->arcs[i][j].adjvex=INFINITY;
	printf("请输入图的顶点数(ex:abcd):");
	for(i=0;i<g->vexnum;i++)
		scanf("%c",&g->vertex[i]);//输入图的顶点
	printf("请输入图的两个顶点及其权值:");
	for(k=0;k<g->arcnum;k++)
	{
		scanf("%c,%c,%d",&v1,&v2,&weight);//输入一条弧的两个顶点及权值
		i=LocateVertex(g,v1);
		j=LocateVertex(g,v2);
		g->arcs[i][j].data=weight;//建立弧
	}
	return OK;
}



void TraverseGraph(Adjxuhe *g)
{
	int vi;
	for(vi=0;vi<g->vexnum;vi++)
		g->vertex[vi].visited=False;  //标记数组初始化为0
	for(vi=0;vi<g->vexnum;vi++)
		if(!g->vertex[vi].visited) 
			DepthFirstSearch(g,vi);
}


void DepthFirstSearch(Adjxuhe *g,int v0)//深度优先
{
	int w;
	//visit(v0);  把visited[] 数组设置在数据结构中。
	g->vertex[v0].visited=True;   //visited[v0] ?  OK
	printf("*%c*\n",g->vertex[v0].data);
	w=FirstAdjVertex(g,v0);
	while(w!=-1)
	{
		if(!g->vertex[w].visited)
			DepthFirstSearch(g,w);

		w=NextAdjVertex(g,v0,w);
	}
}

int FirstAdjVertex(Adjxuhe *g,int v0)
{
	if(g->vertex[v0].firstarc!=NULL)
	{
		return g->vertex[v0].firstarc->adjvex;
	}
	else
		return -1;
}

int NextAdjVertex(Adjxuhe *g,int v0,int w)
{
	ArcNode *p;
	p=(ArcNode *)malloc(sizeof(ArcNode));
	p=g->vertex[v0].firstarc;

	while(p!=NULL && p->adjvex!=w )
	{
		p=p->nextarc;
	}
	
	if(p!=NULL && p->nextarc!=NULL)
	{
		return p->nextarc->adjvex;
	}
	else 
		return -1;	
}

int Minium(better closedge[],int n)
{
	int i,min,k0=0;

	for(i=0;i<n;i++)
	{
		if(closedge[i].lowcost!=0)
		{
			min=closedge[i].lowcost;
			k0=i;
			break;
		}
	}	
	for(i=0;i<n;i++)
	{
		if(closedge[i].lowcost!=0)
		{
			if(closedge[i].lowcost<min)
			{
				min=closedge[i].lowcost;
				k0=i;
			}
		}
	}
	return k0;
}


void print(char u0,char v0,int lowcost)//打印
{
	printf("\n*%c-->%c*  size:%d*\n",u0,v0,lowcost);
}

		
void MiniSpanTree_Prim(Adjxuhe *gn,char s)//最小生成数 普里姆算法
//从定点s出发
{
	int k,i,e;
	int k0;
	char u,u0,v0;
	k=LocateVertex(gn,s);
	closedge[k].lowcost=0;  //初始化 U={s};
	u=s;
	for(i=0;i<gn->vexnum;i++)
	{
		if(i!=k)    //对V－U中的定点i，初始化closedge[i];
		{
			closedge[i].adjvex=u;
			closedge[i].lowcost=gn->arcs[k][i];
		}
	}
	for(e=1;e<=gn->vexnum-1;e++)   //招n-1条边
	{
		k0=Minium(closedge,gn->vexnum);      //colsedge[k0]中存有当前最小边(u0,v0)的信息；
		u0=closedge[k0].adjvex;
		v0=gn->vertex[k0].data;     //书上这么写是有道理的；或者	v0=closedge[k0].next_adjvex;
		print(u0,v0,closedge[k0].lowcost);
		closedge[k0].lowcost=0;  //将顶点v0 纳入U集合
		for(i=0;i<gn->vexnum;i++)    //更新closedge[i];
		{
			if(gn->arcs[k0][i]<closedge[i].lowcost)
			{
				closedge[i].lowcost=gn->arcs[k0][i];
				closedge[i].adjvex=v0;
			
			}
		}
	}
}