图的基本操作及应用
使用邻接矩阵构建如上有向带权图,由有向图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");
}
转载:https://blog.csdn.net/weixin_44303677/article/details/102466469
查看评论