本章介绍邻接矩阵有向图。在"图的理论基础"中已经对图进行了理论介绍，这里就不再对图的概念进行重复说明了。和以往一样，本文会先给出C语言的实现；后续再分别给出C++和Java版本的实现。实现的语言虽不同，但是原理如出一辙，选择其中之一进行了解即可。若文章有错误或不足的地方，请不吝指出！

邻接矩阵有向图的介绍

邻接矩阵有向图是指通过邻接矩阵表示的有向图。

上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了",,,,,,,,"共9条边。

上图右边的矩阵是G2在内存中的邻接矩阵示意图。A[i][j]=1表示第i个顶点到第j个顶点是一条边，A[i][j]=0则表示不是一条边；而A[i][j]表示的是第i行第j列的值；例如，A[1,2]=1，表示第1个顶点(即顶点B)到第2个顶点(C)是一条边。

邻接矩阵有向图的代码说明

1. 基本定义

// 邻接矩阵

typedef struct _graph

{

char vexs[MAX]; // 顶点集合

int vexnum; // 顶点数

int edgnum; // 边数

int matrix[MAX][MAX]; // 邻接矩阵

}Graph, *PGraph;

Graph是邻接矩阵对应的结构体。

vexs用于保存顶点，vexnum是顶点数，edgnum是边数；matrix则是用于保存矩阵信息的二维数组。例如，matrix[i][j]=1，则表示"顶点i(即vexs[i])"和"顶点j(即vexs[j])"是邻接点；matrix[i][j]=0，则表示它们不是邻接点。

2. 创建矩阵

这里介绍提供了两个创建矩阵的方法。一个是用已知数据，另一个则需要用户手动输入数据。

2.1 创建图(用已提供的矩阵)

/*

* 创建图(用已提供的矩阵)

*/

Graph* create_example_graph()

{

char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

char edges[][2] = {

{'A', 'B'},

{'B', 'C'},

{'B', 'E'},

{'B', 'F'},

{'C', 'E'},

{'D', 'C'},

{'E', 'B'},

{'E', 'D'},

{'F', 'G'}};

int vlen = LENGTH(vexs);

int elen = LENGTH(edges);

int i, p1, p2;

Graph* pG;

// 输入"顶点数"和"边数"

if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )

return NULL;

memset(pG, 0, sizeof(Graph));

// 初始化"顶点数"和"边数"

pG->vexnum = vlen;

pG->edgnum = elen;

// 初始化"顶点"

for (i = 0; i < pG->vexnum; i++)

{

pG->vexs[i] = vexs[i];

}

// 初始化"边"

for (i = 0; i < pG->edgnum; i++)

{

// 读取边的起始顶点和结束顶点

p1 = get_position(*pG, edges[i][0]);

p2 = get_position(*pG, edges[i][1]);

pG->matrix[p1][p2] = 1;

}

return pG;

}

createexamplegraph()是的作用是创建一个邻接矩阵有向图。实际上，该方法创建的有向图，就是上面的图G2。

2.2 创建图(自己输入)

/*

* 创建图(自己输入)

*/

Graph* create_graph()

{

char c1, c2;

int v, e;

int i, p1, p2;

Graph* pG;

// 输入"顶点数"和"边数"

printf("input vertex number: ");

scanf("%d", &v);

printf("input edge number: ");

scanf("%d", &e);

if ( v < 1 || e < 1 || (e > (v * (v-1))))

{

printf("input error: invalid parameters!\n");

return NULL;

}

if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )

return NULL;

memset(pG, 0, sizeof(Graph));

// 初始化"顶点数"和"边数"

pG->vexnum = v;

pG->edgnum = e;

// 初始化"顶点"

for (i = 0; i < pG->vexnum; i++)

{

printf("vertex(%d): ", i);

pG->vexs[i] = read_char();

}

// 初始化"边"

for (i = 0; i < pG->edgnum; i++)

{

// 读取边的起始顶点和结束顶点

printf("edge(%d):", i);

c1 = read_char();

c2 = read_char();

p1 = get_position(*pG, c1);

p2 = get_position(*pG, c2);

if (p1==-1 || p2==-1)

{

printf("input error: invalid edge!\n");

free(pG);

return NULL;

}

pG->matrix[p1][p2] = 1;

}

return pG;

}

create_graph()是读取用户的输入，将输入的数据转换成对应的有向图。

邻接矩阵有向图的完整源码

点击查看：源代码

