5.DFS

6.BFS

7.测试程序（待完成）

权与网

连通分量（强连通分量）

1.邻接矩阵的表示

无向图

1.无向图的邻接矩阵是对称的

2.顶点i的度 = 第i行(列)中1的个数

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

有向图

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

2.顶点的出度 = 第i行元素之和，顶点的入度 = 第i列元素之和，顶点的度 = 入度+出度

网（有权图）

2.邻接矩阵的存储

#include <iostream>
#define MaxInt 32767     //表示极大值，即正无穷
#define MVNum 100        //最大顶点数
typedef char VerTeType;   //设顶点的数据类型为字符型
typedef int ArcType;     //假设边的权值类型为整型

typedef struct
{
	VerTexType vexs[MVNum];  //顶点表
	ArcType arcs[MVNum][MVNum];  //邻接矩阵
	int vexnum, arcnum;      //图的当前点数和边数
}AMGraph;//Adjacency Matrix Graph

3.采用邻接矩阵表示法创建无向网


int LocateVex(AMGraph G, VertexType u)
{
	//图G中查找顶点u，存在则返回顶点表中的下标，否则返回-1
	int i;
	for (i = 0; i < G.vexnum; ++i)
		if (u == G.vexs[i])return i;
	return -1;
}
Status CreateUDN(AMGraph& G)
{
	ArcType v1, v2;
	//采用邻接矩阵表示法，创建无向网G
	cin >> G.vexnum > G.arcnum;     //输入总顶点数，总边数
	int i,j,k,w;
	for (i = 0; i < G.vexnum; ++i)  //依次输入点的信息
	{
		cin >> G.vexs[i];
	}
	for (i = 0; i < G.vexnum; ++i)
		for (j = 0; j < G.vexnum; ++j)
			G.arcs[i][j] = MaxInt;      //初始化邻接矩阵，边的权值均置为极大值MaxInt
    
	for (k = 0; k < G.arcnum; ++k)      //构造邻接矩阵
	{
		cin >> v1 >> v2 >> w;           //输入一条边衣服的顶点及其权值
		i = LocateVex{ G,v1 };
		j = LocateVex{ G,v2 };          //确定v1和v2在G中的位置，即顶点数组的下标
		G.arcs[i][j] = w;               //边<v1,v2>的权值置为w
 		G.arcs[j][i] = G.arcs[i][j];    //置<v1,v2>的对称边<v2,v1>的权值为w
	}
	return OK;
}

创建无向图和有向图的区别

优缺点

4.基于邻接矩阵的图上各类操作

声明

#include <iostream>
using namespace std;
#define OVERFLOW -2 //内存溢出错误常量
#define OK 1        //表示操作正确的常量
#define ERROR 0     //表示操作错误的常量
#define TRUE 1      //表示逻辑真的常量
#define FALSE 0     //表示逻辑假的常量

typedef int Status; //指定状态码的类型是int
#define INFINITY 65535
#define MAX_VERTEX_NUM 20

typedef enum
{
	//有向图=0，有向网=1，无向图=2，无向网=3
	DG,
	DN,
	UDG,
	UDN
}GraphKind;

typedef int VRType;
typedef int VertexType;

typedef struct ArcCell
{
	VRType adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum, arcnum;
	GraphKind kind;
}MGraph;

广度优先搜索需要的队列（图的遍历）

#define MAXQSIZE 100; //队列的最大长度
typedef int Status;
typedef int QElemType;

typedef struct//循环队列的C语言描述
{
	QElemType* base; //初始化动态分配存储空间
	int front;       //头指针，若队列不空，指向队头元素
	int rear;        //尾指针，若队列不空，指向队尾元素的下一个位置
}SqQueue;

