图的邻接矩阵.txt

数据结构课堂实验 集中了数据结构,线性表,连表,栈,队列,二叉树,图,排序算法,查找算法的实现

#include <stdio.h>
#include <string.h>
#define INFINITY INT_MAX  999
#define MAX_VERTEX_NUM  20

typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*矩阵类型*/

typedef char VexType[10];  /*顶点类型*/

typedef struct
{   VexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
int kind;  /*图的种类：1-无向图 2-无向网 3-有向图 4-有向网*/
}MGraph; /*图的类型*/

int LocateVex(MGraph &G,VexType v);

void CreatUDG(MGraph &G) /*无向图的创建操作*/
{  VexType v1,v2;
   int i,j,k;
   G.kind=1;
   printf("Input vertex number and edg number:");
   scanf("%d%d",&G.vexnum,&G.arcnum);
   printf("Input vertexs:\n");
   for(i=0;i<G.vexnum;++i)  scanf("%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i)
      for(j=0;j<G.vexnum;++j) G.arcs[i][j]=0;
   for(k=0;k<G.arcnum;++k) 
  { 
     printf("Input edge(v1 v2):");
     scanf("%s%s",v1,v2);
     i=LocateVex(G,v1);
     if(i==-1) { printf(" Error!\n"); return;}
     j=LocateVex(G,v2);
     if(j==-1) {  printf(" Error!\n"); return;}
     G.arcs[i][j]=G.arcs[j][i]=1;
  }   
}

int LocateVex(MGraph &G,VexType v) /*在图G中查找顶点v，若存在返回位置，否则返回-1*/
{  int i;
   for(i=0;i<G.vexnum;i++)
     if(strcmp(G.vexs[i],v)==0) return i;
   return -1;
}

  void GraphOutput(MGraph &G)/*图的邻接矩阵的输出操作*/
{  int i,j;
   printf("\t");
   for(i=0;i<G.vexnum;++i)
      printf("%8s",G.vexs[i]);
   printf("\n");
   for(i=0;i<G.vexnum;++i)
   {  printf("%s\t",G.vexs[i]);
      for(j=0;j<G.vexnum;++j) 
         printf("%8d",G.arcs[i][j]);
      printf("\n");
   }
}

int FirstAdjVex(MGraph &G, int v)/*求v的第一个邻接顶点*/
{ /*代码略*/}
int NextAdjVex(MGraph &G, int v,int w) /*求v的相对于w的下一个邻接顶点*/
{ /*代码略*/}

void DFSTraverse(MGraph &G,int v)/*图的深度优先遍历算法*/
{VisitFunc=Visit;
for (v=0;v<G.vexnum;++v) visited[v]=FALSE;
for (v=0;v<G.vexnum;++v)
  if(!visited[v]) DFS(G,v);
}

void DFS(Graph G,int v)
{visited[v]=TRUE;VisitFunc(v);
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
if(!visited[w]) DFS(G,w);}

void BFSTraverse(MGraph &G)/*图的广度优先遍历算法*/
{for (v=0;v<G.vexnum;++v) visited[v]=FALSE;
InitQueue(Q);
for(v=0;v<G.vexnum;++v)
	if (!visited[v]){
	  visited[v]=TRUE;Visit(v);
	  EnQueue(Q,v);
          while(!QueueEmpty(Q)){
		DeQueue(Q,u);
		for(w=FirstAdjVex(G,u);w>0;w=NextAdjVex(G,u,w))
			if (!Visited[w])
			   {Visited[w]=TRUE;Visit(w);
			    EnQueue(Q,w);}
                               }
          }
}

/*其他操作略*/

main()
{  MGraph G;
   CreatUDG(G);
   GraphOutput(G);
   DFSTraverse(G);
   BFSTraverse(G);
}