图的基本数据结构及算法汇总

系统管理员 2022-06-09 09:10 280阅读 0赞

#  #

# 图的数据结构常见有5种： #

1.邻接矩阵2.邻接表3.十字链表4.邻接多重表5.边集数组

其中邻接矩阵与邻接表较为常用，可根据所研究图的结构（顶点与边）与算法复杂度进行选择。

# 图的常见问题及算法有下面几种： #

## 1.DFS（邻接矩阵、邻接表） ##

深度优先遍历采用递归思想，逐渐深入，采用visited\[ \]数组记录顶点是否被探索。

邻接矩阵：

#include <iostream>
    using namespace std;
    #define MAXVEX 100
    #define MAXEDGE 100
    
    #include <queue>
    #include <stack>
    
    class Graph
    {
    private:
    	int G[MAXVEX][MAXVEX];
    	int numvex;
    	int numedge;
    	bool visited[MAXVEX];
    public:
    	void DFS(int i);
    	void DFSTraverse();
    	void BFS();
    
    	void Prim();
    
    	void Kruskal();
    	void Find(int *parent, int f);
    
    	void Dijkstra();
    	void Floyd();
    };
    
    void Graph::DFS(int i)
    {
    	visited[i] = true;
    	for (int j = 0; j < numvex; j++)
    	{
    		if (visited[j] == false && G[i][j] == 1)
    			DFS(j);
    	}
    }
    void Graph::DFSTraverse()
    {//初始化visited数组
    	for (int i = 0; i < numvex; i++)
    	{
    		visited[i] = false;
    	}
    
    	for (int i = 0; i < numvex; i++)
    	{//从每个顶点开始深度遍历
    		if (visited[i] == false)
    			DFS(i);
    	}
    }

邻接表：

void Graph::DFS(int i)
    {
    	visited[i] = true;
    	EdgeNode *e = G[i].firstedge;
    
    	while (e)
    	{
    		if (visited[e->adjvex] == false)
    		{
    			DFS(e->adjvex);
    		}
    		e = e->next;
    	}
    }
    void Graph::DFSTraverse()
    {
    	for (int i = 0; i < numvex; i++)
    	{
    		visited[i] = false;
    	}
    
    	for (int i = 0; i < numvex; i++)
    	{
    		if (visited[i] == false)
    			DFS(i);
    	}
    }

## 2.BFS（邻接矩阵、邻接表） ##

广度优先遍历与树结构中的层次遍历相同，逐层递进，采用队列作为辅助结构，并采用visited\[ \]数组记录顶点是否被探索。

邻接矩阵：

void Graph::BFS()
    {
    	for (int i = 0; i < numvex; i++)
    	{
    		visited[i] = false;
    	}
    	queue <int> q;
    
    	for (int i = 0; i < numvex; i++)
    	{//从每个点开始广度遍历
    		if (visited[i] == false)
    		{
    			visited[i] = true;
    			q.push(i);
    
    			while (!q.empty())
    			{//将一个层次的点放入队列
    				int temp = q.front();
    				q.pop();
    
    				for (int j = 0; j < numvex; j++)
    				{//找相邻点
    					if (visited[j] == false && G[temp][j] == 1)
    					{
    						visited[j] = true;
    						q.push(j);
    					}
    				}
    			}
    		}
    	}
    }

邻接表：

void Graph::BFS()
    {
    	for (int i = 0; i < numvex; i++)
    	{
    		visited[i] = true;
    	}
    	queue<int> q;
    	EdgeNode *e;
    	for (int i =0; i < numvex; i++)
    	{
    		if (visited[i] == false)
    		{
    			visited[i] = true;
    			q.push(i);
    			while (!q.empty())
    			{
    				int temp = q.front();
    				q.pop();
    				e = G[temp].firstedge;
    				while (e)
    				{
    					if (visited[e->adjvex] == false)
    					{
    						visited[e->adjvex] = true;
    						q.push(e->adjvex);
    					}
    					e = e->next;
    				}
    			}
    		}
    	}
    }

