高级数据结构02(图)

1.图的遍历

1.1DFS深度遍历(类似二叉树的先序遍历)

思路:
1.为了防止多次访问,设置标志位;由于结点多,所以设置一个数组,将其全部初始化为0,如果访问过该节点,则将对应下标的元素置1
2.找到当前节点的第一条边,如果边存在则说明有邻接点,可以继续往下走
3.找到邻接点后,如果下标为0,则说明未被访问,那就递归访问,直到无邻接点
4.无邻接点则回退,回退后则访问前一个结点的下一条边

#include<stdio.h>
#include<iostream>

#define maxsize 10

using namespace std;
typedef struct ArcNode //边
{
	int adjvex;          //边所指向的结点的位置
	struct ArcNode* next;//指向下一条边的指针
	int info;//
}Edge;
typedef struct VNode
{
	char data;
	ArcNode* firstarc;
};
typedef struct AGraph
{
	VNode adjlist[maxsize];
	int n, e;//顶点数和边数
};

int visit[maxsize]; //0 1 2 3 4 visit[1]=1;  全局数组
//DFS
void DFS(AGraph* G, int v)//起点编号
{
	ArcNode* p;
	visit[v] = 1;
	//	Visit(v);
	p = (G->adjlist[v]).firstarc;
	while (p != NULL)
	{
		if (visit[p->adjvex] == 0)
		{
			DFS(G, p->adjvex);
		}
		p = p->next;
	}
}

1.2BFS广度遍历(类似二叉树的层序遍历)

思路:
1.为了防止多次访问,设置标志位,初始为0,访问置1
2.将第一个结点入队列
3.如果队列不为空则出队,出队的同时将该节点的邻接点入队
入队的具体操作:(先让指针指向该节点的第一条边,如果存在且未被访问,则入队,接着访问下一条边;若被访问过则直接指向该节点下一条边)

/BFS
int visit[maxsize];
void BFS(AGraph* G, int v)
{
	ArcNode* p;
	int que[maxsize], front = 0, rear = 0;
	int j;
	//	Visit(v);
	visit[v] = 1;
	rear = (rear + 1) % maxsize;//入队
	que[rear] = v;
	while (front != rear)
	{
		front = (front + 1) % maxsize;//出队
		j = que[front];

		p = G->adjlist[j].firstarc;
		while (p != NULL)
		{
			if (visit[p->adjvex] == 0)
			{
				//	Visit(p->adjvex);
				visit[p->adjvex] = 1;
				rear = (rear + 1) % maxsize;//邻接点入队
				que[rear] = p->adjvex;
			}
			p = p->next;
		}
	}
}

1.3一点点注解

定义结点结构体时会碰到以下这种形式:
typedef可以掩饰复合类型,如指针和数组。例如不需要像这样定义一个字符数组:

char arr[5];
char brr[5];

每当要用到相同类型和大小的数组是,可以:

typedef char Array[5];
Array arr,brr;

so:

typedef struct VNode
{
	int a;
	struct VNode* next;
}Adjlist[maxsize];
Adjlist A;
//使用Adjlist可以定义一个长度为maxsize的结构体数组,数组中的每个元素都是struct VNode类型

2.最小生成树(Prim)

时间复杂度O(n²),只与顶点有关,因此适合稠密图
思路:
1.设置结点数组以及最小权值数组
2.以v0为起点,记录为权值数组的值
3.将所有节点,在数组里置为0,即未被并入生成树中
4.将起点并入生成树,将初始权值sum置为0,之后每次并入都将权值累加
5.在以v为起点的权值数组里,找最小的权值,将其并入生成树中,并记录其终点结点的位置
6.以终点结点作为起点,更新权值数组
7.循环步骤56,n-1次,n个结点都并入生成树中,结束!

#define INF 10000000
typedef struct VertexType//顶点类型
{
	int no;  //顶点编号
	char info; //顶点其他信息
};
typedef struct MGraph  //邻接矩阵类型
{
	int edges[maxsize][maxsize];//边的权值
	int n, e;//顶点数和边数
	VertexType vex[maxsize];//结点信息
};   

void Prim(MGraph g,int v0,int &sum)
{
	int lowcost[maxsize], vset[maxsize], v;
	//lowcost数组是生成树到剩余各顶点最短边的权值
	//vset数组是记录顶点的访问情况,如果vset[i]=0表示顶点i还未并入生成树
	int i, j, k, min;
	v = v0;
	for (i = 0; i < g.n; ++i)
	{
		lowcost[i] = g.edges[v0][i];//顶点到各点的权值
		vset[i] = 0;//初始化各点未入生成树
	}
	vset[v0] = 1;//顶点并入生成树
	sum = 0;//权值初始值为0
	for (i = 0; i < g.n - 1; ++i)//控制次数,更新n-1次
	{
		min = INF;//INF是一个被定为比图中所有边权值都大的常量
		for (j = 0; j < g.n; ++j)//选出以v0为起点,候选边中的最小值
		{
			if (vset[j] == 0 && lowcost[j] < min)//未被并入且权值小
			{
				min = lowcost[j];//更新min值
				k = j;//记录该结点的序号
			}
		}
		vset[k] = 1;//将上个结点并入,置1
		v = k;//记录结点序号
		sum += min;//权值累加
		for (j = 0; j < g.n; ++j)//
		{
		//以最后一个被并入的结点,为起点更新最小权值
			if (vset[j] == 0 && g.edges[v][j] < lowcost[j])//未被并入且从其出发找到下一个顶点的权值<记录的最小权值
			{
				lowcost[j] = g.edges[v][j];//最小权值更新(同一个终点,更新成最短的值)
			}
		}
	}
}

3.拓扑排序

拓扑排序的一般步骤为:
1.找出入度为0的结点,输出该结点并删除其出度的边
2.重复1

思路:
1.找到第一个入度为0的结点入栈
2.如果栈不为空则出栈,每次出栈计数器+1
3.该节点邻接点的入度需要-1(具体操作为:指针先指向该结点的第一条边,如果存在边则入度-1,[如果减的过程中度为0则入栈,不为0就跳过],指针指向下一条边,入度-1)
4.如果计数器的值等于总结点数,则拓扑排序成功,否则失败返回0

//拓扑排序
typedef struct VNode
{
	char data;
	int count;//当前结点的入度
	ArcNode* firstarc;
};

int TopSort(AGraph* G)
{
	int i, j, n = 0;
	int stack[maxsize], top = -1; //定义并初始化
	ArcNode* p;
	for (i = 0; i < G->n; ++i)
	{
		if (G->adjlist[i].count == 0) //入度为0入栈
		{
			stack[++top] = i;//top=top+1; stack[top]=i;
		}
	}
	while (top != -1)  //栈不为空
	{
		i = stack[top--];   //出栈
		++n;//计数器
		cout << i << " ";
		p = G->adjlist[i].firstarc;
		while (p != NULL) //如果存在边     指向的顶点入度-1
		{
			j = p->adjvex;
			--(G->adjlist[j].count);
			if (G->adjlist[j].count == 0)//度为0就入栈
			{
				stack[++top] = j;
			}
			p = p->next;
		}
	}
	if (n == G->n)//出栈一次 n+1,出栈==总数则成功
	{
		return 1;
	}
	else
	{
		return 0;
	}
} 
上一篇:数据结构学习笔记(C++):邻接矩阵实现图的存储结构


下一篇:2021-10-21