Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

数据结构与算法 -- 图(邻接矩阵)原理详解

CMusketeer 2019-01-21 18:29:00 阅读数:147 评论数:0 点赞数:0 收藏数:0

PS:图在数据结构中有着非常大的分量,它比树有着更为复杂的形式结构,这里就不再说图的基本概念,直接就说图的存储结构,邻接矩阵和邻接表。图是有方向的,有方向的叫做弧,无方向的叫做边。存储图中各顶点本身数据,使用一维数组就足够了;存储顶点之间的关系时,要记录每个顶点和其它所有顶点之间的关系,所以需要使用二维数组。图在大多行业中的使用也是很多的,比如说游戏中两个人物的寻址,自动寻路,就是图与图直接经过计算然后移动。后序还会介绍Dijkstra(迪杰斯特拉)算法计算最短路径问题。

下面介绍邻接矩阵原理:

下面可以看到顶点之间有一定的联系,如果想要把他们存放在计算机中怎么存入呢,首先我们想到的是把顶点存在一维数组中,那么他们的关系存在在二维数组中,就好像是如下格式,A->B 权值是10,B->E 权值30。(下方1为有关系,0为没有关系,未加入权值)

思路

首先把要知道顶点和边数,然后单独把顶点存在一维数组中,根据边来确定两个顶点之间的联系,比如说第一条边,是A->B。归根结底也是通过数组来存储。当然这是邻接矩阵。

步骤

  1. 定义结构体
  2. 输入顶点和边数
  3. 通过顶点和边数初始化数据(内部全是0或者是无穷)
  4. 打印表
  5. 遍历(深度和广度优先遍历)

1:结构体定义

typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define IUNFINITY 65535
typedef struct {
VertexType vexs[MAXVEX]; /* 顶点表*/
EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵 */
int vnum, edgenum; /*定点的个数和边的个数*/
} MGraphy;

2:数据初始化

代码中有很多注释,有没有用到的,但是一种经验。 

//加入权值
void createGraphyWeight(MGraphy *g) {
printf("输入总顶点(空格)边数\n");
scanf("%d %d", &g->vnum, &g->edgenum);
printf("输入 顶点表示:\n");
//顶点请输入;
for (int i = 0; i < g->vnum; i++) {
printf("请输入第%d个顶点", (i + 1));
// fflush(stdin);//不起作用,资料显示一些linux平台下一些库没有定义这个方法。
// flushall(); //清除多余的回车符。
//如果不加入getchar的话,在for循环中就会先执行一遍scanf,因为上面可能会有一些回车,导致执行一遍scanf。需要清除之前的回车。
getchar();
scanf("%c", &g->vexs[i]);
}
for (int i = 0; i < g->vnum; i++) { // 初始化数组元素 Infonity
for (int j = 0; j < g->vnum; j++) {
// g->arc[i][j] = IUNFINITY;//对于加权值的默认全部设置为最大值,
g->arc[i][j] = 0;//对于未加权值的默认全部设置为0
}
}
printf("输入边有关的两个顶点,\n");
for (int i = 0; i < g->edgenum; i++) {
char a, b;
int c ;
printf("输入第 %d 条边有关的两个顶点加权值(空格隔开),没有权值输入0\n ", (i + 1));
getchar();
// setbuf(stdin,NULL);
scanf("%c %c %d", &a, &b,&c);
int ii = localGV(g, a);
int jj = localGV(g, b);
if(c == 0){
c=1;
}
// printf("c的值是%d",c);
g->arc[ii][jj] = c;
g->arc[jj][ii] = c; // 无向图
}
printfL(g);
}

 3:打印表

void printfL(MGraphy *g) {
//输出图的信息
printf("表为 :\n");
int i = 0;
//先打印行标题;顶点标题
for (i = 0; i < g->vnum + 1; i++) {
if (i > 0) {
printf("%c\t", g->vexs[i - 1]);
} else {
printf("\\\t");
}
}
printf("\n");
for (i = 0; i < g->vnum; i++) {
printf("%c\t", g->vexs[i]);
for (int j = 0; j < g->vnum; j++) {
printf("%d\t", g->arc[i][j]);
}
printf("\n");
}
}

 4:深度优先遍历

这里的深度优先遍历只给出代码,原理后序会给出。

//深度优先搜索
void DFSTraverse(MGraphy *G){//
int v;
//将用做标记的visit数组初始化为false
for( v = 0; v < G->vnum; ++v){
visited[v] = false;
}
//对于每个标记为false的顶点调用深度优先搜索函数
for( v = 0; v < G->vnum; v++){
//如果该顶点的标记位为false,则调用深度优先搜索函数
if(!visited[v]){
DFS(G, v);
}
}
}
int FirstAdjVex(MGraphy *g,int v)
{
//查找与数组下标为v的顶点之间有边的顶点,返回它在数组中的下标
for(int i = 0; i<g->vnum; i++){
if( g->arc[v][i]){
return i;
}
}
return -1;
}
int NextAdjVex(MGraphy *G,int v,int w)
{
//从前一个访问位置w的下一个位置开始,查找之间有边的顶点
for(int i = w+1; i<G->vnum; i++){
//最关键的一个判断,调试了很久,让其等于'1'或者 !=0 ,否则该字符不知道后面还是否有值相连接。
if(G->arc[v][i] != 0){
return i;
}
}
return -1;
}
void DFS(MGraphy *g,int v){
visited[v]= true;
printf("%c",g->vexs[v]);//输入data值
//从该顶点的第一个边开始,一直到最后一个边,对处于边另一端的顶点调用DFS函数
int w;
for( w= FirstAdjVex(g,v); w>=0; w = NextAdjVex(g,v,w)){
//如果该顶点的标记位false,证明未被访问,调用深度优先搜索函数
if(!visited[w]){
DFS(g,w);
}
}
}

 

版权声明
本文为[CMusketeer]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/cmusketeer/p/10300318.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;