Status InitQueue_Sq(SqQueue& Q)
{
	if (!(Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType))))
	{
		printf("内存分配失败，程序即将退出!\n");
		exit(OVERFLOW);
	}
	Q.front = Q.rear = 0;
	return OK;
}
Status DestoryQueue_Sq(SqQueue &Q)
{
	if (Q.base)
	{
		free(Q.base);
	}
	Q.base = NULL;
	Q.front = Q.rear = 0;
	return OK;
}
Status QueueEmpty_Sq(SqQueue Q)
{
	if (Q.rear == Q.front)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

Status EnQueue_Sq(SqQueue& Q, QElemType e)
{
	if ((Q.rear + 1) % MAXQSIZE == Q.front)
	{
		return ERROR;
	}
	Q.base[Q.rear] = 0;
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK;
}

Status DeQueue_Sq(SqQueue& Q, QElemType& e)
{
	if (QueueEmpty_Sq(Q))
	{
		return ERROR;
	}
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}

基于邻接矩阵的图上操作

int LocateVex(MGraph G, VertexType u)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.vexs[i] == u)
		{
			return i;
		}
	}
	return -1;
}

Status CreateUDN(MGraph& G)
{
	VertexType v1, v2;
	int w, i, j;
	printf("请输入无向网G的顶点数和弧数\n");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	printf("请依次输入无向网G的顶点名称，用空格隔开\n");
	for (int i = 0; i < G.vexnum; ++i)
	{
		scanf("%d", &G.vexs[i]);
	}
	for (int i = 0; i < G.vexnum; ++i)
		for (int j = 0; j < G.vexnum; ++j)
			G.arcs[i][j].adj = INFINITY;
	printf("请依次输入无向网G每条弧依附的两顶点名称即权值，输完一组按回车\n");
	for (int k = 0; k < G.arcnum; ++k)
	{
		scanf("%d", &v1);
		scanf("%d", &v2);
		scanf("%d", &w);
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j].adj = w;
		G.arcs[j][i] = G.arcs[i][j];
	}
	return OK;
}

Status CreateUDG(MGraph& G)
{
	VertexType v1, v2;
	int i, j;
	printf("请依次输入无向图G的顶点数和弧数\n");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	printf("请依次输入无向图G的顶点名称，用空格隔开\n");
	for (int i = 0; i < G.vexnum; ++i)
	{
		scanf("%d", &G.vexs[i]);
	}
	for (int i = 0; i < G.vexnum; ++i)
		for (int j = 0; j < G.vexnum; ++j)
			G.arcs[i][j].adj = 0;
	printf("请依次输入无向网G每条弧依附的两顶点u名称及权值，输完一组按回车\n");
	for (int k = 0; k < G.arcnum; ++k)
	{
		scanf("%d", &v1);
		scanf("%d", &v2);
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j].adj = 1;
		G.arcs[j][i] = G.arcs[i][j];
	}
	return OK;
}

Status CreateDN(MGraph& G)
{
	VertexType v1, v2;
	int w, i, j;
	printf("请依次输入有向图G的顶点数和弧数\n");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	printf("请依次输入有向图G的顶点名称，用空格隔开\n");
	for (int i = 0; i < G.vexnum; ++i)
	{
		scanf("%d", &G.vexs[i]);
	}
	for (int i = 0; i < G.vexnum; ++i)
		for (int j = 0; j < G.vexnum; ++j)
			G.arcs[i][j].adj = INFINITY;
	printf("请依次输入有向图G每条弧衣服的两顶点名称及权值，输完依次按回车\n");
	for (int k = 0; k < G.arcnum; ++k)
	{
		scanf("%d", &v1);
		scanf("%d", &v2);
		scanf("%d", &w);
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j].adj = w;
	}
	return OK;
}

Status CreateDG(MGraph& G)
{
	VertexType v1, v2;
	int i, j;
	printf("请依次输入有向图G的顶点数和弧数\n");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	printf("请依次输入有向图G的顶点名称，用空格隔开\n");
	for (int i = 0; i < G.vexnum; ++i)
	{
		scanf("%d", &G.vexs[i]);
	}
	for (int i = 0; i < G.arcnum; ++i)
		for (int j = 0; j < G.arcnum; ++j)
			G.arcs[i][j].adj = 0;
	printf("请依次输入有向图G每条弧的两顶点名称，输完一组按回车\n");
	for (int k = 0; k < G.arcnum; ++k)
	{
		scanf("%d", &v1);
		scanf("%d", &v2);
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j].adj = 1;
	}
	return OK;
}

