【数据结构】图

标签：typedef int MAX 路径邻接顶点数据结构

图的定义和基本术语

【数据结构】图_邻接矩阵

【数据结构】图_最小生成树_02

【数据结构】图_深度、广度优先搜索_03

【数据结构】图_邻接矩阵_04

【数据结构】图_邻接矩阵_05

【数据结构】图_邻接表_06

【数据结构】图_最小生成树_07

【数据结构】图_最短路径_08

【数据结构】图_最短路径_09

边或弧可以关联相应的值，这些值称作边或弧的权，带权图通常称作网。

【数据结构】图_最小生成树_10

对于无向图G＝(V, {E})，如果边(v, v’)∈E，则称v 和v’互为邻接点，或称v和v’相邻接。

此时称边(v, v’) 依附于顶点v 和v’，或边(v, v’)和顶点v 和v’ 相关联。

和顶点v相关联的边的数目称为顶点v的度，记为TD(v) 。

对于有向图G=(V, {A})，若弧<v,v’> ∈A，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v，弧<v,v’> 和顶点v，v’相关联。

以顶点v为头的弧的数目，称顶点v的入度，记为ID(v)；以v为尾的弧的数目，称顶点v的出度，记为OD(v)。顶点v的度TD(v)=ID(v)+OD(v) 。

若图G中有n个顶点，e条边或弧，每个顶点的度为TD(vi)，则：

【数据结构】图_邻接表_11

【数据结构】图_邻接表_12

【数据结构】图_最小生成树_13

【数据结构】图_邻接表_14

在有向图G中，如果任意两个顶点都是连通的，则称此图为强连通图。有向图的极大强连通子图称该图的强连通分量

【数据结构】图_最短路径_15

【数据结构】图_最小生成树_16

图的类型定义

ADT Graph{

数据元素V：

数据关系R：

基本操作：

CreatGraph(&G, V, R)

DestroyGraph(&G)

LocateVex(G, u)

GetVex(G, v)

PutVex(&G, v, value)

FirstAdjVex(G, v) //返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空。

NextAdjVex(G, v, w)//返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回空。

InsertVex(&G, v)

DeleteVex(&G, v)

InsertArc(&G, v, w)

DeleteArc(&G, v, w)

DFSTraverse(G, Visit())//对图进行深度优先遍历，在遍历过程中队每个顶点调用visit一次且仅一次。一旦visit（）失败，则操作失败。

BFSTraverse(G, Visit())//对图进行广度优先遍历。在遍历过程中对每个顶点调用函数visit一次且仅一次。一旦visit（）失败，则操作失败。

}ADT Graph

图的存储结构

数组（邻接矩阵）表示法

无向图的邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n✖n的方阵，定义为：

【数据结构】图_最小生成树_17

无向图的邻接矩阵是对称的；

顶点i的度=第i行（列）中1的个数；

特别的：完全图的邻接矩阵中，对角元素为0，其余为1。

有向图的邻接矩阵表示法

【数据结构】图_邻接表_18

有向图的邻接矩阵可能是不对称的。

顶点的出度=第i行元素之和。

顶点的入度=第i列元素之和

顶点的度=顶点的出度+顶点的入度

网（即有权图）的邻接矩阵表示法

【数据结构】图_最小生成树_19

邻接矩阵的存储表示

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20//最大顶点个数
typedef enum{DG,DN,UDG,UDN}GraphKind;//有向图，有向网，无向图，无向网
typedef struct ArcCell
{
  //用1或0表示相邻否；
  //对带权图，则为权值类型
  VRType adj;
  InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
  VertexType vexs[MAX_VERTEX_NUM];//顶点向量
  AdjMatrix arcs;//邻接矩阵
  int vexnum,arcnum;//图的当前点数和边数
  GraphKind kind;//图的种类
}MGraph;

采用邻接矩阵表示法创建无向图

算法思想：

（1）输入总顶点数和总边数。

（2）依次输入点的信息存入顶点表中。

（3）初始化邻接矩阵，使每个权值初始化为极大值。

（4）构造邻接矩阵

