图:是一种非线性结构
形式化的描述: G={V,R}
V:图中各个顶点元素(如果这个图代表的是地图,这个顶点就是各个点的地址)
R:关系集合,图中顶点与顶点之间的关系(如果是地图,这个关系集合可能就代表的是各个地点之间的距离)
在顶点与顶点之间的关系上面加上一个权值(w),这种权值代表的意义可能会不一样
如果没有权值,顶点与顶点之间可能只有是否能到达的情况,但是不知道到达它需要的"距离"
图是一个二元组:描述V(顶点的代号,我们需要一个"数组") 描述R(可能是两点之间的距离,我们也需要一个"数组"去描述)
图分为两种
1 有向图:关系是有方向的(你可以想象是一个单行道)
有去不一定有来
在画图的时候,关系是有箭头指向的
2 无向图:关系是没有方向的(你可以想象是小区的小道,你过去是走这一条,回来的时候也是走的这一条)
有去一定有来
在画图的时候,关系是没有箭头指向的
网:带权值的图我们就叫网
顶点的度:有出度也有入度
如果图是有向图,这个顶点有出度不一定有入度,有入度不一定有出度
如果图是无向图,这个顶点有出度一定有入度
一般图里面算度的数量的时候分别都要算入度和出度的数量
出度:拓扑 --> 找一个没有入度的顶点出发
通过出度到达另外一个顶点,然后将这个点的入度全部删除
然后从下一个点继续开始,如果最后能将图里面的所有的顶点都遍历一遍
那个这个图就叫拓扑有序,否则就叫拓扑无序
入度:逆拓扑 -> 跟上面的是反的
图:里面主要要搞定一个叫路径的问题
1 最短路径 --- 最短的那一条
2 关键路径 --- 在覆盖所有的工作流程里面找最短的那些路径
这些路径里面最长的那条路径就叫关键路径
计算机里面描述图
图是一个二元组,因此需要用至少两个东西分别描述顶点元素集合,关系集合
假设你的顶点是ABCDEFG -> 我们开一个char[]就可以描述了
假设你的顶点是"长沙" "武汉"... -> char *[]描述
假设你的关系集合为距离 -> int [][]
我们有几种方式去做图的保存
"数组表示法" -> 邻接矩阵
"链表表示法" -> 邻接表(逆邻接表) 十字链表 邻接多重表
邻接矩阵:通过顶点元素数组和关系集合数组来描述
通过画图可以看出,邻接矩阵适合稠密图
邻接表:通过顶点元素数组和关系链表来描述(有向图无向图都能做)
十字链表:主要搞定有向图(可以快速反应这个点的入度与出度)
邻接多重表:主要搞定无向图(有去必有来,因此可以少建立很多的关系)
通过画图可以看出,链表表示法适合稀松图
图的遍历
1 深度优先DFS:树里面的先序遍历的扩展
图里面的任何一个顶点都可能是出发点
从出发点开始,将其遍历,然后以深度优先的方式继续遍历它的邻接点(和它有直接关系的点
在画图的时候有一根线和它连起来了,这个点就是它的邻接点)
邻接点遍历完毕继续以深度优先遍历它的邻接点的邻接点
这个点有去也有可能有来,遍历的时候就可能会遇到刚刚遍历过点
因此我们需要一个辅助向量来表明这个顶点是不是已经被遍历过了
char V[10];
visit[10] -> visit[0]表示V[0]是不是已经被访问 visit[1]表示V[1]是不是已经被访问.....
0没有被遍历,1表示遍历过了
if(visit[i] == 0)
{
访问V[i]
visit[i] = 1;//标记已经被访问过
DFS(V[i]的邻接点) //以相同的规则去访问这个邻接点
}
访问w;
for(v = 从w第一个邻接点开始;v邻接点存在;v = w下一个邻接点)
{
if(visit[v] == 0)
{
//访问v
visit[v] == 1;
DFS(v);
}
}
2 广度优先BFS:树里面的层次遍历的扩展
利用队列来进行每一层每一层的遍历
入队访问出队访问都可以
从起点开始,将它入队
出队,转向它的下一辈(它所有的邻接点(前面有可能已经被访问过,访问过的要排除))
为了确保孤岛也能被访问,我们需要将每一个点都要以BFS的形式走一遍
BFS(v)
{
//将顶点入队
queue_push(v);
while(队列不为空)
{
v = queue_front();
queue_pop();
for(i = v的所有邻接点)
{
if(visit[i] == 0) //这些邻接点没有被访问你才需要去访问
{
visit[i] = 1;
queue_push(i);
}
}
}
}
for(i < 顶点个数个数)//防止有孤岛 所以每一个点都要试一次BFS
{
if(visit[i] == 0)
{
BFS(i);
}
}
//输入格式
ABCDEFG ->所有的顶点元素
AB3 ->边以及权值
BC5
...
##-1退出
//你的图里面最多可以容纳的顶点个数
#define VMaxNum 1000
//这个值代表一个无法到达的权值
#define VERYBIG 65535
//弄的是邻接矩阵
//你现在需要一个图的类型
typedef struct
{
char _V[VMaxNum];//顶点元素的数组
int _R[VMaxNum][VMaxNum];//顶点与顶点之间的关系集合
int _vexnum;//真正顶点的个数
int _arcnum;//边(关系线)的个数 无向的叫边 有向的叫弧
}Graph;
#include "Graph.h"
//建立邻接矩阵
Graph * GraphInit(void)
{
return (Graph *)calloc(1,sizeof(Graph));
}
//获取顶点元素的下标 -1表示失败
int GetVIndex(Graph * g,char v)
{
for(int i = 0;i < g ->_vexnum;i++)
{
if(v == g ->_V[i])
return i;
}
return -1;
}
//从键盘获取顶点元素以及边
void GetGraph(Graph * g)
{
if(!g)
return;
printf("请输入所有的顶点元素:");
scanf("%s",g ->_V);
getchar();
g ->_vexnum = strlen(g ->_V);//实际顶点个数为这么多
//关系集合里面什么玩意儿都没有 不能是0
for(int i = 0;i < g ->_vexnum;i++)
{
for(int j = 0;j < g ->_vexnum;j++)
{
g ->_R[i][j] = VERYBIG;//用VERYBIG将关系集合初始化一遍
}
}
char start,stop;
int w;
while(1)
{
printf("请输入边和权值(AB2):");
if(scanf("%c%c%d",&start,&stop,&w) != 3)
{
printf("\t\t输入有误,请重新输入\n");
char buf[1024];
fgets(buf,1024,stdin);
continue;
}
getchar();//输入成功在后面会多一个\n 你需要拿走
if('#' == start || '#' == stop || -1 == w)
{
break;
}
//printf("%c %c %d\n",start,stop,w);
int start_index = GetVIndex(g,start);
int stop_index = GetVIndex(g,stop);
if(-1 == start_index || -1 == stop_index)
{
printf("\n边有问题,请重新输入\n");
}
//为了避免重复
if(g ->_R[start_index][stop_index] == VERYBIG)
g ->_arcnum++;
g ->_R[start_index][stop_index] = w;//这个东西代表的是start到stop有w远
printf("%d %d\n",start_index,stop_index);
g ->_R[stop_index][start_index] = w;//无向图就可以多这一步
}
}
//打印邻接矩阵
void PrintGraph(Graph * g)
{
if(!g)
return;
for(int i = 0;i < g ->_vexnum;i++)
{
printf("\t%c",g ->_V[i]);
}
printf("\n");
for(int i = 0;i < g ->_vexnum;i++)
{
printf("%c",g ->_V[i]);
for(int j = 0;j < g ->_vexnum;j++)
{
if(g ->_R[i][j] == VERYBIG)
printf("\t\\");
else
printf("\t%d",g ->_R[i][j]);
}
printf("\n");
}
}
//获取v的第一个邻接点 v这一行里面第一个不是VERYBIG的
//失败返回-1
int GetFirstIndex(Graph * g,int v)
{
for(int i = 0;i < g ->_vexnum;i++)
{
if(g ->_R[v][i] != VERYBIG)
return i;
}
return -1;
}
//获取v的w的下一个邻接点 v这一行里面w列后面第一个不是VERYBIG的
//失败返回-1
int GetNextIndex(Graph * g,int v,int w)
{
for(int i = w + 1;i < g ->_vexnum;i++)
{
if(g ->_R[v][i] != VERYBIG)
return i;
}
return -1;
}
//遍历的向量
int visit[VMaxNum];//visit[i]表示顶点V[i]是否被访问 0表示没有 1表示访问过了
//这里用的v是下标
static void DFS(Graph * g,int v)
{
if(!g || visit[v])//已经访问过就不用访问了
return;
printf("%c ",g ->_V[v]);
visit[v] = 1;
for(int w = GetFirstIndex(g,v);w > -1;w = GetNextIndex(g,v,w))
{
if(visit[w] == 0)
{
DFS(g,w);
}
}
}
//DFS 深度优先 从v开始进行DFS v是顶点
void DFS_search(Graph * g,char v)
{
//初始化visit
memset(visit,0,g ->_vexnum *sizeof(visit[0]));
printf("DFS:");
//先弄一个遍v开始的DFS
DFS(g,GetVIndex(g,v));
printf("\n");
//所有再遍历来一遍
for(int i = 0;i < g ->_vexnum;i++)
{
if(visit[i] == 0)
{
DFS(g,i);
printf("\n");
}
}
}
//请你实现BFS
static void BFS(Graph * g,int v)
{
if(!g || visit[v])//图不存在或者v被访问过都无需访问
return;
//队列要存在
ArrayQueue * qu = ArrayQueue_init(100);
//将顶点入队
ArrayQueue_push(qu,v);
visit[v] = 1;
while(!ArrayQueue_empty(qu))
{
v = ArrayQueue_front(qu);
printf("%c ",g ->_V[v]);
ArrayQueue_pop(qu);
//for(int i = GetFirstIndex(g,v);i > -1;i = GetNextIndex(g,v,i))
for(int i = 0;i < g ->_vexnum;i++)
{
if(g ->_R[v][i] != VERYBIG)
{
if(visit[i] == 0) //这些邻接点没有被访问你才需要去访问
{
visit[i] = 1;
ArrayQueue_push(qu,i);
}
}
}
}
ArrayQueue_destory(&qu,NULL);
}
//BFS 广度优先 从v开始进行BFS v是顶点
void BFS_search(Graph * g,char v)
{
//初始化visit
memset(visit,0,g ->_vexnum *sizeof(visit[0]));
printf("BFS:");
//先弄一个遍v开始的BFS
BFS(g,GetVIndex(g,v));
printf("\n");
//所有再遍历来一遍
for(int i = 0;i < g ->_vexnum;i++)//防止孤岛
{
if(visit[i] == 0)
{
BFS(g,i);
printf("\n");
}
}
}