邻接表有向图&lpar;一&rpar;之 C语言详解

本章介绍邻接表有向图.在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了.和以往一样,本文会先给出C语言的实现:后续再分别给出C++和Java版本的实现 ...

邻接矩阵无向图&lpar;一&rpar;之 C语言详解

本章介绍邻接矩阵无向图.在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了.和以往一样,本文会先给出C语言的实现:后续再分别给出C++和Java版本的实 ...

原来Github上的README&period;md文件这么有意思——Markdown语言详解(sublime text2 版本)

一直想学习 Markdown 语言,想起以前读的一篇 赵凯强 的 博客 ,该篇博主 使用的是Mac系统, ...

Java Web----EL&lpar;表达式语言&rpar;详解

Java Web中的EL(表达式语言)详解 表达式语言(Expression Language)简称EL,它是JSP2.0中引入的一个新内容.通过EL可以简化在JSP开发中对对象的引用,从而规范页面 ...

Floyd算法&lpar;一&rpar;之 C语言详解

本章介绍弗洛伊德算法.和以往一样,本文会先对弗洛伊德算法的理论论知识进行介绍,然后给出C语言的实现.后续再分别给出C++和Java版本的实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3 ...

Dijkstra算法&lpar;一&rpar;之 C语言详解

本章介绍迪杰斯特拉算法.和以往一样,本文会先对迪杰斯特拉算法的理论论知识进行介绍,然后给出C语言的实现.后续再分别给出C++和Java版本的实现. 目录 1. 迪杰斯特拉算法介绍 2. 迪杰斯特拉算法 ...

Prim算法&lpar;一&rpar;之 C语言详解

本章介绍普里姆算法.和以往一样,本文会先对普里姆算法的理论论知识进行介绍,然后给出C语言的实现.后续再分别给出C++和Java版本的实现. 目录 1. 普里姆算法介绍 2. 普里姆算法图解 3. 普里 ...

Kruskal算法&lpar;一&rpar;之 C语言详解

本章介绍克鲁斯卡尔算法.和以往一样,本文会先对克鲁斯卡尔算法的理论论知识进行介绍,然后给出C语言的实现.后续再分别给出C++和Java版本的实现. 目录 1. 最小生成树 2. 克鲁斯卡尔算法介绍 3 ...

拓扑排序&lpar;一&rpar;之 C语言详解

本章介绍图的拓扑排序.和以往一样,本文会先对拓扑排序的理论知识进行介绍,然后给出C语言的实现.后续再分别给出C++和Java版本的实现. 目录 1. 拓扑排序介绍 2. 拓扑排序的算法图解 3. 拓扑 ...

随机推荐

&lbrack;译&rsqb;git fetch

git fetch从远程仓储导入commit到你的本地仓储. 这些fetch到的commit是做为一个远程分支存储在你本地的. 这样你可以在集成这些commit到你的项目前先看看都有些什么修改. 用法 ...

使用 nginx &plus; thin 的配置启动 rails server

http://www.iwangzheng.com 在大师的指导下配置了新的服务器的nginx,通过top命令查看了服务器是8个cpu的,所以起了8个端口,把它们都映射到一个总的端口3600上,需要在 ...

phpDoc 注释案例说明

浅析PC机串口通讯流控制

转自浅析PC机串口通讯流控制 我们在串行通讯处理中,常常看到RTS/CTS和XON/XOFF这两个选项,这就是两个流控制的选项,目前流控制主要应用于调制解调器的数据通讯中,但对普通RS232编程,了解 ...

vi同类品

nvi 更纯正,接近原始的vi command argument-F    don't copy whole file, may faster-S    secure help (quick refe ...

HY&period;Mail：C&num;简单、易用的邮件工具库

一.开发HY.Mail的初衷 Nuget或者github上有很多成熟且优秀的邮件库可以使用, 但是目前找到的使用都不够简洁或者不适合我的使用场景 我的场景是开发应用场景(例如系统通知.运维通知),而非 ...

下载的js文件本地编辑器打开中文乱码如何解决

今天遇到的小问题,已解决,直接上图 下载直接打开是这样的 用记事本打开 另存为utf-8格式 正常了!

tcprstat分析服务的响应速度

Tcprstat 是免费开源的TCP分析工具,可检测网络通信状态,并且计算请求和响应之间的延迟. 它的输出格式类似 linux 的 vmstat 和 iostat 的输出格式.这个工具能够检测到某个端 ...

