11.cpp

数据结构(c++)图的全部操作 结构分为无向,有向,无权,有权

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ERROR 0
#define OK 1
#define N 50
#define E 50
#define MAX 100
#define INFINITY 65535//最大值无穷
typedef char VexType;//顶点类型
typedef int AdjType;//权值类型
typedef struct{
    AdjType number;//顶点个数
    AdjType arcnum;//弧个数
	VexType vexs[N];
	AdjType arcs[N][N];//二维数组以行存
}MGraph;
AdjType CreateUDN(MGraph &G)//无向图
{
	int i,j,k,w,h,m,z,q;VexType v1,v2;
    printf("无向图\n");
	printf("请输入顶点个数:\n");
	scanf("%d",&G.number);
	z=N-1;
	if(G.number>z) exit(ERROR);
	printf("请输入弧个数:\n");
	scanf("%d",&G.arcnum);
	printf("输入各顶点的值:\n");
	for(i=1;i<=G.number;++i)//0不用
		scanf(" %c",&G.vexs[i]);
   
	for(i=1;i<=G.number;++i)//行
		for(j=1;j<=G.number;++j)//列
		  G.arcs[i][j]=INFINITY;//初始化邻接矩阵

	for(q=1;q<=G.arcnum;q++)//以边数作为循环的条件
	{
	 printf("输入一条弧的两个顶点(顶点1,顶点2):\n");
	 getchar();//吃掉回车
	 scanf("%c,%c",&v1,&v2);
	 for(k=1;k<=G.number;++k)//在二维数组里找位置
		 if(G.vexs[k]==v1) {h=k;break;}
		 if(k>G.number) {printf("输入顶点值错误\n");exit(ERROR);}
  	for(w=1;w<=G.number;++w)
      if(G.vexs[w]==v2) {m=w;break;}
        if(w>G.number) {printf("输入顶点值错误\n");exit(ERROR);}
       printf("输入此条弧的权值\n");
	   scanf("%d",&G.arcs[h][m]);
       G.arcs[m][h]=G.arcs[h][m];
	}
	return OK;
}
AdjType Print(MGraph G)
{int i,j;
 for(i=1;i<=G.number;i++)//上三角
	 for(j=i;j<=G.number;j++)
		{if(G.arcs[i][j]!=INFINITY)
		      printf("顶点 %c,顶点 %c,权值 %d\n",G.vexs[i],G.vexs[j],G.arcs[i][j]);
		}
	 return OK;
}

void main()
{MGraph M;
printf("创建\n");
  CreateUDN(M);
  printf("打印\n");
  Print(M);
}*/
//第二个
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define ERROR 0
#define OK 1
#define INFINITY 65535//最大值无穷
typedef char VexType;//顶点类型
typedef int AdjType;//权值类型
typedef struct ArcNode{
	  AdjType adjvex;//顶点在VNode中的位置
      AdjType weight;//权值
      struct ArcNode *next;
}Arc,*ArcNodete;
typedef struct VNode{
        VexType data;//顶点
        ArcNodete address;
}VNo,*VNodete;
typedef struct{
    AdjType vexnum,arcnum;//顶点数，边数
}ALGraph;
VNodete Creat(VNodete &M,ALGraph &H)
{int i,j,k,m,h;ArcNodete L;VexType ch;ArcNodete P;
 printf("无向图\n");
 printf("输入顶点个数:\n");
 scanf("%d",&H.vexnum);
 printf("输入边个数:\n"); 
 scanf("%d",&H.arcnum);
 if(H.vexnum<=0) exit(ERROR);
 else {if(!(M=(VNodete)malloc((H.vexnum+1)*sizeof(VNo)))) {printf("错误\n");exit(ERROR);}}//0不用
 for(i=1;i<=H.vexnum;i++)
	{printf("输入顶点的值:\n");
		scanf(" %c",&M[i].data);
        M[i].address=NULL;
	}

for(i=1;i<=H.vexnum;i++)
{ 
 printf("和%c邻接的顶点个数:\n",M[i].data);
  scanf("%d",&j);
  for(k=1;k<=j;k++)
	{if(!(L=(ArcNodete)malloc(sizeof(Arc)))) {printf("错误\n");exit(ERROR);}
		printf("输入和%c邻接其中一个顶点:\n",M[i].data);
		scanf(" %c",&ch);
		for(m=1;m<=H.vexnum;m++)
			if(M[m].data==ch) {h=m;m=1;break;}
		if(m>H.vexnum) {m=1;printf("顶点输入错误\n");continue;}
		L->adjvex=h;
		printf("输入%c与%c的权值:\n",M[i].data,ch);
		scanf("%d",&(L->weight));
		P=M[i].address;M[i].address=L;L->next=P;
		  
	}
}
return M;
}
AdjType Printling(VNodete M,ALGraph H)
{int i;ArcNodete P;
 for(i=1;i<=H.vexnum;i++)
 {P=M[i].address;
 if(P==NULL) {printf("没有与%c邻接的顶点\n",M[i].data);continue;}
 else printf("与%c邻接的顶点:\n",M[i].data);
	while(P!=NULL)
		{printf("顶点 %c ",M[P->adjvex].data);
		 printf("在顶点数组中第%d位",P->adjvex);
		 printf("此条边权值 %d",P->weight);
		 printf("\n");
		 P=P->next;
		}
	}
		return OK;
}