Status CreateUDN(MGraph &G)
{
  scanf(&G.vexnum,&G.arcnum,&IncInfo);
  for(i=0;i<G.vexnum;++i)
    scanf(&G.vexs[i]);//构造顶点向量
  for(i=0;i<G.vexnum;++i)//初始化邻接矩阵
    for(j=0;j<G.vexnum;++j)
      G.arcs[i][j]={INFINITY,NULL};
  for(k=0;k<G.arcnum;++k)
  {
    scanf(&v1,&v2,&w);//输入一条边依附的顶点及权值
    i=LocateVex(G,v1);
    j=LocateVex(G,v2);//确定v1和v2在G中的位置
    G.arcs[i][j].adj=w;
    if(IncInfo)
      Input(*G.arcs[i][j].info);
    G.arcs[j][i]=G.arcs[i][j];
  }
  return OK;
}

补充算法：在图中查找顶点

int LocateVex(MGraph G,VertexType v)
{
	int i;
	for(i=0;i<G.arcnum;i++)
		if(!strcmp(G.vexs[i],v))
			return i;
	return -1;
}
/*此函数的作用是在无向图G中查找节点名称为v的顶点，并返回其位置。具体逻辑如下：

1. 首先定义一个循环变量i，用于遍历G中的所有边；
2. 在循环中，先判断G中第i条边的节点名称是否与v相等，如果相等则返回i；
3. 如果循环结束后仍未找到，则返回-1，表示未找到。*/

无向网就是有权值w，需要为w进行赋值，无向图初始化邻接矩阵时，w均为0，构造邻接矩阵时，w为1；有向网仅为G.arc[i][j]赋值，无需为G.arcs[j][i]赋值。有向图就是把无向图和有向网的操作都给做了。

邻接矩阵的优缺点

优点：直观、简单、好理解；方便检查任意一对顶点间是否存在边；方便找任一顶点的所有邻接点（有边直接相连的顶点）；方便计算任一顶点的“度”。

缺点：不便于增加和删除；浪费空间——存稀疏图有大量无效元素；浪费时间——统计稀疏图中一共有多少条边。

邻接表表示法（链式）

无向图：

【数据结构】图_深度、广度优先搜索_20

类似于孩子表示法，将结点存入数组，并对节点的孩子进行链式存储，不管有多少孩子，也不会存在空间浪费问题。

顶点：按编号顺序将顶点数据存储在一维数组中；

关联同一顶点的边（以顶点为尾的弧）：

用线性链表存储

特点：

邻接表不唯一

若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。

无向图中顶点vi的度为第i个单链表中的结点数。

有向图

【数据结构】图_最小生成树_21

逆邻接表

【数据结构】图_深度、广度优先搜索_22

顶点vi的入度为第i个单链表中的结点个数。

顶点vi的出度为整个单链表中邻接点域值是i-1的结点个数。

如果我们想要知道某个顶点的度，就去查找这个顶点的边表中结点的个数。若要判断顶点vi到vJ是否存在边，只需要测试顶点vi的边表中adjvex是否存在vj的下标j就行。若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的adjvex域对应的顶点就是邻接点。

若是有向图，邻接表的结构是类似的。有向图由于有方向，我们是以顶点为弧尾来存储边表的，这样就很容易得到每个顶点的出度。但有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表，即对每个顶点vi都建立一个链接为v1为弧头的表。

【数据结构】图_最短路径_23

【数据结构】图_深度、广度优先搜索_24

图的邻接表存储表示

