1、图的定义和基本术语

1.1 图的数据类型定义

2、图的存储结构

2.1 邻接矩阵

#define MaxInt 50000			//定义一个极大的数
#define MVNum 100				//定义最大的顶点数	
typedef char VerTexType;		//设顶点的数据类型为字符型
typedef int ArcType;			//设边的权值类型为整数型

typedef struct
{
          
   
	VerTexType vexs[MVNum];		//顶点表
	ArcType arcs[MVNum][MVNum];	//邻接矩阵
	int vexNum, arcNum;			//图当前的节点数量和边数量
}AMGraph;

//创建图
void CreatUDN(AMGraph &G)
{
          
   
	cin >> G.vexNum >> G.arcNum;
	for(int i = 0; i < G.verNum; ++i)
		cin>> G.vex[i];		//依次输入点的信息
	for(int i = 0; i < G.vexNum; ++i)	//初始化邻接矩阵
		for(int j = 0; j < G.vexNum; ++j)
			G.arcs[i][j] = MaxInt;
	//给边赋值
	for(int k = 0; k < G.arcNum; ++k)
	{
          
   
		int v1 = 0, v2 = 0;
		double w = 0;
		cin >> v1 >> v2 >> w;		//输入当前边的顶点和边的权重
		int i = LocateVex(G, v1);	//确定出点v1和v2在图中的位置
		int j = LocateVex(G, v2);
		G.arcs[j][i] = G.arcs[i][j] = w;//无向图是对称的
	}
}

//在图中查找顶点
int LocateVex(AMGraph &G, VertexType u)
{
          
   
	for(int i = 0; i < G.verNum; ++i)
		if(u==G.vers[i]) return i;
	return -1;	
}

2.2 邻接矩阵的优缺点

2.3 邻接表

//顶点的结构
#define MVnum 100	//最大顶点数量
typedef struct VNode
{
          
   
	VerTexType data;	//顶点信息
	ArcNode *firstArc;	//指向第一条依附于该顶点的边的指针
}AdjList[MVnum];		//AdjList表示邻接表类型

//边的节点结构
typedef struct ArcNode
{
          
   
	int adjVex;		//该边指向的顶点的位置
	ArcNode *nextArc;	//指向下一条边的指针
	double info;		//边的权值
};

//图的结构定义
typedef struct ALGraph
{
          
   
	AdjList vertices;	//邻接表中的顶点表
	int vexNum, arcNum;//图中的顶点数和边数
};

//邻接表的构建
void CreateUDG(ALGraph &G)
{
          
   
	cin >> G.vexNum >> G.arcNum;	//输入总的顶点数和总的边数
	for(int i = 0; i < G.vexNum; ++i)
	{
          
   //构建顶点表
		cin >> G.vertices[i].data;
		G.vertices[i].firstArc = nullptr;	//初始化头结点的指针域为空
	}
	for(k= 0; k <G.arcNum; ++k)
	{
          
   //构建边链表
		cin >> v1 >> v2;		//输入一条边依附的两个顶点
		int i = LocateVex(G,v1);
		int j = LocateVex(G,v2);
		ArcNode p1 = new ArcNode;//生成一个新的边结点
		p1->adjVex = j;	//邻接点的序号为j
		p1->nextArc = G.vertices[i].firstArc;//头插法
		G.vertices[i].firstArc = p1;	//将新结点插入到顶点vi的头部
		//构建无向网
		ArcNode p2 = new ArcNode;//生成一个新的边结点
		p2->adjVex = i;	
		p2->nextArc = G.vertices[j].firstArc;//头插法
		G.vertices[j].firstArc = p2;	
	}
}

2.4 邻接表的优缺点

2.5 十字链表和邻接多重表

3、图的遍历

3.1 深度优先搜索-DFS

void DFS(AMGraph &G, int v)
{
          
   
	cout << v << endl;
	visited[v] = true;	//visited为辅助记录节点是否访问的向量
	for(int i = 0; i < G.vexNum; ++i)
	{
          
   
		if(G.arcs[v][i]!=0 && !visited[i])
			DFS(G, i);
	}
}

3.2 广度优先搜索-BFS

void BFS(Graph &G, int v)
{
          
   
	cout << v;
	visited[v]=true;
	queue<int> Q;
	Q.push(v);
	while(!Q.empty())
	{
          
   
		int top = Q.top();
		Q.pop();
		for(int w = FistAdjVex(G,top); w>=0; w=NextAdjVex(G,top,w))
		{
          
   
			if(!visited[w])
			{
          
   
				cout << w<<endl;
				visited[w] = true;
				Q.push(w);
			}
		}
	}
}

4、图的应用

4.1 生成树

THE END