void main()
{VNodete M;ALGraph H;
printf("创建\n");
 M=Creat(M,H);
 printf("遍历\n");
 Printling(M,H);
}

第四个
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ERROR 0
#define OK 1
#define N 50
#define E 50
#define MAX 100
#define INFINITY 65535//最大值无穷
typedef char VexType;//顶点类型
typedef int AdjType;//权值类型
typedef struct{
    AdjType number;//顶点个数
    AdjType arcnum;//弧个数
	VexType vexs[N];
	AdjType arcs[N][N];//二维数组以行存
}MGraph;
int dgvisited[MAX];
AdjType CreateUDN(MGraph &G)//无向图
{
	int i,j,k,w,h,m,z,q;VexType v1,v2;
    printf("无向图\n");
	printf("请输入顶点个数:\n");
	scanf("%d",&G.number);
	z=N-1;
	if(G.number>z) exit(ERROR);
	printf("请输入弧个数:\n");
	scanf("%d",&G.arcnum);
	printf("输入各顶点的值:\n");
	for(i=1;i<=G.number;++i)//0不用
		scanf(" %c",&G.vexs[i]);
   
	for(i=1;i<=G.number;++i)//行
		for(j=1;j<=G.number;++j)//列
		  G.arcs[i][j]=INFINITY;//初始化邻接矩阵

	for(q=1;q<=G.arcnum;q++)//以边数作为循环的条件
	{
	 printf("输入一条弧的两个顶点(顶点1,顶点2):\n");
	 getchar();//吃掉回车
	 scanf("%c,%c",&v1,&v2);
	 for(k=1;k<=G.number;++k)//在二维数组里找位置
		 if(G.vexs[k]==v1) {h=k;break;}
		 if(k>G.number) {printf("输入顶点值错误\n");exit(ERROR);}
  	for(w=1;w<=G.number;++w)
      if(G.vexs[w]==v2) {m=w;break;}
        if(w>G.number) {printf("输入顶点值错误\n");exit(ERROR);}
       printf("输入此条弧的权值\n");
	   scanf("%d",&G.arcs[h][m]);
       G.arcs[m][h]=G.arcs[h][m];
	}
	return OK;
}
AdjType Print(MGraph G)
{int i,j,k,z;
 for(i=1;i<=G.number;i++)//上三角
	 for(j=i;j<=G.number;j++)
		{if(G.arcs[i][j]!=INFINITY)
		      printf("顶点 %c,顶点 %c,权值 %d\n",G.vexs[i],G.vexs[j],G.arcs[i][j]);
		}
	 printf("矩阵\n");
	 
	 for(z=1;z<=G.number;z++)
		{for(k=1;k<=G.number;k++)
			printf("%6d",G.arcs[z][k]);
			printf("\n");
		}


	 return OK;
}



