/*
*无向网的基本操作(邻接矩阵存储)
*/
#include<stdio.h>
#define MAX_VERTEX_NUM 20
typedef char VertexType;
typedef struct
{
int vertexNum;//顶点个数
VertexType vertex[MAX_VERTEX_NUM];//顶点信息
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
}GraphMatrix,*PGraphMatrix;
//用数组vertex按序存放遍历的各个顶点,广度遍历时看成队列,深度遍历时看成栈
VertexType vertex[MAX_VERTEX_NUM];
//建立无向网
void createGraph(PGraphMatrix pGraph)
{
int i,j,arcNum,from,to,weight;
printf("please enter the numbers of vertex(顶点):\n");
scanf("%d",&pGraph->vertexNum);
for(i=0;i<pGraph->vertexNum;i++)
pGraph->vertex[i]='a'+i;
for(i=0;i<pGraph->vertexNum;i++)
for(j=0;j<pGraph->vertexNum;j++)
pGraph->arcs[i][j]=0;
printf("please enter the numbers of arcs(弧):\n");
scanf("%d",&arcNum);
for(i=0;i<arcNum;i++){
printf("please enter the information of arcs(弧),(起始点 终点 权值):\n");
scanf("%d%d%d",&from,&to,&weight);
pGraph->arcs[from][to]=weight;
pGraph->arcs[to][from]=weight;
}
}
//求指定顶点
VertexType getVertexByIndex(PGraphMatrix pGraph,int index)
{
return pGraph->vertexNum==0?'0':pGraph->vertex[index];
}
//求第一个顶点
VertexType getFirstVertex(PGraphMatrix pGraph)
{
return pGraph->vertexNum==0?'0':pGraph->vertex[0];
}
//求图中顶点index的下一个顶点
VertexType getVertexAfterIndex(PGraphMatrix pGraph,int index)
{
return (index>=0 && index+1 < pGraph->vertexNum) ? pGraph->vertex[index+1] : '0';
}
//求第一个与顶点index相邻的顶点
VertexType getVertexNextIndex(PGraphMatrix pGraph,int index)
{
int j;
if(index>=0&&index<pGraph->vertexNum){
for(j=0;j<pGraph->vertexNum;j++)
if(j!=index&&pGraph->arcs[index][j]!=0)
return pGraph->vertex[j];
}
return '0';
}
//根据顶点信息寻返回顶点在图中的位置
int findVertex(PGraphMatrix pGraph,VertexType vertex)
{
int i;
for(i=0;i<pGraph->vertexNum;i++)
if(pGraph->vertex[i]==vertex)
return i;
return -1;
}
//返回任一顶点的边的个数
int getArcsNum(PGraphMatrix pGraph,int index)
{
int j,k=0;
if(index>=0&&index<pGraph->vertexNum){
for(j=0;j<pGraph->vertexNum;j++)
if(pGraph->arcs[index][j]!=0)
k++;
return k;
}
return -1;
}
//广度优先遍历
void breadthTraverse(PGraphMatrix pGraph)
{
int i,j,k;
int flag[MAX_VERTEX_NUM];//记录顶点的下标
int front,rear;
front=rear=0;
for(i=0;i<MAX_VERTEX_NUM;i++)
flag[i]=-1;
//从第一个顶点开始
front=rear=0;
vertex[rear++]=pGraph->vertex[0];
flag[0]=0;
while(front<rear){
i=flag[front];
for(j=0;j<pGraph->vertexNum;j++){//遍历i为下标的那一行
for(k=0;k<rear;k++)//判断此顶点是否在队列中
if(flag[k]==j)
break;
if(k==rear && i!=j && pGraph->arcs[i][j]!=0){
vertex[rear]=pGraph->vertex[j];
flag[rear++]=j;
}
}
front++;
}
}
//深度优先遍历
void depthTraverse(PGraphMatrix pGraph)
{
int i,j,top=0,k,m;
int flag[MAX_VERTEX_NUM];//记录顶点的下标
for(i=0;i<MAX_VERTEX_NUM;i++)
flag[i]=-1;
//从第一个顶点开始
vertex[top++]=pGraph->vertex[0];
flag[0]=0;
while(top>0 && top<pGraph->vertexNum){
if(j==pGraph->vertexNum)//退栈,从上一个顶点开始
i=flag[--m];
else
m=i=flag[top-1];
for(j=0;j<pGraph->vertexNum;j++){
for(k=0;k<top;k++)
if(flag[k]==j)
break;
if(k==top && i!=j && pGraph->arcs[i][j]!=0){
vertex[top]=pGraph->vertex[j];
flag[top++]=j;
break;
}
}
}
}
//测试
void main()
{
int i;
GraphMatrix graph;
createGraph(&graph);
printf("指定顶点:%c\n",getVertexByIndex(&graph,1));
printf("第一个顶点:%c\n",getFirstVertex(&graph));
printf("index的下一个顶点:%c\n",getVertexAfterIndex(&graph,0));
printf("第一个与顶点index相邻的顶点:%c\n",getVertexNextIndex(&graph,1));
printf("根据顶点信息寻返回顶点在图中的位置:%d\n",findVertex(&graph,'b'));
printf("返回任一顶点的边的个数:%d\n",getArcsNum(&graph,0));
printf("-----------广度优先遍历-----------------\n\n");
breadthTraverse(&graph);
for(i=0;i<graph.vertexNum;i++)
printf("%-3c",vertex[i]);
printf("\n\n-------深度优先遍历------------------\n\n");
depthTraverse(&graph);
for(i=0;i<graph.vertexNum;i++)
printf("%-3c",vertex[i]);
printf("\n\n");
}
分享到:
相关推荐
图的邻接矩阵存储表示和实现图的邻接矩阵存储表示和实现图的邻接矩阵存储表示和实现,图的邻接矩阵存储表示和实现,图的邻接矩阵存储表示和实现,图的邻接矩阵存储表示和实现,图的邻接矩阵存储表示和实现,图的邻接...
无向图的邻接矩阵存储及输出无向图的邻接矩阵存储及输出
有关无向网的邻接矩阵存储,用C语言编写,详细代码。
包括线性表的各种基本操作C语言实现(不用库函数)
c语言代码实现如下: #include #include #define MAX_VER_NUM 50 typedef char VertexType; typedef enum { DG,UDG }GraphType; typedef struct { VertexType vexs[MAX_VER_NUM]; //顶点向量 int arcs[MAX_VER_...
用C语言实现,利用邻接矩阵存储图的程序,建立图用邻接矩阵存储,输出邻接矩阵,并用深度优先算法遍历二叉树
基于邻接矩阵存储的图的最小生成树的Prime算法,对学习C++和数据结构很有帮助
一学期数据结构的代码作业,基本上涵盖了课本上面所有算法的C语言代码实现,压缩包无密码 2019/11/03 21:43 1,478 BF_KMP.cpp 2019/11/03 21:22 2,664 KMP.cpp 2019/10/24 18:49 3,956 LinkStack.cpp 2019/11/21 ...
该代码是通过C语言编程实现,主要是为了快速求解邻接矩阵对应的可达矩阵,邻接矩阵和可达矩阵是系统工程中表征系统元素之间关系的重要工具之一
用C语言实现图的基本操作 typedef struct ArcCell{ VRType adj; //VRType是顶点关系类型。对无权图,用1或0 //表示相邻与否;对带权图,则为权值类型 InfoType *info; //该弧相关信息的指针 }ArcCell,AdjMatrix...
博文测试代码,博文链接:https://blog.csdn.net/qq_44075108/article/details/116085013
基于邻接矩阵存储的图的最短路径问题,可以很好的学习C++和数据结构
数据结构 图的遍历(邻接矩阵) c语言 源代码
数据结构(C语言)(严蔚敏)各章节基本操作实现
C语言实现邻接矩阵存储图的深度优先遍历。
顺序表的基本操作 C语言实现 数据结构实验
本人使用C语言编写使用初等行变换的方法,求出矩阵的逆矩阵。
这是图的邻接矩阵,可以求各顶点,深度周游,广度周游,包括邻接矩阵的连能图和非连能图等