&lbrack;Android&rsqb;RecyclerView添加HeaderView出现宽度问题

通过getItemViewType方式判断HeaderView方式添加HeaderView的,结果发现有几个界面HeaderView宽度不能满屏. 于是对比了几种布局,发现LinearLayout为根 ...

执行AJAX返回HTML片段中的JavaScript脚本

如果AJAX加载的数据是一个HTML片段,而且这个HTML片段还包含脚本

/*

*顺序储存有向图邻接矩阵

*定义一个边的权值的二维数组

*定义一个点的一维数组

*创建一个邻接矩阵

*输出这个邻接矩阵

*/

#include

#include

#include

#define MAXVERTEX 100//顶点数

#define ERROR 0

#define OK 1

typedef char * VertexType;//顶点数据类型

typedef int ArcType;//权值数据类型

typedef int Statu;//返回值的数据类型

typedef enum{

DG,//有向图

UDG,//无向图

DN,//有向网

UDN//无向网

}GraphKind;//图的枚举类型

typedef struct

{

VertexType vertex[MAXVERTEX];//点的一维数组

ArcType arcs[MAXVERTEX][MAXVERTEX];//权值的二维数组

int vertexcount;//点数

int arccount;//边数

GraphKind kind;//图的类型

}Mtrix_Graph;//图的结构体类型

Statu create_matrixgraph(Mtrix_Graph*G);//创建邻接矩阵

void test();//测试函数

int locate_graph(Mtrix_Graph*G,VertexType vex);//返回名称在数组中的下标(定位函数)

void main()

{

test();//测试函数

}

Statu create_matrixgraph(Mtrix_Graph*G)//创建邻接矩阵

{

G->kind=UDG;//表明是无向图 (UDG代表有向图)

int i;

int j;

int x,y;

printf("输入图的顶点数:");

scanf("%d",&G->vertexcount);

printf("输入图的边数:");

scanf("%d",&G->arccount);

printf("请依次输入顶点的信息:\n");

for( i=0;ivertexcount;i++)

{

G->vertex[i]=(VertexType)malloc(sizeof(char)*10);//分配内存空间

printf("顶点%d：",i+1);

scanf("%s",G->vertex[i]);

}

for(i=0;ivertexcount;i++)//邻接矩阵初始化

for(j=0;jvertexcount;j++)

G->arcs[i][j]=0;

//输入边的顶点位置 创建邻接矩阵

for( i=0;iarccount;i++)

{

VertexType vex1=(VertexType)malloc(sizeof(char)*10);

//创建临时字符串变量

VertexType vex2=(VertexType)malloc(sizeof(char)*10);

printf("顶点：");

scanf("%s",vex1);

printf("临接点：");

scanf("%s",vex2);

x=locate_graph(G,vex1);

y=locate_graph(G,vex2);

if(x==-1||y==-1)

return ERROR;

else{

G->arcs[x][y]=1;

//G->arcs[y][x]=G->arcs[x][y];//无向图对称原因

free(vex1);//临时变量释放空间

free(vex2);

}

}

return OK;

}

int locate_graph(Mtrix_Graph*G,VertexType vex)//返回名称在数组中的下标

{

int index=0;

while(indexvertexcount)

{

if(strcmp(vex,G->vertex[index])==0)

{

break;

}

else

index++;

}

return index==G->vertexcount?-1:index;

}

void test()//测试函数

{

Mtrix_Graph *G;

int i,j;

G=(Mtrix_Graph*)malloc(sizeof(Mtrix_Graph));

Statu result =create_matrixgraph(G);

if(result==ERROR)

{

printf("创建邻接矩阵失败:\n");

return ;

}

printf("打印一个邻接矩阵:\n");

printf("\t");//格式控制最上面的一行字母和矩阵数字对齐

for(i=0;ivertexcount;i++)

{

printf("\t%s",G->vertex[i]);//输出第一行的字母

}

printf("\n");//第一行字母打印完之后换行

for(i=0;ivertexcount;i++)

{

printf("\t%s",G->vertex[i]);//输出每一行的第一个字母 \t 缩进八个字节

for(j=0;jvertexcount;j++)

printf("\t%d",G->arcs[i][j]);//缩进八个字节

printf("\n");//输入每一行之后换行

}

}

标签：VertexType,有向图,Mtrix,int,邻接矩阵,++,printf,顺序存储

来源： https://blog.csdn.net/qq_44213634/article/details/91038980