1、图
1）图 Graph
是一种非线性的数据结构
节点之间的关系是任意的，图中任意的两个数据元素之间都有可能相关
图的形式化描述
Graph = ( V, R )
其中 V = { Vi | Vi属于图中的数据元素(i=0,1,2,3,...n-1),顶点的集合，当n=0时，V是空集}
R = { <vi,vj> | vi,vj都属于集合V，且vi和vj之间存在路径的 0<= i,j <= n-1}
是顶点之间的关系的集合
<vi,vj>为顶点vi到顶点vj之间是否存在路径的判定条件
即 如果顶点vi到顶点vj之间是存在路径的，那么<vi,vj>属于集合R
图是一个二元组，是 顶点 以及 顶点之间的路径的 集合
2）分类
无向图
路径 --> 边
如果<vi,vj>存在，那么<vj,vi>就一定存在
有向图
路径 --> 弧
如果<vi,vj>存在，那么<vj,vi>就不一定存在
3）网
如果在图的关系<vi,vj>或者<vj,vi>上 附加一个权值w，称w为弧或者边上的权
带权值的图 称为 网
4）顶点的度
顶点的边或者弧的条数
有向图 分为 ：入度 和 出度
5）图的物理存储结构
存储图需要存储哪些东西？
顶点的集合 --> 数据元素的集合
关系的集合 --> 顶点与顶点之间的关系
“数据表示法” 邻接矩阵
“邻接表”
“十字链表”
“邻接多重表”
邻接点：
在无向图中，如果存在一条边(vi,vj),则vi和vj互为邻接点
在有向图中，如果存在一条弧<vi,vj>，则vi是该弧的起点，vj是弧的终点
称 vj是vi的邻接点
() --> 路径
<> --> 关系
2、“数组表示法” 邻接矩阵 Adjacency matrix
G = (V, R)
用两个数组来保存图G
一个 一维数组 来存储顶点的集合
一个 二维数组 来存储图G中 顶点之间的关系
typedef char VType; //顶点的数据类型
typedef int AdjType; //权值的类型
#define MAXN 256
struct Graph
{
VType V[MAXN]; //一维数组 来存储顶点的集合
AdjType Adj[MAXN][MAXN]; //二维数组 来存储图G中 顶点之间的关系
int vex_num; //顶点的个数
int arc_num; //图中 弧的个数
};
3、“邻接表” Adjacency List
数组 + 链表
所谓 邻接表就是将图中的每一个顶点v 和 由v出发的边或者弧 构成的一个单链表
邻接表 是 图的一种链式的存储结构
struct adj //邻接表 节点的类型
{
int termIndex; //边的终点在顶点数组中的下标
int w; //权值
struct adj *next; //指向下一个点
};
struct Vertex //顶点结构体数组的类型
{
VType data;
struct adj *first;
};struct Vertex graph[MAXN]; //顶点结构体数组
4、代码实现
邻接矩阵 方法实现图
typedef char VType; //顶点的数据类型
typedef int AdjType; //权值的类型
#define MAXN 256
struct Graph
{
VType V[MAXN]; //一维数组 来存储顶点的集合
AdjType Adj[MAXN][MAXN]; //二维数组 来存储图G中 顶点之间的关系
int vex_num; //顶点的个数
int arc_num; //图中 弧的个数
};
Graph.c / Graph.h
练习：
1）创建一个图
//创建一个图
struct Graph * create_graph()
{//1.创建一个空图,把关系集合初始化struct Graph *g = malloc(sizeof(struct Graph));g->vex_num = 0;g->arc_num = 0;//把关系的集合否赋值为无穷大/小 INT_MAX / INT_MIN //或者 自定义一个宏 #define ADJ_MAX 65535int i,j;for( i=0; i<MAXN; i++ ){for(j=0; j<MAXN; j++ ){g->Adj[i][j] = ADJ_MAX;}}//2.根据用户的输入 初始化顶点的集合printf("please input the Vertex value (eg: abcdefg ) :\n");char vex[MAXN] = {0};scanf("%s", vex);getchar();//吸收掉回车i=0;while( vex[i] ){g->V[i] = vex[i]; //把顶点数据 保存到图g中顶点集合Vg->vex_num ++ ;i++;}//3.根据用户的输入 初始化邻接矩阵（关系的集合：顶点s到顶点d的权值为w）printf("please input the Relations value (NO space ! eg: ab15 ac2 ad12 ) :\n");while(1){VType s,d;int w;scanf("%c%c%d", &s, &d, &w ); //注意：输入时一组数据中不用空格隔开getchar(); //吸收掉回车if( s == '#' || d == '#' ) //人为约定退出条件{break;}//找出顶点s,d 在顶点集合V中对应的下标 int si = find_index( g->V, g->vex_num, s );int di = find_index( g->V, g->vex_num, d );//保存关系 权值 if( si != -1 && di != -1 ){g->Adj[si][di] = w;g->arc_num ++ ;}}return g;}//打印一个图
void print_graph(struct Graph *g)
{//打印顶点数组 int i,j;putchar('\t');for(i=0; i<g->vex_num; i++ ){printf("%c\t", g->V[i] );}putchar('\n');//打印关系 for( i=0; i<g->vex_num; i++ ){printf("%c:\t", g->V[i] );for( j=0; j<g->vex_num; j++ ){if( g->Adj[i][j] == ADJ_MAX ){printf("-\t");}else{printf("%d\t", g->Adj[i][j] );}}putchar('\n');}}5、图的遍历
图的遍历 是树的遍历的推广，是按照某种规则访问图中的每一个顶点，且只访问一次
也就是 将网状结构按照某种规则线性化的过程
对于图的遍历： “深度优先搜索” 和 “广度优先搜索”
1）深度优先搜索 DFS： Depth First Search ---》 类似于树的先序遍历
设 初始时，图中各个顶点都是未被访问的，
从图中的某个顶点出发(设为v0)，先访问v0，
然后再找v0的邻接点vi，如果vi未被访问，那么就按照同样的方式去访问vi，
再去搜索vi的邻接点 ... (深度优先搜索)
如果该顶点所有的邻接点都被访问完毕，则回溯到它的上一个顶点
然后再去以该顶点 以“深度优先搜索”的方式 去搜索其余的邻接点 ...
直到那个访问的顶点 全部都被访问完毕
DFS( g, v ) --> 从图g中以顶点v出发，按照深度优先搜索的算法
去访问v的邻接点，v的邻接点v1,v2,v3,...vn
v未被访问
visit v
if( not visit v1 )
{
visit v1
DFS( g, v1 ); //按照同样的规则DFS去访问v1的邻接点
}
if( not visit v2 )
{
visit v2
DFS( g, v2 ); //按照同样的规则DFS去访问v2的邻接点
}
...
if( not visit vn )
{
visit vn
DFS( g, vn ); //按照同样的规则DFS去访问vn的邻接点
}
代码实现：
// ============= DFS 深度优先搜索 ====================================int visit[MAXN]; //访问 标志位数组，表示下标对应的顶点是否以及访问//0表示没有访问，1表示已经被访问了//在图g中，找到v的第一个邻接点的下标
int FirstAdjVex(struct Graph *g, int v)
{//遍历，判断与各个顶点是否存在路径int i;for( i=0; i<g->vex_num; i++ ){if( g->Adj[v][i] != ADJ_MAX ) //关系存在{return i;}}return -1;
}//在图g中，找到v的邻接点w的下一个邻接点的下标
int NextAdjVex(struct Graph *g, int v, int w)
{int i;for( i=w+1; i<g->vex_num; i++ ){if( g->Adj[v][i] != ADJ_MAX ) //关系存在{return i;}}return -1;
}//深度优先搜索
void DFS(struct Graph *g, int v)
{//1.先访问v visit[v] = 1;printf("%c ", g->V[v] );//2.找到v的第一个邻接点的下标w，如果x未被访问 //就按照 深度优先搜索的方式去访问w//for( 取v的第一个邻接点w; w != -1; 再取下一个邻接点 )int w;for( w=FirstAdjVex(g, v); w != -1; w=NextAdjVex(g, v, w) ){if( visit[w] == 0 ) //未被访问{DFS( g, w );}}
}//以深度优先搜索的算法，去遍历图g中的每一个顶点
void DFS_Traverse(struct Graph *g)
{//先把标志位全部置0int i;for( i=0; i<g->vex_num ; i++ ){visit[i] = 0;}printf("\n------- DFS --------\n");//深度优先搜索去遍历图中的每一个顶点for( i=0; i<g->vex_num; i++ ){if( visit[i] == 0 ){DFS( g, i); //从顶点i出发，按照深度优先搜索的算法，去遍历图g中的每一个顶点}}putchar('\n');
}
2）广度优先搜索 BFS：Breath First Search ---》 类似于树的层次遍历
设 初始时，图中各个顶点都是未被访问的，
从图中的某个顶点v0出发，去访问它，并依次访问完v0的所有的邻接点
然后 再从这些已经访问的邻接点中，仍然按照广度优先搜索 的方式去访问它的邻接点...
直到所有的顶点全部访问完毕
用到 队列的思想
入队元素 先访问再入队
出队元素 把它所有未被访问的邻接点入队
// ============= BFS 广度优先搜索 ====================================//广度优先搜索
void BFS( struct Graph * g, int v )
{//初始化一个队列 CircleQueue.c / CircleQueue.hstruct CircleQueue * cq = InitQueue();//访问v，然后再把v入队（只需要入队顶点的下标）visit[v] = 1;printf("%c ", g->V[v] );EnQueue( cq, v ); //把v入队while( ! IsEmpty(cq) ) //队列不为空 {//出队，获取该顶点的下标i，把i所有的未被访问的邻接点入队int i = 0;DeQueue( cq, &i );//for( 取i的第一个邻接点w; w != -1; 再取下一个邻接点 )int w = 0;for( w=FirstAdjVex(g, i); w != -1 ; w=NextAdjVex(g,i,w) ){if( visit[w] == 0 ){//先访问，再入队visit[w] = 1;printf("%c ", g->V[w] );EnQueue(cq, w);}}}//销毁队列DestroyQueue(cq);}//以广度优先搜索的算法，去遍历图
void BFS_Traverse(struct Graph *g)
{//先把标志位全部置0int i;for( i=0; i<g->vex_num; i++ ){visit[i] = 0;}//以广度优先搜索的算法，去遍历图printf("\n------- BFS --------\n");for( i=0; i<g->vex_num; i++ ){if( visit[i] == 0 ){BFS( g , i ); //以顶点i出发，按照广度优先搜索的方法去访问}}putchar('\n');}
6、最短路径问题
解决带权有向图中 两个顶点之间的最短距离的问题
两个经典的算法：
Dijkstra（迪杰斯特拉）算法 和 Floyd（弗洛伊德）算法
都是基于比较 v0vi 与 v0vk+vkvi 的大小的基本算法
Dijkstra（迪杰斯特拉）算法：使用两层循环 计算一个顶点到其他各个顶点的最短距离
Floyd（弗洛伊德）算法 ：使用三层循环 计算每一个顶点到其他各个顶点的最短距离
Dijkstra（迪杰斯特拉）算法：
是解决网络中任意的顶点(源点)出发，
求它到其他的各个顶点(终点)的最短距离
基本思想：
如果顶点vi --》顶点vj的最短距离是经过顶点vk的
那么 <vi,vj>路径中，顶点vi到顶点vk的路径 一定是vi到vk的最短路径
需要三个辅助变量：
v：表示以v为下标的顶点（源点）
(1)向量 S[n] 标记最短路径是否已经求出来了 （标志位数组）
S[i] == 1 源点v到顶点i的最短距离已经被求出来了
S[i] == 0 源点v到顶点i的最短距离还没有被求出来
初始时 S[v] = 1, 其他的S[i] = 0
(2)向量 dist[n]
dist[i] --> 存放 源点v 到 顶点i 的最短距离的长度
初始时，dist[i]
<v,vi>上的权为w，如果p(v,vi)存在，也就是v到vi有一条直接路径
如果(v,vi)不存在，dist[i] = 无穷大 ，也就是说 v到vi没有直接路径
(3)向量 path[n]
path[i] --> 存放 源点v 到 顶点i 的最短路径(v -> ... -> vi )
初始时 path[i] = {v}
算法：
1)把源点v 到 其他各个顶点的第一条最短路径长度（直接路径）求出来 //初始化dist[n]
2)dist[m] = MIN( dist[i] | i=0,1,2,... 且S[i] == 0 )
表示在所有未被求出来的最短路径中 找出一条最短的，其长度当作成当前求出的最短路径
3) 对于所有的 S[i] == 0 （源点v到顶点i的最短距离还没有被求出来）
if( dist[m] + <m, i> < dist[i] )
{
更新 dist[i] = dist[m] + <m, i> ;
}
重复 2) 和 3) ....
/*
用Dijkstra算法 求从v出发到其他各个顶点的最短距离
*/
//================== Dijkstra算法 ======================int S[MAXN]; //是否已经求出最短路径，标志位数组
int dist[MAXN]; //存放源点到其他顶点的最短路径长度
int path[MAXN]; //存放源点到终点i的最短路径，时利用哪些最优点更新的/*用Dijkstra算法 求从v出发到其他各个顶点的最短距离
*/
void Dijkstra(struct Graph *g, int v)
{//1.初始化辅助变量 int i;for( i=0; i<g->vex_num; i++ ){S[i] = 0;dist[i] = g->Adj[v][i];path[i] = v;}S[v] = 1;dist[v] = 0;//在所有未被求出来的最短路径中 找出一条最短的，其长度当作成当前求出的最短路径int min; //保存最小值int min_i; //最优点的下标int j; //寻找最短路径的次数，每次找一条for( j=0; j<g->vex_num; j++ ){//2.求出当前的最优点 （在dist[n]找最小值）min = ADJ_MAX;for( i=0; i<g->vex_num; i++ ){if( S[i] == 0 && dist[i] <= min ){min = dist[i];min_i = i;}}S[min_i] = 1;//3.根据最优的顶点去比较，更新其他的distfor( i=0; i<g->vex_num; i++ ){if( S[i] == 0 ){// dist[m] + <m, i> < dist[i]if( dist[min_i]+ g->Adj[min_i][i] < dist[i] ){//更新dist[i] = dist[min_i]+ g->Adj[min_i][i]; path[i] = min_i;}}}}}// a --> b : 15
void print_dist(struct Graph *g, int v)
{printf("\n ------ dist[n] ------ \n");int i;for( i=0; i<g->vex_num; i++ ){printf("%c --> %c : %d\n", g->V[v], g->V[i], dist[i] );}
}// a --> g : a c f d g
void print_path(struct Graph *g, int v)
{printf("\n ------ path[n] ------ \n");int i;for( i=0; i<g->vex_num; i++ ){if( dist[i] == ADJ_MAX ){printf("%c --> %c : is no path !!!\n",g->V[v], g->V[i]);continue;}printf("%c --> %c : ",g->V[v], g->V[i]);int j = path[i];char a[MAXN];int count = 0;a[count++] = g->V[i];while(1){a[count++] = g->V[j];if( j == v ){break;}j = path[j];}int k;for( k=count-1; k>=0; k-- ){printf("%c ", a[k] );}putchar('\n');}
}