## 3.Prim（邻接矩阵） ##

采用Prim算法构建最小生成树，算法思路是挑选n - 1条能够覆盖所有顶点，且权值最小的边，因此外层循环以为边循环，内层循环采用遍历点寻找权值最小的点。

void Graph::Prim()
    {
    	int adjvex[MAXVEX];//记录相关顶点
    	int lowcost[MAXVEX];//0代表顶点放入生成树
    
    	for (int i = 0; i < numvex; i++)
    	{
    		adjvex[i] = 0;
    		lowcost[i] = G[0][i];
    	}
    
    	for (int i = 1; i < numvex; i++)
    	{//n - 1条边
    		int min = INF;
    		int k = 0;
    		for (int j = 0; j < numvex; j++)
    		{
    			if (lowcost[j] != 0 && lowcost[j] < min)
    			{
    				min = lowcost[j];
    				k = j;
    			}
    		}
    		lowcost[k] = 0;
    		//k加入生成树，根据k更新lowcost
    		for (int j = 0; j < numvex; j++)
    		{
    			if (lowcost[j] != 0 && G[k][j] < lowcost[j])
    			{
    				lowcost[j] = G[k][j];
    				adjvex[j] = k;
    			}
    		}
    	}
    }

## 4.Kruskal（边集数组） ##

算法前提是将所有边按照权值从小到大排列，从中选取权值最小，且不形成环的边来构成最小生成树。

void Graph::Kruskal()
    {
    	int parent[MAXVEX];
    	Edge e[MAXEDGE];
    
    	for (int i = 0; i < numvex; i++)
    	{
    		parent[i] = 0;//终点全设置为0
    	}
    
    	for (int i = 0; i < numvex; i++)
    	{//确保不成环
    		int n = Find(parent, e[i].begin);
    		int m = Find(parent, e[i].end);
    		if (n != m)
    			parent[n] = m;
    	}
    }
    void Graph::Find(int *parent, int f)
    {
    	while (parent[f] > 0)
    	{
    		f = parent[f];
    	}
    	return f;
    }

## 5.Dijsktra（邻接矩阵） ##

算法思路与Prim算法类似，要在所有顶点中寻找最近的点，并以该点为基础向后求解

void Graph::Dijkstra()
    {
    	int D[MAXVEX];
    	int P[MAXVEX];
    	int final[MAXVEX];
    	
    	for (int i = 0; i < numvex; i++)
    	{
    		D[i] = G[v0][i];
    		P[i] = 0;
    		final[i] = 0;
    	}
    	final[v0] = 1;
    
    	for (int i = 0; i < numvex; i++)
    	{
    		int min = INF;
    		int k = 0;
    		for (int j = 0; j < numvex; j++)
    		{
    			if (final[j] != 1 && D[j] < min)
    			{
    				min = D[j];
    				k = j;
    			}
    		}
    		final[k] = 1;
    
    		for (int j = 0; j < numvex; j++)
    		{//以k为基础更新D数组
    			if (min + G[k][j] < D[j] && final[j] != 1)
    			{
    				D[j] = min + G[k][j];
    				P[j] = k;
    			}
    		}
    	}
    }

## 6.Floyd（邻接矩阵） ##

算法直接采用三重循环，最外层循环为所有顶点，看这些顶点的加入能否使得两点间的距离缩短。

void Graph::Floyd()
    {
    	int P[MAXVEX][MAXVEX];
    	int D[MAXVEX][MAXVEX];
    
    	for (int i = 0; i < numvex; i++)
    	{
    		for (int j = 0; j < numvex; j++)
    		{
    			P[i][j] = j;
    			D[i][j] = G[i][j];
    		}
    	}
    
    	for (int i = 0; i < numvex; i++)
    	{//中间加入顶点
    		for (int j = 0; j < numvex; j++)
    		{
    			for (int k = 0; k <numvex; k++)
    			{
    				if (D[j][k] > D[j][i] + D[i][k])
    				{
    					P[j][k] = P[j][i];
    					D[j][k] = D[j][i] + D[i][k];
    				}
    			}
    		}
    	}
    }