typedef struct VNode{
  VertexType        data;//顶点信息
  ArcNode          *firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct ArcNode{
  int               adjvex;//该边所指向的顶点的位置
  struct ArcNode   *nextarc;//指向下一条边的指针
  InfoType         *info;//和边相关的信息
}ArcNode;

【数据结构】图_最小生成树_25

【数据结构】图_最短路径_26

邻接表的特点

1.方便找任一顶点的所有邻接点，只需要数结点个数就可以得到。

2.节约稀疏图的空间（需要N个头指针+2E个结点）（每个结点至少两个域）

3.对于无向图：方便计算任一顶点的度；对有向图：只能计算出度；需要构造逆邻接表来方便计算入度。

4.不方便检查任意顶点之间有没有边

邻接矩阵与邻接表表示法的关系

1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。

2.区别：

①对于任一确定的无向图，邻接矩阵是唯一的（行列号域顶点编号一致），但是邻接表不唯一（连接次序与顶点编号无关）。

②邻接矩阵的空间复杂度为O（n^2），而邻接表的空间复杂度为O（n+e）。

3.用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图。

图的遍历

我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。

深度优先搜索DFS

图的任一顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原点，而有些顶点却还没有遍历到的情况。因此我们需要在遍历过程中把访问过的顶点打上标记，以避免访问多次而不自知。具体办法是设置一个访问数组visited[n]，n是图中顶点的个数，初值为0，访问过后设置为1。

从图中某个顶点V出发，访问此顶点，然后依次从V未被访问的邻接点出发深度优先搜索，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

【数据结构】图_最小生成树_27

遍历的实质就是找每个顶点的邻接点的过程。

方法：

【数据结构】图_最小生成树_28

采用邻接矩阵表示图的深度优先搜索遍历

Boolean visited[MAX];
Status (*VisitFunc)(int v);
void DFSTraverse(Graph G,Status (*Visit)(int v))
{
  VisitFunc=Visit;
  for(v=0;v<G.vexnum;v++)
    visited[v]=FALSE;
  for(v=0;v<G.vexnum;v++)
    if(!visited[v])
      DFS(G,v);
}
void DFS(Graph G,int v)
{
  visited[v]=TRUE;
  VisitFunc(v);
  for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
    if(!visit[w])
      DFS(G,w);//w是v的邻接点，如果w未访问，则递归调用DFS
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"my.h"
#define MAX_VERTEX_NUM 20
typedef char QElemType;
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef int VRType;
typedef char InfoType;
typedef char VertexType [10];
typedef struct ArcCell
{
	VRType adj;
	InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum,arcnum;
	GraphKind Kind;
}MGraph;
typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;
int visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(MGraph G,int v);
int LocateVex(MGraph G,VertexType v)
{
	int i;
	for(i=0;i<G.arcnum;i++)
		if(!strcmp(G.vexs[i],v))
			return i;
	return -1;
}
Status CreateUDN(MGraph *G)
{
	int i,j,k;
	char v1[20],v2[20];
	printf("请输入顶点和弧的个数：");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	for(i=0;i<G->vexnum;i++)
		scanf("%s",G->vexs[i]);
	for(i=0;i<G->vexnum;i++)
		for(j=0;j<G->vexnum;j++)
		{
			G->arcs[i][j].adj=0;
			G->arcs[i][j].info=NULL;
		 }
		printf("\n请输入边依附的顶点：\n"); 
	for(k=0;k<G->arcnum;k++)
	{
		scanf("%s%s",&v1,&v2);
		i=LocateVex(*G,v1);
		j=LocateVex(*G,v2);
		G->arcs[i][j].adj=G->arcs[j][i].adj=1;
	}
}
int FirstAdjVex(MGraph G,int v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(G.arcs[v][i].adj)
			return i;
	return -1;
}
int NextAdjVex(MGraph G,int v,int w)
{
	int k;
	if(!G.arcs[v][w].adj)
		return -1;
	for(k=w+1;k<G.vexnum;k++)
		if(G.arcs[v][k].adj)
			return k;
}
void DFS(MGraph G,int v)
{
	int w;
	visited[v]=TRUE;
	(*VisitFunc)(G,v);
	for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
		if(!visited[w])
			DFS(G,w);
}
void DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v))
{
	VisitFunc=Visit;
	int i;
	for(i=0;i<G.vexnum;i++)
		visited[i]=FALSE;
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
			DFS(G,i);
}
Status func(MGraph G,int v)
{
  printf("%s ",G.vexs[v]);
}
int main()
{
	MGraph G;
	int i,j;
	CreateUDN(&G);
	printf("建立的邻接矩阵为：\n");
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
			printf("%3d",G.arcs[i][j].adj);
		printf("\n");
	}
	printf("深度优先搜索结果为：\n");
	DFSTraverse(G,func);
	printf("\n");
}

