实验4图的基本操作及应用

图的基本操作及应用

使用邻接矩阵构建如上有向带权图，由有向图G的邻接矩阵产生邻接表，并输出有邻接矩阵和邻接表；分别在邻接矩阵和邻接表存储结构下求图中每个顶点的入度和出度；分别在邻接矩阵和邻接表存储结构下对图进行深度和广度优先遍历。

#include <stdio.h>
#include <malloc.h>
#include<string.h>
typedef int InfoType;
#define	MAXV 100				//最大顶点个数
#define INF  32767 
//以下定义邻接矩阵类型
typedef struct 
{  	int no;						//顶点编号
	InfoType info;				//顶点其他信息
} VertexType;					//顶点类型
typedef struct  				//图的定义
{  	int edges[MAXV][MAXV]; 		//邻接矩阵
   	int n,e;   					//顶点数，弧数
	VertexType vexs[MAXV];		//存放顶点信息
} MGraph;						//图的邻接矩阵类型
//以下定义邻接表类型
typedef struct ANode           	//弧的结点结构类型
{	int adjvex;              	//该弧的终点位置
   	struct ANode *nextarc; 		//指向下一条弧的指针
   	InfoType info;           	//该弧的相关信息,这里用于存放权值
} ArcNode;
typedef int Vertex;
typedef struct Vnode      		//邻接表头结点的类型
{	Vertex data;            	//顶点信息
	int count;             		//存放顶点入度,只在拓扑排序中用
    ArcNode *firstarc;     		//指向第一条弧
} VNode;
typedef VNode AdjList[MAXV];	//AdjList是邻接表类型
typedef struct 
{	AdjList adjlist;         	//邻接表
    int n,e;                 	//图中顶点数n和边数e
} ALGraph;                   	//图的邻接表类型
void MatToList(MGraph g,ALGraph *&G)
//将邻接矩阵g转换成邻接表G
{  int i,j,n=g.n; ArcNode *p; 	//n为顶点数
   G=(ALGraph *)malloc(sizeof(ALGraph));
   for (i=0;i<n;i++)     //给所有头节点的指针域置初值
      G->adjlist[i].firstarc=NULL;
   for (i=0;i<n;i++)	 //检查邻接矩阵中每个元素
      for (j=n-1;j>=0;j--)
         if (g.edges[i][j]>0 && g.edges[i][j]<INF) 			
         {   p=(ArcNode *)malloc(sizeof(ArcNode));   //创建节点*p
	          p->adjvex=j;
		      p->info=g.edges[i][j];
	          p->nextarc=G->adjlist[i].firstarc;  //将*p链到链表头
	         G->adjlist[i].firstarc=p;
	      }
   G->n=n;G->e=g.e;
} 
void DispMat(MGraph g)
//输出邻接矩阵g
{
	int i,j;
	for (i=0;i<g.n;i++)
	{
		for (j=0;j<g.n;j++)
			if(g.edges[i][j]>=0 && g.edges[i][j]<INF)
		    	printf("%5d",g.edges[i][j]);
			else printf("%s","  INF");
		printf("\n");
	}
}
void DispAdj(ALGraph *G)
//输出邻接表G
{
	int i;
	ArcNode *p;
	for (i=0;i<G->n;i++)
	{
		p=G->adjlist[i].firstarc;
		printf("%3d: ",i);
		while (p!=NULL)
		{
			printf("%3d(%2d)",p->adjvex,p->info);
			p=p->nextarc;
		}
		printf("\n");
	}
}