## 7.AOV网拓扑排序（邻接表，顶点表增加入度） ##

通过不断去掉入度为0的顶点输出拓扑序列，同时可用来判断有向图是否有环，采用栈作为辅助结构，将入度为0的结点压栈

bool Graph::Topological()
    {
    	stack<int> s;
    	int count = 0;
    	for (int i = 0; i < numvex; i++)
    	{//将入度为0的结点压栈
    		if (G[i].in == 0)
    			s.push(i);
    	}
    	
    	EdgeNode *e;
    	while (!s.empty())
    	{
    		int temp = s.top();
    		s.pop();
    		count++;
    		e = G[temp].firstedge;
    		while (e)
    		{//如果与入度为0结点相邻的结点在去掉一条边，即入度-1后为0，则压栈
    			if ((--G[e->adjvex].in) == 0)
    				s.push(e->adjvex);
    			e = e->next;
    		}
    	}
    	return count == numvex ? true : false;
    }

## 8.AOE网求解关键路径（邻接表，边表带权值） ##

首先根据AOV网的拓扑排序算法求得事件的最早发生时间etv\[ \]数组，并增加一个栈记录拓扑序列，再反向求解事件发生的最晚事件得到ltv\[ \]数组，在通过上述数组求的活动的最早开始时间ete以及最晚开始时间lte，相等即可判定为关键路径。

void Graph::Topoetv()
    {
    	stack<int> s;
    	stack<int> s_out;
    	int etv[MAXVEX];
    
    	for (int i = 0; i < numvex; i++)
    	{//将入度为0的结点压栈
    		if (G[i].in == 0)
    			s.push(i);
    		etv[i] = 0;
    	}
    	
    	EdgeNode *e;
    	while (!s.empty())
    	{//构造拓扑序列和etv数组
    		int temp = s.top();
    		s.pop();
    		s_out.push(temp);
    		e = G[temp].firstedge;
    		while (e)
    		{//如果与入度为0结点相邻的结点在去掉一条边，即入度-1后为0，则压栈
    			if ((--G[e->adjvex].in) == 0)
    				s.push(e->adjvex);
    			if (etv[temp] + e->weight > etv[e->adjvex])//对于每个顶点取最大的作为最早时间
    				etv[e->adjvex] = etv[temp] + e->weight;
    			e = e->next;
    		}
    	}
    }
    void Graph::TopocriticalPath()
    {
    	int ltv[MAXVEX];
    	EdgeNode *e;
    	for (int i = 0; i < numvex; i++)
    		ltv[i] = etv[numvex - 1];
    
    	while (!s_out.empty())
    	{//构造ltv数组
    		int temp = s_out.top();
    		s_out.pop();
    		e = G[temp].firstedge;
    		while (e)
    		{
    			if (ltv[e->adjvex] - e->weight < ltv[temp])
    			{
    				ltv[temp] = ltv[e->adjvex] - e->weight;
    			}
    			e = e->next;
    		}
    	}
    
    	for (int i = 0; i < numvex; i++)
    	{//比较相同的ete与lte
    		e = G[i].firstedge;
    		while (e)
    		{
    			int ete = etv[i];
    			int lte = ltv[e->adjvex] - e->weight;
    			if (ete = lte)
    				cout<<e->adjvex<<" ";
    			e = e->next;
    		}
    	}
    }

再次自己动手撸了一遍，感觉以后写代码的时候还是要多加注释，想清楚每一步的用处。多注释，自己看的懂，也方便别人看得懂，写起来也会流畅得多。