【数据结构】图_最小生成树_29

DFS算法效率分析

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O（n^2)

用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O（n+e）。

结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。

采用邻接表表示图的深度优先算法

void DFS(ALGraph G,int v)
{
  int w;
  visited[v]=TRUE;
  (*VisitFunc)(G,v);
  for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
    if(!visited[w])
      DFS(G,w);
}
void DFSTraverse(ALGraph G,Status (*visit)(ALGraph G,int v))
{
  int i;
  VisitFunc=Visit;
  for(i=0;i<G.vexnum;i++)
    visited[i]=FALSE;
  for(i=0;i<G.vexnum;i++)
    if(!visited[i])
      DFS(G,i);
}

【数据结构】图_最小生成树_30

#define MAX_VERTEX_NUM 20
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"my.h"
typedef char VertexType[20];
typedef char InfoType;
typedef struct ArcNode
{
	int adjvex;
	struct ArcNode *nextarc;
	InfoType *info;
}ArcNode;
typedef struct VNode
{
	VertexType data;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
	AdjList vertices;
	int vexnum,arcnum;
	int kind;
}ALGraph;
int visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(ALGraph G,int v);
Status LocateVex(ALGraph G,char *v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(!strcmp(G.vertices[i].data,v))
			return i;
	return -1;
}
Status Create(ALGraph *G)
{
	int i,j,k;
	char v1[20],v2[20];
	ArcNode *p,*q;
	printf("请输入顶点数和边数：");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	for(i=0;i<G->vexnum;i++)
	{
		scanf("%s",G->vertices[i].data);
		G->vertices[i].firstarc=NULL;
	}
	printf("\n请输入边依附的顶点：\n");
	for(k=0;k<G->arcnum;k++)
	{
		scanf("%s%s",v1,v2);
		i=LocateVex(*G,v1);
		j=LocateVex(*G,v2);
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->nextarc=G->vertices[i].firstarc;
		G->vertices[i].firstarc=p;
		p->adjvex=j;
		
		q=(ArcNode*)malloc(sizeof(ArcNode));
		q->nextarc=G->vertices[j].firstarc;
		G->vertices[j].firstarc=q;
		q->adjvex=i;
	}
}
int FirstAdjVex(ALGraph G,int v)
{
	ArcNode *p;
	if(p=G.vertices[v].firstarc)
		return p->adjvex;
	return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{
	ArcNode *p;
	for(p=G.vertices[v].firstarc;p->adjvex!=w;p=p->nextarc);
		if(p=p->nextarc)
			return p->adjvex;
		else
			return -1;
}
void DFS(ALGraph G,int v)
{
	int w;
	visited[v]=TRUE;
	(*VisitFunc)(G,v);
	for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
		if(!visited[w])
			DFS(G,w);
}
void DFSTraverse(ALGraph G,Status (*visit)(ALGraph G,int v))
{
	int i;
	VisitFunc=visit;
	for(i=0;i<G.vexnum;i++)
		visited[i]=FALSE;
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
			DFS(G,i);
}
Status func(ALGraph G,int v)
{
	printf("%s",G.vertices[v].data);
}
int main()
{
	ALGraph G;
	ArcNode *p;
	int i;
	Create(&G);
	printf("建立的邻接表为：\n");
	for(i=0;i<G.vexnum;i++)
	{
		printf("%s ",G.vertices[i].data);
		for(p=G.vertices[i].firstarc;p;p=p->nextarc)
			printf("%s ",G.vertices[p->adjvex].data);
		printf("\n");
	}
	printf("深度优先搜索结果为：\n");
	DFSTraverse(G,func);
	return 0;
}

广度优先搜索BFS

从图中的某个顶点V出发，并在访问此顶点之后依次访问V的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有和V有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

【数据结构】图_最小生成树_31

void BFSTraverse(MGraph G,Status (*Visit)(int v))
{
	int i,u,w;
	LinkQueue Q;
	for(i=0;i<G.vexnum;i++)
		visited[i]=FALSE;
	InitQueue(&Q);//初始化一辅助用的队列
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])//若是未访问过就处理
		{
			visited[i]=TRUE;//设置当前结点访问过
			(*VisitFunc)(G,i);//打印结点
			EnQueue(&Q,i);//将此顶点入队列
			while(!QueueEmpty(Q))//若当前队列不为空
			{
				DeQueue(&Q,&u);//将队中元素出队列，赋值给u
				for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))//判断其他顶点
					if(!visited[w])
					{
						visited[w]=TRUE;
						(*VisitFunc)(G,w);
						EnQueue(&Q,w);
					}
			}
		}
}