int visited[MAXV];
void DFS(ALGraph *G,int v)  
{  ArcNode *p; int w;
   visited[v]=1; 			           //置已访问标记
   printf("%d  ",v); 	    	    //输出被访问顶点的编号
   p=G->adjlist[v].firstarc;      	//p指向顶点v的第一条边的边头节点
   while (p!=NULL) 
   {  w=p->adjvex;
	if (visited[w]==0) 
	   DFS(G,w);                   //若w顶点未访问，递归访问它
	p=p->nextarc;                   //p指向顶点v的下一条边的边头节点
   }
}
void BFS(ALGraph *G,int v)  
{  ArcNode *p; int w,i;
   int queue[MAXV],front=0,rear=0;	//定义循环队列
   int visited[MAXV];     //定义存放节点的访问标志的数组
   for (i=0;i<G->n;i++) visited[i]=0;  //访问标志数组初始化
   printf("%2d",v);           	//输出被访问顶点的编号
   visited[v]=1;                   	//置已访问标记
   rear=(rear+1)%MAXV;
   queue[rear]=v;             	//v进队
	while (front!=rear)        	//若队列不空时循环
	{  front=(front+1)%MAXV;
	   w=queue[front];          	//出队并赋给w
	   p=G->adjlist[w].firstarc; 	//找w的第一个的邻接点
	   while (p!=NULL) 
	   {	if (visited[p->adjvex]==0) 
		{  printf("%2d",p->adjvex); //访问之
		   visited[p->adjvex]=1; 
	         rear=(rear+1)%MAXV;	//该顶点进队
		   queue[rear]=p->adjvex;
            }
            p=p->nextarc;     	//找下一个邻接顶点
	   }
	}
	printf("\n");
   }

int InDegreeM(MGraph g,int v)
{
    int n = 0;
    int i;
    for(i = 0; i < g.n; i++)
    {
        if(g.edges[i][v] != INF && g.edges[i][v] != 0)
            n++;
    }
    return n;
}

int outDegreeM(MGraph g,int v)
{
    int n = 0;
    int i;
    for(i = 0; i < g.n; i++)
    {
        if(g.edges[v][i] != INF && g.edges[v][i] != 0)
            n++;
    }
    return n;
}

void main()
{
	int i,j;
	MGraph g,g1;
	ALGraph *G;
	 int A[MAXV][6]={
	 {0,5,INF,7,INF,INF},
		{INF,0,4,INF,INF,INF},		
		{8,INF,0,INF,INF,9},
		{INF,INF,5,0,INF,6},
		{INF,INF,INF,5,0,INF},
		{3,INF,INF,INF,1,0}};
	g.n=6;g.e=10;
	for (i=0;i<g.n;i++)
		for (j=0;j<g.n;j++)
			g.edges[i][j]=A[i][j];
	printf("\n");
	printf(" 有向图G的邻接矩阵:\n");
	DispMat(g);
	G=(ALGraph *)malloc(sizeof(ALGraph));
	printf(" 图G的邻接矩阵转换成邻接表:\n");
	MatToList(g,G);
	DispAdj(G);
		for (i=0;i<MAXV;i++)
		visited[i]=0;
	printf(" 顶点0的入度为:%d\n",InDegreeM(g,0));
    printf(" 顶点1的入度为:%d\n",InDegreeM(g,1));
    printf(" 顶点2的入度为:%d\n",InDegreeM(g,2));
    printf(" 顶点3的入度为:%d\n",InDegreeM(g,3));
    printf(" 顶点4的入度为:%d\n",InDegreeM(g,4));
    printf(" 顶点5的入度为:%d\n",InDegreeM(g,5));
    printf("\n");
    printf(" 顶点0的出度为:%d\n",outDegreeM(g,0));
    printf(" 顶点1的出度为:%d\n",outDegreeM(g,1));
    printf(" 顶点2的出度为:%d\n",outDegreeM(g,2));
    printf(" 顶点3的出度为:%d\n",outDegreeM(g,3));
    printf(" 顶点4的出度为:%d\n",outDegreeM(g,4));
    printf(" 顶点5的出度为:%d\n",outDegreeM(g,5));
	printf(" 深度优先序列:");
	DFS(G,0);
	printf("\n");
	printf(" 广度优先序列:");
	BFS(G,0);
	printf("\n");
}