Statuss CreateGraph(MGraph& G)
{
	printf("请输入要构造的图的类型：有向图输入0，有向网输入1，无向图输入2，无向网输入3):");
	scanf("%d", &G.kind);
	switch (G.kind)
	{
	case DG:
		return CreateDG(G);//构造有向图G
	case DN:
		return CreateDN(G);//构造有向网G
	case UDG:
		return CreateUDG(G);//构造无向图G
	case UDN:
		return CreateUDN(G);//构造无向网G
	default:
		return ERROR;
	}
}


Status DestroyGraph(MGraph& G)
{
	if(G.king % 2)
		for(int i = 0;i<G.vexnum;i++)
			for (int j = 0; j < G.vexnum; j++)
			{
				G.arcs[i][j].adj = INFINITY;
			}
	else
	{
		//若是图
		for (int i = 0; i < G.vexnum; i++)
		{
			for (int j = 0; j < G.vexnum; j++)
				G.arcs[i][j].adj = 0;
		}
	}
	G.vexnum = 0;
	G.arcnum = 0;
}

Status PrintAdjMatrix(MGraph G)
{
	printf("        ");
	for (int i = 0; i < G.vexnum; i++)
	{
		printf(" %3d", G.vexs[i]);
	}
	printf("\n");
	printf("      +");
	for (int i = 0; i < G.vexnum; i++)
	{
		printf("-----");
	}
	printf("\n");
	for (int i = 0; i < G.vexnum; i++)
	{
		printf(" %3d |", G.vexs[i]);
		for (int j = 0; j < G.vexnum; j++)
		{
			if (G.arcs[i][j].adj == INFINITY)
				printf("  ∞ ");
			else
				printf(" %3d", G.arcs[i][j].adj);
		}
		printf("\n        |\n");
	}
}

//返回V的值
VertexType& GetVex(MGraph G, int v)
{
	if (v >= G.vexnum || v < 0)
		exit(ERROR);
	return G.vexs[v];
}

//对V赋值value
Status PutVex(MGraph& G, VertexType v, VertexType value)
{
	int k = LocateVex(G, v);
	if (k < 0)
	{
		return ERROR;
	}
	G.vexs[k] = value;
	return OK;
}

//返回v的第一个邻接顶点，若v在G中没有邻接顶点，则返回空
int FirstAdjVex(MGraph G, VertexType v)
{
	int kv, j;
	VRType adj;
	kv = LocateVeX(G, v);
	if (kv == -1)
		return -1;
	if (G.kind == DG || G.kind == UDG)
	{
		adj = 0;  //图
	}
	else if (G.kind == DN || G.kind == UDN)
	{
		adj = INFINITY;  //网
	}
	else
	{
		return -1;
	}
	for (j = 0; j < G.vexnum; j++)
	{
		if (G.arcs[kv][i].adj != adj)
		{
			return j;
		}
	}
	return -1;
}

//返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回空
int NextAdjVex(MGraph G, VertexType v, VertexType w)
{
	int kv, kw, j;
	VRType adj;
	kv = LocateVex(G, v);
	if (kv == -1)
		return -1;
	kw = LoateVex(G, w);
	if (kw == -1)
	{
		return -1;
	}
	if (G.kind == DG || G.kind == UDG)
	{
		adj = 0;    //图
	}
	else if (G.kind == DN || G.kind == UDN)
	{
		adj = INFINITY; //网
	}
	else
	{
		return -1;
	}
	for (j = k2 + 1; j < G.vexnum; j++)
	{
		if (G.arcs[kv][j].adj != adj)
		{
			return j;
		}
	}
	return -1;
}

//在图G中增加新顶点v
Stauts InsertVEX(MGraph& G, VertexType v)
{
	int j = 0;
	if (G.kind % 2)
	{
		j = INFINITY;
	}
	G.vexs[G.vexnum] = v;
	for (int i = 0; j <= G.vexnum; i++)
	{
		G.arcs[G.vexnum][i].adj = G.arcs[i][G.vexnum].adj = j;
	}
	G.vexnum++;
	return OK;
}

