一.引出
1.七桥问题
欧拉回路判定规则：
如果通奇数桥的地方多于两个，则不存在欧拉回路；
如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；
如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。
二.基本概念
1.图
1）由顶点（数据元素）的有穷非空集合和顶点之间边的集合组成。
2）表示为：G（V,E）<V:顶点的集合（不能是空集），顶点之间边的集合>
2.无向图
1）图中任意两个顶点之间的边都是无向边。
2）无向边：表示为(vi,vj)，顶点vi和vj之间的边没有方向。
3）邻接、依附：无向图中，对于任意两个顶点 vi 和顶点 vj，若存在边(vi，vj)，则称顶点 vi 和顶点 vj 互为邻接点，同时称边(vi，vj)依附于顶点 vi 和顶点 vj
3.有向图
1）图中任意两个顶点之间的边都是有向边。
2）有向边（弧）：表示为<vi,vj>，从vi 到vj 的边有方向
3）邻接、依附：有向图中，对于任意两个顶点 vi 和顶点 vj，若存在弧<vi，vj>，则称顶点 vi “邻接到 ”vj ，顶点 vj “邻接自”vi ，同时称弧<vi，vj>依附于顶点 vi 和顶点 vj
4.稠密图，稀疏图
5.完全图
1）无向完全图：无向图中，任意两个顶点之间都存在边。
n×(n-1)/2
2）有向完全图：有向图中，任意两个顶点之间都存在方向相反的两条弧。
n×(n-1)<有2倍关系>
6.权
1）权：对边赋予的有意义的数值量
2）带权图（网图），非带权图
7.度，入度，出度及其与边的关系：
1）无向图——度TD（v)
2）有向图——入度 ID(v)、出度OD(v)
7.路径
1）无向图中：顶点vp和顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,…, vim=vq)，其中(vij-1,vij)∈E(1≤j≤m)
eg:
2）在有向图中：从顶点vp到顶点vq的路径是一个顶点序列(vp=vi0,vi1, …, vim=vq)，其中<vij-1,vij>∈E(1≤j≤m)
eg:
3)
简单路径：序列中顶点不重复出现的路径
简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
4）路径长度：
非带权图——路径上边的个数
带权图——路径上边的权值之和
8.子图
9.连通——对于无向图来说
1）连通顶点：在无向图中，如果顶点vi和顶点vj(i≠j)之间有路径，则称顶点vi和vj是连通的
2）连通图：在无向图中，如果任意两个顶点都是连通的（任意两个顶点之间都有路径），则称该无向图是连通图
3）连通分量：非连通图的极大连通子图
（是对无向图的划分）
PS：含有极大顶点数
依附于这些顶点的所有边
10.强连通——对于有向图来说
1）强连通图：有向图中，若对于每一对顶点vi和vj ，都存在一条从vi到vj和从vj到vi的路径（每个顶点之间都有两条边），此有向图为强连通图。
2）强连通分量：有向图的极大强连通子图
PS：
a)任何强连通图的强连通分量只有一个——本身
b)非强连通图则有多个强连通分量。
例题：
1.设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。
//0 n(n-1)/2 0 n(n-1)
2.在一个无向图中，所有顶点的度数之和等于所有边数的（）倍
//2
3.无向图G有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3，则图G至少有（ ）个顶点。
//11
//"顶点越少,那么每个顶点的度越大，在无向图中：边的个数的2倍=为所有顶点度数之和，故：3*4+4*3+(x-3-4)*2>=16*2
4.n个顶点的强连通图至少有（）条边，其形状是（）
//（强连通图——有向）n，环形
三.图的存储结构
1.图不可以采用顺序存储结构
无法通过存储位置表示：任何两个顶点之间存在的关系。
2.将点和边分开存储
邻接矩阵（也称：数组表示法）：
1基本思想：
一维数组：存储图中顶点的信息
二维数组（邻接矩阵）：存储图中各顶点之间的邻接关系
2.
1）无向图：
2）邻接点：
3）有向图：
4）网图——无向图（对称）
3.存储结构的定义：
#define MaxSize 10//十个顶点
typedef char DataType;
typedef struct
{
DataType vertex[MaxSize]; //存储点
int edge[MaxSize][MaxSize];//存储关系
int vertexNum, edgeNum;//顶点数量 边数
} MGraph;
4.图的建立：
//输入：n个顶点,e条边
//结果：
1）伪代码：
算法：CreatGraph(a[n], n, e)
输入：顶点的数据a[n]，顶点个数n，边的个数e
输出：图的邻接矩阵
1. 存储图的顶点个数和边的个数；
2. 将顶点信息存储在一维数组vertex中；
3. 初始化邻接矩阵edge；//int edge[MaxSize][MaxSize]={0}；
4. 依次输入每条边并存储在邻接矩阵edge中：
4.1 输入边依附的两个顶点的编号i和j；
4.2 将“edge[i][j]和edge[j][i]”（两个）的值置为1；
2）实现代码：
void CreatGraph(MGraph *G, DataType a[ ], int n, int e)
{
int i, j, k;
G->vertexNum = n; G->edgeNum = e;//输入顶点的个数和边的个数
//存储顶点信息
for(i=0;i<G->vertexNum;i++)
{
G->vertex[i]=a[i];
}
//1）初始化邻接矩阵
for(i=0;i<G->vertexNum;i++)
{
for(j=0;j<G->vertexNum;j++)
{
G->edge[i][j]=0;
}
}
//2）在定义时：
//int edge[MaxSize][MaxSize]={0}；
//依次输入每一条边
for(k=0;k<G->edgeNum;k++)
{
scanf("%d %d",&i,&j);//输入边依附的顶点编号
G->edge[i][j]=1;
G->edge[j][i]=1;
}
}
3)图的邻接矩阵不需要销毁
图的邻接矩阵存储是静态存储分配–>在图变量退出作用域时自动释放所占内存单元–>图的邻接矩阵存储无需销毁
4）存储的空间复杂度：O（n^2)
最坏情况——稀疏矩阵
1.基本思想：
2.存储结构定义：
#define MaxSize 10
typedef char DataType;
//边表————邻接点组成的单链表
typedef struct EdgeNode
{
int adjvex;
struct EdgeNode *next;
} EdgeNode;
// 顶点表
typedef struct
{
DataType vertex;
EdgeNode *first;
} VertexNode;
//整体定义
typedef struct
{
VertexNode adjlist[MaxSize];
int vertexNum, edgeNum;
} ALGraph;
3.时间复杂度：O（n+e）
4.一些问题：
1）求顶点 v 的度——顶点 v 的边表中结点的个数
p = adjlist[v].first;
count = 0;
while (p != NULL)
{
count++;
p = p->next;
}
2）求顶点 v 的所有邻接点——顶点 i 的边表中的所有结点
3）判断顶点 i 和顶点 j 之间是否存在边——测试顶点 i 的边表中是否存在数据域为 j 的结点
4）
求顶点 v 的出度——顶点 v 的出边表中结点的个数
求顶点 v 的入度——边表中数据域为 v 的结点个数
5）如何存储带权图——权值存储在边表中
5.图的建立：
1）
2）伪代码：
算法：CreatGraph(a[n], n, e)
输入：顶点的数据信息a[n]，顶点个数 n，边的个数 e
输出：图的邻接表
1. 存储图的顶点个数和边的个数；
2. 将顶点信息存储在顶点表中，将该顶点边表的头指针初始化为NULL；
3. 依次输入边的信息并存储在边表中：
3.1 输入边所依附的两个顶点的编号 i 和 j；
3.2 生成边表结点 s，其邻接点的编号为 j；
3.3 将结点 s 插入到第 i 个边表的表头；
3）实现代码：
void CreatGraph(ALGraph *G,DataType a[],int n,int e)
{
int i,j,k;
EDgeNode *s=NULL;
G->vertexNum=n;
G->edgeNum=e;
//建立一个顶点表
for(i=0;i<G->vertexNum;i++)
{
G->adjlist[i].vertex=a[i];
G->adjlist.first=NULL;
}
//完善边表
for(k=0;k<G->edgeNum;k++)
{
scanf("%d %d",&i,&j);
s=(EdgeNode*)malloc(sizepf(EdgeNode));
s->adjvex=j;
s->next=G->adjlist[i].first;
G->adjlist[i].first=s;
}
}
6.图的销毁：
//在邻接表存储中，须释放所有在程序运行过程中申请的的“边表结点”
void DestroyGraph(ALGraph *G)
{
EdgeNode *p = NULL, *q = NULL;
for (int i = 0; i < G->vertexNum; i++)
{
p = q = G->adjlist[i].first;
while (p != NULL)
{
p = p->next;
free(q);
q = p;
}
}
}
四.图的遍历
##从图中某一顶点出发访问图中所有顶，并且每个结点仅被访问一次
1.选取遍历的起始点：
将图中的顶点按任意顺序排列起来， 从编号最小的顶点开始
2.若为非连通图（不是任意两个顶点之间都有边）：
多次调用图遍历算法
3.避免陷入死循环：
附设访问标志数组visited[n]（记录访问的次数）
4.访问次序：
深度优先遍历
广度优先遍历
1.深度优先遍历：（递归）（用栈）
1）基本思想：
a)访问顶点 v
b)从 v 的未被访问的邻接点中选取一个顶点 w，从 w 出发进行深度优先遍历
c)重复上述两步，直至访问所有和 v 有路径相通的顶点
2)伪代码：
算法:DFTraverse
输入:顶点的编号 v
输出:无
1. 访问顶点 v ; 修改标志visited[v] = 1;
2. w =顶点 v 的第一个邻接点；
3. while (w 存在)
3.1 if (w 未被访问) 从顶点 w 出发递归执行该算法;
3.2 w = 顶点 v 的下一个邻接点;
3.1)实现代码：
//邻接矩阵
//void DFTraverse(MGraph *G, int v)【顶点编号V0】
void DFTraverse(MGraph *G, int v) /*全局数组变量visited[n]已初始化为0*/
{
printf("%c ", G->vertex[v]); visited[v] = 1;//输出顶点的值，并将标记为设为1
for (int j = 0; j < G->vertexNum; j++)//不知道每一个顶点有多少条边
{
//无向图：v行，v列均可
//有向图：（需要看“出度”,才能到达）必须为v行，故此处都用“行”
if (G->edge[v][j] == 1 && visited[j] == 0) //j相当于v的下角标
{
DFTraverse(G, j);
}
}
}
3.2)实现代码
//邻接表
void DFTraverse(ALGraph *G, int v)
{
EdgeNode *p = NULL;
int j;
printf("%c ", G->adjlist[v].vertex);
visited[v] = 1;
p = G->adjlist[v].first;
while (p != NULL)
{
j = p->adjvex;
if (visited[j] == 0)
{
DFTraverse(G, j);
}
p = p->next;
}
}
2.广度优先：（用队列）（类似于层序遍历——先进来一个V0，V0出队的时候它的所有可一步到达的点全都进来）
1）基本思想：
⑴ 访问顶点 v
⑵ 依次访问 v 的各个未被访问的邻接点 v1 , v2 , …, vk
⑶ 分别从 v1 , v2 , …, vk 出发依次访问它们未被访问的邻接点，直至访问所有与顶点 v 有路径相通的顶点
//邻接矩阵
2.1）伪代码：
算法：BFTraverse
输入：顶点的编号 v
输出：无
1. 队列 Q 初始化;
2. 访问顶点 v ; 修改标志visited [v] = 1; 顶点 v 入队列 Q;
3. while (队列 Q 非空)
3.1 v = 队列 Q 的队头元素出队;
3.2 w = 顶点 v 的第一个邻接点;
3.3 while (w 存在)
3.3.1 如果 w 未被访问，则访问顶点 w ; 修改标志visited[w] = 1; 顶点 w 入队列 Q；
3.3.2 w = 顶点 v 的下一个邻接点；
3.1）实现代码：
//邻接矩阵
void BFTraverse(MGraph *G, int v) /*全局数组变量visited[n]已初始化为0*/
{
//队列————int
int i, j, Q[MaxSize];/*采用顺序队列，存储顶点编号*/
int front = rear = -1;/*初始化顺序队列*/
printf("%c ", G->vertex[v]);
visited[v] = 1;
Q[++rear] = v;
while (front != rear)/*当队列非空时*/
{
i = Q[++front];
for (j = 0; j < G->vertexNum; j++)
{
if (G->edge[i][j] == 1 && visited[j] == 0 ) //有边且没有被访问过
{
printf("%c ", G->vertex[j]);
visited[j] = 1; //标志已经被访问过
Q[++rear] = j;//入队
}
}
}
//邻接表
2.2）伪代码：
算法：BFTraverse
输入：顶点的编号 v
输出：无
1. 队列 Q 初始化;
2. 访问顶点 v ; 修改标志visited [v] = 1; 顶点 v 入队列 Q;
3. while (队列 Q 非空)
3.1 i = 队列 Q 的队头元素出队;
3.2 j = 顶点 v 的第一个邻接点;
3.3 while (j 存在)
3.3.1 如果 j 未被访问，则访问顶点 j ; 修改标志visited[j] = 1; 顶点 j 入队列 Q；
3.3.2 j = 顶点 i 的下一个邻接点；
3.2）实现代码：
void BFTraverse(ALGraph *G, int v)
{
EdgeNode *p = NULL;
int Q[MaxSize], front = rear = -1, i, j;
printf("%c ", G->adjlist[v].vertex);
visited[v] = 1;
Q[++rear] = v;
while (front != rear)
{
i = Q[++front];
p = G->adjlist[i].first;
while (p != NULL)
{
j = p->adjvex;
if (visited[j] == 0)
{
printf("%c ", G->adjlist[j].vertex);
visited[j] = 1;
Q[++rear] = j;
}
p=p->next;
}
}
}
4）讨论：
a.深度优先搜索结果唯一吗？
问题描述】
输入指定的边数和顶点数建立图，并输出深度优先遍历和广度优先遍历的结果。
实验要求：在程序中定义下述函数，并实现要求的函数功能：
CreateGraph(): 按从键盘输入的顶点数和边数建立图
DFSGrahp()：深度优先遍历图
BFSGrahp()：广度优先遍历图
实验提示：
图的存储可采用邻接表或邻接矩阵，若采用邻接表存储，“要求边链表中结点按顶点序号递增次序排列；”<保证输出结果唯一>
【输入形式】
首先输入一个n表示有n个节点（1-n）编号，再输入一个 m 表示下边接下来 m 行，每行两个整数 a b，表示a b有条无向边。
【输出形式】
第一行输出1号节点开始的深度优先遍历结果（DFS），第二行输出1号节点开始的广度优先遍历结果（BFS）
//(无向图)输入指定的边数和顶点数建立图，并输出深度优先遍历和广度优先遍历的结果。
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 10
//为了好定义，下面输入的n不能在现在用于结构体里数组的定义
//1.存储结构的定义
//1)边表---邻接点组成的单链表
typedef struct EdgeNode
{
int adjvex;
struct EdgeNode *next;
}EdgeNode;
//2)顶点表
typedef struct
{
int vertex;
EdgeNode *first;//统一格式
}VertexNode;
//3)整体定义
typedef struct
{
VertexNode adjlist[MaxSize];//MaxSize=n相当于顶点的个数
int vertexNum;//vertexNum==n;
int edgeNum;//edgeNum==m;
}ALGraph;
int visited[MaxSize]={0};
//2.图的建立
ALGraph CreatGraph(ALGraph G,int n,int m)
/*图：G(有一个顶点表)
int n,int m：将点和边的数量传递过来
*/
{
int i,a,b,t,j,count;
EdgeNode *s=NULL;
EdgeNode *p=NULL;
G.vertexNum=n;
G.edgeNum=m;
//建立一个顶点表
for(i=1;i<=G.vertexNum;i++)
{
G.adjlist[i].vertex=i;
G.adjlist[i].first=NULL;
}
//完善边表
for(i=1;i<=G.edgeNum;i++)
{
scanf("%d %d",&a,&b);
count=0;
for(j=0;j<2;j++)
{
if(count!=0)
{
t=a;
a=b;
b=t;
}
p=G.adjlist[a].first;
if(p==NULL)
{
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=b;
s->next=G.adjlist[a].first;
G.adjlist[a].first=s;
}
else
{
while(b>p->adjvex&&p->next!=NULL)
{
p=p->next;
}
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=b;
s->next=p->next;
p->next=s;
if(s->adjvex<p->adjvex)
{
t=s->adjvex;
s->adjvex=p->adjvex;
p->adjvex=t;
}
}
count++;
}
}
return G;
}
//3.遍历
/*
深度优先：
从 v 的未被访问的邻接点中选取一个顶点 w，从 w 出发进
行深度优先遍历
广度优先：
依次访问v的各个未被访问的邻接点
*/
//1.2)深度优先(递归)
void DFSGrahp(ALGraph G,int v)
{
EdgeNode *p = NULL;
printf("%d ", G.adjlist[v].vertex);
visited[v] = 1;
p = G.adjlist[v].first;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
{
DFSGrahp(G,p->adjvex);
}
p = p->next;
}
}
//2)广度优先
void BFSGrahp(ALGraph G,int v)
{
int visited[MaxSize]={0};
EdgeNode *p=NULL;
int Q[MaxSize],i,j;
int front=-1,rear=-1;
printf("%d ",G.adjlist[v].vertex);
visited[v]=v;
Q[++rear]=v;
while(front!=rear)
{
i=Q[++front];//i=G->adjlist[0].vertex
p=G.adjlist[i].first;
while(p!=NULL)
{
j=p->adjvex;
if(visited[j]==0)
{
printf("%d ",G.adjlist[j].vertex);
visited[j]=1;
Q[++rear]=j;
}
p=p->next;
}
}
}
int main()
{
int n,m;//n个结点，m条边
scanf("%d %d",&n,&m);
//创建一个图
ALGraph G;
G=CreatGraph(G,n,m);
//遍历
int v=1;
DFSGrahp(G,v);
printf("\n");
BFSGrahp(G,v);
return 0;
}
【样例输入】
6 8
1 5
5 2
2 6
1 4
4 5
2 3
3 6
4 3
【样例输出】
1 4 3 2 5 6
1 4 5 3 2 6