深度优先更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"my.h"
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef int VRType;
typedef char InfoType;
typedef int QElemType;
typedef char VertexType [10];
typedef struct QNode{
  QElemType data;
  struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
  QueuePtr front;
  QueuePtr rear;
}LinkQueue;

typedef struct ArcCell
{
	VRType adj;
	InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum,arcnum;
	GraphKind Kind;
}MGraph;
int visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(MGraph G,int v);
Status InitQueue(LinkQueue *Q)
{
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q->front)
		exit(OVERFLOW);
	Q->front->next=NULL;
	return OK;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{
	QueuePtr p;
	p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)
		exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	Q->rear->next=p;
	Q->rear=p;
	return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return ERROR;
	p=Q->front->next;
	*e=p->data;
	Q->front->next=p->next;
	if(Q->rear==p)
		Q->rear=Q->front;
	free(p);
	return OK;
}
Status QueueEmpty(LinkQueue Q)
{
	if(Q.front==Q.rear)
		return TRUE;
	else
		return FALSE;
}
int LocateVex(MGraph G,VertexType v)
{
	int i;
	for(i=0;i<G.arcnum;i++)
		if(!strcmp(G.vexs[i],v))
			return i;
	return -1;
}
Status CreateUDN(MGraph *G)
{
	int i,j,k;
	char v1[20],v2[20];
	printf("请输入顶点和弧的个数：");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	for(i=0;i<G->vexnum;i++)
		scanf("%s",G->vexs[i]);
	for(i=0;i<G->vexnum;i++)
		for(j=0;j<G->vexnum;j++)
		{
			G->arcs[i][j].adj=0;
			G->arcs[i][j].info=NULL;
		 }
		printf("\n请输入边依附的顶点：\n"); 
	for(k=0;k<G->arcnum;k++)
	{
		scanf("%s%s",&v1,&v2);
		i=LocateVex(*G,v1);
		j=LocateVex(*G,v2);
		G->arcs[i][j].adj=G->arcs[j][i].adj=1;
	}
}
int FirstAdjVex(MGraph G,int v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(G.arcs[v][i].adj)
			return i;
	return -1;
}
int NextAdjVex(MGraph G,int v,int w)
{
	int k;
	if(!G.arcs[v][w].adj)
		return -1;
	for(k=w+1;k<G.vexnum;k++)
		if(G.arcs[v][k].adj)
			return k;
	return -1;
}
void BFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v))
{
	int i,u,w;
	LinkQueue Q;
	for(i=0;i<G.vexnum;i++)
		visited[i]=FALSE;
	InitQueue(&Q);
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
		{
			visited[i]=TRUE;
			(*Visit)(G,i);
			EnQueue(&Q,i);
			while(!QueueEmpty(Q))
			{
				DeQueue(&Q,&u);
				for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
					if(!visited[w])
					{
						visited[w]=TRUE;
						(*Visit)(G,w);
						EnQueue(&Q,w);
					}
			}
		}
}
Status func(MGraph G,int v)
{
	printf("%s ",G.vexs[v]);
}
int main()
{
	MGraph G;
	int i,j;
	CreateUDN(&G);
	printf("建立的邻接矩阵为：\n");
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
			printf("%3d",G.arcs[i][j].adj);
		printf("\n");
	}
	printf("广度优先搜索的结果为：\n");
	BFSTraverse(G,func);
	printf("\n");
}

【数据结构】图_邻接矩阵_32

最小生成树

生成树：所有顶点均由边连接在一起，但不存在回路的图。