//删除G中顶点V及其相关弧
Status DeleteVex(MGraph& G, VertexType v)
{
	VRType m = 0;
	if (G.kind % 2)
		m = INFINITY;
	int k = LocateVex(G, v);
	if (k < 0)
		return ERROR;
	for (int j = 0; j < G.vexnum; j++)
	{
		if (G.arcs[j][k].adj != m)
		{
			G.arcs[j][k].adj = m;
			G.arcnum--;
		}
		if (G.arcs[k][j].adj != m)
		{
			G.arcs[k][j].adj = m;
			G.arcnum--;
		}
	}
	for (int j = k + 1; j < G.vexnum; j++)
	{
		G.vexs[j - 1] = G.vexs[j];
	}
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = k + 1; j < G.vexnum; j++)
			G.arcs[i][j - 1] = G.arcs[i][j];
	}
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = k + 1; j < G.vexnum; j++)
			G.arcs[j - 1][i] = G.arcs[j][i];
	}
	G.vexnum--;
	return OK;
}

//在G中增添弧<v,w>，若G是无向图，则还增添对称弧<w,v>
Status InsertArc(MGraph& G, VertexType v, VerType w)
{
	int v1 = LocateVex(G, v);
	int w1 = LocateVex(G, w);
	if (v1 < 0 || w1 < 0)
	{
		return ERROR;
	}
	G.arcnum++;
	if (G.kind % 2)
	{
		printf("请输入此弧或边的权值：");
		scanf("%d", &G.arcs[v1][w1].adj);
	}
	else
		G.arcs[v1][w1].adj = 1;
	if (G.kind > 1)
		G.arcs[w1][v1].adj = G.arcs[v1][w1].adj;
	return OK;
}

//在G中删除弧<v,w>，若G是无向图，则还删除对称弧<w,v>
Status DeleteArc(MGraph& G, VertexType v, VertexType w)
{
	int j = 0;
	if (G.kind % 2)
	{
		j = INFINITY;
	}
	int v1 = LocateVex(G, v);
	int w1 = LocateVeX(G, W);
	if (v1 < 0 || w1 < 0)
		return ERROR;
	G.arcs[V1][W1].adj = j;
	if (G.kind >= 2)
		G.arcs[w1][v1].adj = j;
	G.arcnum--1;
	return OK;
}

5.DFS

深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次

//深度优先遍历
int visited[MAX_VERTEX_NUM];
Status(*VisitFunc)(int v);
Status Print(int v)
{
	printf(" %3d ", v);
	return OK;
}

void DFS(MGraph, int v)
{
	visited[v] = TRUE;
	VisitFunc(G.vexs[v]);
	for (int w = FirstAdjVex(G, G.vexs[v]); w >= 0; W = NextAdjVex(G, G.vex[v], G.vex[w]))
	{
		if (!visited[w])
		{
			DFS(G, w);
		}
	}
}

void DFSTraverse(MGraph G, Status(*Visit)(int v))
{
	VisitFunc = Visit;
	for(int v = 0; v < G.vexnum; ++v)
		visited[v] = FALSE;
	for (int v = 0; v < G.vexnum; ++v)
		if (!visited[v)
			DFS(G, v);
}

6.BFS

广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

void BFSTraverse(MGraph G, Status(*Visit)(int v))
{
	int u;
	SqQueue Q;
	for (int v = 0; v < G.vexnum; ++v)
	{
		visited[v] = FALSE;
	}
	InitQueue_Sq(Q);
	for (int v = 0; v < G.vexnum; ++v)
	{
		if (visited[v])
			continue;
		visited[v] = TRUE;
		Visit(G.vexx[v]);
		EnQueue_Sq(Q, v);
		while (!QueueEmpty_Sq(Q))
		{
			DeQueue_Sq(Q, u);
			for (int w = FirstAjVex(G, G.vexs[u]); w >= 0;
				w = NextAdjVex(G, G.vexs[u), G, vexs[w]))
				if (!visited[w])
				{
					visited[w] = TRUE;
					Visit(G.vexs[w]);
					EnQueue_Sq(Q.w);
				}
		}
	}
}

7.测试程序（待完成）

原文链接：https://blog.csdn.net/m0_61548909/article/details/125131792

1.邻接矩阵的表示

2.邻接矩阵的存储

3.采用邻接矩阵表示法创建无向网

4.基于邻接矩阵的图上各类操作

5.DFS

6.BFS

7.测试程序（待完成）

你可能也喜欢