void DFSM(MGraph M){//无向图,非递归DFS算法,从第i个结点起深度遍历图中顶点
   int s2[MAX],k=0;//S为栈,k为栈顶
   int j,v,z,l,start;VexType ch;int visited[MAX];//本来想用(M.number+1),0不用的,但数组是常量,不行
   if(M.number>=MAX) exit(ERROR);
   for(z=1;z<=M.number;z++)
   visited[z]=0;
   
	printf("任意选择一个起点:\n");
	scanf(" %c",&ch);

   for(l=1;l<=M.number;l++)
		if(M.vexs[l]==ch) {start=l;printf("%c",ch);visited[l]=1;s2[k++]=l;break;}//列
	if(l>M.number) {printf("输入起点不正确\n");exit(ERROR);}

   v=start;
   
   while(k>0){//不考虑不连通的
      
      j=1;
while(j<=M.number)//找未访问过的相邻顶点,列
	  {
       if ((M.arcs[v][j]!=INFINITY)&&(!visited[j])) 
	   {printf("%c",M.vexs[j]);
         s2[k++]=j;
        visited[j]=1;v=j;break;
	  //找到后,接着找所得相邻顶点的未访问过的相邻顶点
	   }
     j++;
     }
     if (j>M.number) v=s2[--k-1];//一定用这个做,判断条件为k=0
 //找不到相邻顶点,则将栈顶顶点出栈,取栈顶顶点的未访问过的相邻顶点
   }   
}
AdjType DFSMDG(MGraph M,int i)//递归,i行
{int j=1;
  while (j<=M.number)
  {
	if((M.arcs[i][j]!=INFINITY)&&(!dgvisited[j]))
		{printf("%c",M.vexs[j]);dgvisited[j]=1;DFSMDG(M,j);}
	j++;
  }
	if(j>M.number) return OK;
	return OK;
}
void CENGCIBIANLI(MGraph M)
{VexType ch;int l,start,z,v,j,visited[MAX],s2[MAX],front=0,rear=0;//队列
for(z=1;z<=M.number;z++)
  visited[z]=0;
 printf("任意选择一个起点:\n");
	scanf(" %c",&ch);

   for(l=1;l<=M.number;l++)
		if(M.vexs[l]==ch) {start=l;s2[rear++]=l;visited[s2[front]]=1;break;}//列
	if(l>M.number) {printf("输入起点不正确\n");exit(ERROR);}
	v=start;	
	while(front!=rear)
	{
		j=1;
		while(j<=M.number)
		{ 
			if((M.arcs[v][j]!=INFINITY)&&(!visited[j]))
			{s2[rear++]=j;visited[s2[rear-1]]=1;}
			
			++j;
		}
      printf("%c",M.vexs[s2[front++]]);
		v=s2[front];
	}
}

			




void main()
{MGraph M;VexType comp;int i=0,j;
 printf("创建\n");
  CreateUDN(M);
  printf("打印邻接距阵\n");
  Print(M);
  printf("遍历\n");
  DFSM(M);
  printf("\n");
  printf("递归遍历\n");
  printf("任意选择一个起点:\n");
  scanf(" %c",&comp);
  for(i=1;i<=M.number;i++)
	  if(comp==M.vexs[i]) 
	  {for(j=1;j<=M.number;j++)
		  dgvisited[j]=0;
       dgvisited[i]=1;printf("%c",comp);
	   break;
	  }
	if(i>M.number) {printf("输入起点不正确\n");exit(ERROR);}
  DFSMDG(M,i);
  printf("\n");
  printf("广度优先遍历\n");
 CENGCIBIANLI(M);
 printf("\n");

}