一个图可以有许多棵不同的生成树。

所有生成树具有以下共同顶点：

生成树的顶点个数与图的顶点个数相同；

生成树是图的极小连通子图，去掉一条边则非连通一个有n个顶点的连通图的生成树有n-1条边。

在生成树中再加一条边必然形成回路。

生成树中任意两个顶点间的路径是唯一的。

含n个顶点n-1条边的图不一定是生成树。

一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。我们把构造连通网的最小代价生成树称为最小的生成树。

最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树，也叫最小代价生成树。

【数据结构】图_深度、广度优先搜索_33

prim算法

一些相关概念

带权图：边赋赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。

生成树和最小生成树的应用：要连通n个城市需要n-1条边线路。可以把边上的权值解释为线路的造价，则最小生成树表示其造价最小的生成树。

连通图：在无向图中，若任意两个顶点vi vi与vj vj都有路径相通，则称该有向图为强连通图。

强连通图：在有向图中，若任意两个顶点vi vi与路径vj vj 都有路径相通，则称该有向图为强连通图。

连通网：在连通图中，若图的边具有一定意义，每一条边都对应着一个数，称为权；权代表着连接两个顶点的代价，称这种连通图叫做连通网。

生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。

最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

prim算法从任意一个顶点开始，每次选择一个与当前顶点集最近的一个顶点，并将两顶点之间的边加入到树中。

prim算法在找当前最近顶点时使用到了贪婪算法，也叫割边法。

【数据结构】图_邻接矩阵_34

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"my.h"
#define MAX_VERTEX_NUM 20
#define INFINITY 65535
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef int VRType;
typedef int InfoType;
typedef char VertexType [10];
typedef struct ArcCell
{
    VRType adj;
    InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
    GraphKind Kind;
}MGraph;

int LocateVex(MGraph G,VertexType v)
{
    int i;
    for(i=0;i<G.arcnum;i++)
        if(!strcmp(G.vexs[i],v))
            return i;
    return -1;
}
Status CreateUDN(MGraph *G)
{
    int i,j,k,w;
    char v1[20],v2[20];
    printf("请输入顶点和弧的个数：");
    scanf("%d%d",&G->vexnum,&G->arcnum);
    for(i=0;i<G->vexnum;i++)
        scanf("%s",G->vexs[i]);
    for(i=0;i<G->vexnum;i++)
        for(j=0;j<G->vexnum;j++)
        {
            G->arcs[i][j].adj=INFINITY;
            G->arcs[i][j].info=0;
         }
        printf("\n请输入边依附的顶点和权值：\n"); 
    for(k=0;k<G->arcnum;k++)
    {
        scanf("%s%s%d",&v1,&v2,&w);
        i=LocateVex(*G,v1);
        j=LocateVex(*G,v2);
        G->arcs[i][j].adj=G->arcs[j][i].adj=w;
    }
}

void MiniSpanTree_Prim(MGraph G)
{
    int min,i,j,k;
    int adjvex[MAX_VERTEX_NUM];//保存相关顶点下标 
    int lowcost[MAX_VERTEX_NUM];//保存相关顶点间边的权值
    lowcost[0]=0;//初始化第一个权值为0，即v0加入生成树
    adjvex[0]=0;//初始化第一个顶点下标为0
    for(i=1;i<=G.vexnum;i++)//循环除下标为0外的全部顶点
    {
        lowcost[i]=int(G.arcs[0][i].adj);//将v0顶点与之有边的权值存入数组
        adjvex[i]=0;//初始化都为v0的下标 
    } 
    for(i=1;i<G.vexnum;i++)
    {
        min=INFINITY;
        j=1;k=0;
        while(j<G.vexnum)//循环全部顶点
        {
            if(lowcost[j]!=0&&lowcost[j]<min)
            {
                min=lowcost[j];
                k=j;
            }
            j++;
        }
        printf("(v%d,v%d)",adjvex[k]+1,k+1);//打印当前顶点边中权值最小边
        lowcost[k]=0;//将当前顶点权值设置为0，表示此顶点已经完成任务
        for(j=1;j<G.vexnum;j++)//循环所有的顶点
        {
            if(lowcost[j]!=0&&int(G.arcs[k][j].adj)<lowcost[j])
            {//若下标为K的顶点各边权值小于此前这些顶点未被加入生成树权值
                lowcost[j]=int(G.arcs[k][j].adj);//将较小权值存入lowcost
                adjvex[j]=k;//将下标为K的顶点存入adjvex 
                
            }
         } 
    }
}
int main()
{
	int i,j;
    MGraph G;
    CreateUDN(&G);
    printf("邻接矩阵为：\n");
    for(i=0;i<G.vexnum;i++)
  	{
    	for(j=0;j<G.vexnum;j++)
      		printf("%d\t",G.arcs[i][j].adj);
    	printf("\n");
  	}
  	printf("最小生成树路径为：");
    MiniSpanTree_Prim(G);
    return 0;
}

【数据结构】图_深度、广度优先搜索_35

克鲁斯卡尔算法

设连通网N=(V,{E})，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{Φ})，每个顶点自成一个连通分量。在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。依此类推，直至T中所有顶点都在同一连通分量上为止。

typedef struct
{
  int begin;
  int end;
  int weight;
}Edge;

【数据结构】图_最小生成树_36

Prim算法适合求边稠密的网的最少生成树，Kruskal算法适合求边稀疏的网的最小生成树。

哪种图的最小生成树是唯一的？

在构造最小生成树的过程中，若候选边集中的边数始终为一条时，其生成树唯一。如所有边的权值不同时即属于这种情况。

最短路径

带权图中从一个结点到另一个结点可能存在多条路径，带权路径长度最短的那条路径称作最短路径。其带权路径长度称作最短路径长度。

某顶点到其他顶点的最短路径—迪杰斯特拉(Dijkstra)算法。

图中任意两顶点间的最短路径—弗洛伊德(Floyd)算法。

迪杰斯特拉算法

问题：给定一个带权有向图G与源点v，求从v到G中其它顶点的最短路径，限定各边上的权值大于或等于0。

为求出这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。

它并不是一下就求出了v0到v8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径。

在所有从源点出发的弧中选取一条权值最小的弧<v,v’>，它即为所求的n-1条最短路径中路径长度最小的一条(按路径长度递增顺序求得的第一条路径)，或者说它一定是v和v’间的最短路径。

弗洛伊德算法

问题：给定一个带权有向图G，求图中任意两顶点间的最短路径，限定各边上的权值大于或等于0

解决方案1：分别以每个顶点为源点施加迪杰特斯拉算法

解决方案2：弗洛伊德算法

1.首先考虑从i到j是否有以顶点1为中间点的路径<i,1,j>，即考虑图中是否有边<i,1>和<1,j>，若有，则新路径<i,1,j>的长度是C[i][1]+C[1][j]，比较路径<i,j>和<i,1,j>的长度，并以较短者为当前所求得的最短路径。该路径是中间点序号不大于1的最短路径。

2.考虑从i到j是否包含顶点2为中间点的路径<i,...,2,...j>，若有，则<i,...,2,...j>可分解成两条路径<i,...,2>和<2,...j> ，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径相加就得到路径<i,...,2,...j>的长度，将该长度与前一次求出的从i到j的中间点序号不大于1的最短路径长度比较，取其较短者作为当前求得的从i到j的中间点序号不大于2的最短路径。

3.再选择顶点3加入当前求得的从i到j中间点序号不大于2的最短路径中，按上述步骤进行比较，从未加入顶点3作中间点的最短路径和加入顶点3作中间点的新路径中选取较小者，作为当前求得的从i到j的中间点序号不大于3的最短路径。

4.依次类推，直到考虑了顶点n加入当前从i到j的最短路径后，选出从i到j的中间点序号不大于n的最短路径为止。由于图中顶点序号不大于n，所以从i到j的中间点序号不大于n的最短路径，已考虑了所有顶点作为中间点的可能性，因而它必是从i到j的最短路径。

标签：typedef,int,MAX,路径,邻接,顶点,数据结构
From： https://blog.51cto.com/heliotopekxy/6373932