本文主要是介绍PKU 数据结构与算法笔记——图，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

图

图的基本概念

用 G = ( V , E ) G=(V,E) G=(V,E)代表一个图，V表示有限顶点的集合，E表示边的集合，是顶点的偶对，|v|表示顶点的总数，|E|表示边的总数

分类

• 稀疏图-边相对较少的图
• 密集图-边数相对较多的图
• 完全图-包括所有可能边的图
• 无向图-顶点偶对无序的图
• 有向图-顶点偶对有序的图
• 标号图-各顶点均带有标号的图
• 带权图-边上标有权的图

相关概念

• 邻接点-一条边所连接的两个顶点

• 顶点的度-与该顶点相关联的边的数目

  ​ 对于有向图

  • 入度：以该顶点为终点的边的数目
  • 出度：以该顶点为起点的边的数目
  • 终端结点(叶子)：出度为0的顶点

• 子图- G = ( V , E ) , G ′ = ( V ′ , E ′ ) , 若 V ′ ⊆ V , E ′ ⊆ E , G ′ 是 G 的 子 图 G=(V,E),G^{'}=(V^{'},E^{'}),若V^{'}\subseteq V,E^{'}\subseteq E,G^{'}是G的子图 G=(V,E),G′=(V′,E′),若V′⊆V,E′⊆E,G′是G的子图

• 路径-从一个顶点出发能到达一个结点的边的集合

• 回环-路径上某个顶点与自身连接

图的连通性

• 有根图

  一个有向图中，存在一个顶点，能从它出发到达其他所有顶点，称此图为有根图，该结点称为图的根

• 连通图

  对于无向图，若任意两个顶点之间都有边，则该图是连通的

• 联通分量

  无向图的最大连通子图

• 强连通图

  对于有向图，任意两个顶点之间都有不同方向的两条边相连，则称该图为强连通图

• 强连通分量

  有向图的最大强连通子图

图的抽象数据类型

边的基类

Class Edge//边的基类
{   				
Public:
	int from, to, weight;
	Edge()//构造函数
    {    				
		from=-1; to=-1; weight=0;
	}
	Edge(int f, int t, int w)//构造函数
    {		
		from=f; to=t; weight=w;
	}
	bool operator > (Edge oneEdge)//定义边比较运算符 “>”
    {    	
		return  weight>oneEdge.weight;
	}
	bool operator < (Edge oneEdge)//定义边比较运算符 “<”
    {    	
		return  weight<oneEdge.weight;
	}
};

图的基类

Class Graph//图的基类
{			
Public:
	int numVertex,  numEdge;//图的顶点和边的数目
	int *Mark, *indegree;//保持顶点是否被访问过和顶点入度的数组
	
	Graph(int numVert)//构造函数
    {  	                                           
		numVertex= numVert;
		numEdge=0;
		indegree = new int[numVertex];//初始化顶点入度数组；
		Mark = new int[numVertex]; //初始化顶点是否被访问的标志数组；
		for (int i=0; i<numVertex;i++)
		{  	
			Mark[i]= UNVISITED;
			Indegree[i]=0;
		}
	}
	～Graph()//析构函数
    {  			
		delete[] mark;
		delete[] indegree;
	}
	virtual Edge FirstEdge (int oneVertex)=0;//返回顶点的第一条边；
	virtual Edge NextEdge (Edge preVertex)=0;//返回当前边的下一条边；
	int verticesNum() {return  numVertex};//返回顶点数；
	int EdgesNum() {return  numEdge}; //返回边数；
	bool isEdge(Edge  oneEdge)//判断oneEdge是否为边；
    {	
		if (oneEdge.weight>0 && oneEdge.weight<INFINITY && oneEdge.to>=0)     				return true;
		else  return false;
	}
	int FromVertex(Edge oneEdge)//返回边oneEdge的始点
	     {return oneEdge.from;} 		
	int ToVertex(Edge oneEdge)//返回边oneEdge的终点
	     {return oneEdge.to;} 	
	int Weight(Edge oneEdge)//返回边oneEdge的权
	     {return oneEdge.weight;}
	virtual void setEdge(int from, int to, int weight)=0;//设置边
	virtual void delEdge(int from, int to)=0;//删除边
};

图的存储结构

邻接矩阵

对于矩阵A,若顶点i，j相邻(有边相连)，则A[i][j]=1，空间复杂度为O(n²),与边数无关

• 对于无向图的邻接矩阵

  矩阵对称

  第i行或第i列中1的个数为顶点i的度

  矩阵中1的个数的一半为图中边的数目

  容易判断顶点i和顶点j之间是否有边相连

• 对于有向图的邻接矩阵

  矩阵不一定对称

  第i行中1的个数为顶点i的出度

  第i列中1的个数为顶点i的入度

  矩阵中1的个数为图的边数

  容易判断i和j之间是否有边相连

邻接矩阵的类表示

Class Graphm: public Graph
{
private:
	int ** matrix;
Public:
	Graphm(int numVert) : Graph(numVert)//构造函数 
    {  	
		int i, j;
		matrix = (int **) new int* [numVertex];//声明一个相邻矩阵；
		for (int i=0; i<numVertex; i++)//构造一个相邻矩阵；
		      matrix[i]= new int[numVertex];
		for (int i=0; i<numVertex; i++)//初始化相邻矩阵；
		      for (int j=0; j<numVertex; j++)
			matrix[i][j]=0;
	}
	～Graph()//析构函数
    {
		for (int i=0; i<numVertex; i++) 			
		       delete[] matrix[i];
		delete[] matrix;
	}
	Edge FirstEdge(int oneVertex)//返回顶点oneVertex的第一条边；
    {
		Edge  myEdge;
		myEdge.from = oneVertex;  
        myEdge.to = -1;
		for (int i=0; i<numVertex; i++) 
        {
		        if (matrix[oneVertex][i]!=0)
                {
					myEdge.to=i;
                    myEdge.weight = matrix[oneVertex][i];
					break;
		        }
		}
		return myEdge;
	}
	Edge NextEdge(Edge preEdge)//返回与边preEdge有相同顶点的下一条边
    {
		Edge  myEdge;
		myEdge.from = preEdge.from; 
		myEdge.to = -1;//-1可以判断是非边
		for (int i=preEdge.to+1; i<numVertex; i++)
        {
		        if (matrix[preEdge.from][i]!=0)
                {
                    myEdge.to=i;	
                    myEdge.weight = matrix[oneVertex][i];
                    break;
		        }
		}
		return myEdge;
	}
	void setEdge(int from, int to, int weight)//为图设定一条边；
    {
		if (matrix[from][to]<=0)
        {
			numEdge++;	
			indegree[to]++;
	    }
		matrix[from][to]=weight;
	}
	void delEdge(int from, int to)//删掉图的一条边；
    {
		if (matrix[from][to]>0)
        {
			numEdge--;	
			indegree[to]--;
	    }
		matrix[from][to]=0;//0可以判断是非边
	}

邻接表

顶点表：对应n各顶点，包括顶点数据和指向边表的指针

边链表：对应m条边，包括顶点序号和指向边表下一条边的指针

无向图：需要|V|+2|E|个存储单元

有向图：保存出边表和入边表之一即可，需要|V|+|E|个存储单元

基于邻接表的类表示

Struct listUnit//邻接表表目中数据部分的结构定义
{
	int vertex;//边的终点；
	int weight;//边的权；
};
Template <class Elem>//链表元素
class link
{
public:
	Elem  element;//顶点元素；
	link *next;//指针元素；
	link (const Elem& elemval, Link *nextval=NULL)//构造函数
    {
		element  = elemval;//初始化顶点值；
		next = nextval;//初始化指针值；
	}
	link (link  * nextval = NULL) {next = nextval;}//构造函数
};
template <class Elem>//链表
class LList
{
public:
	Link <Elem> *head;//定义头指针head，只为操作方便
	LList()//构造函数；
    {
		head = new Link<Elem>();
	}
	void removeall()//释放边表所有表目占据的空间；
    {
		Link<Elem> * fence;
		while(head!=NULL)
        {
			fence =head;  
            head=head->next; delete fence;
		}
	}
	~LList(){removeall();}//析构函数
};
class Graphl：public Graph
{
private:
	LList <listunit>  * graList;//保存所有边表的数组；
public:
	Graphl(int numVert):Graph(numVert)//构造函数
    {
		graList =  new LList <listUnit>[numVertex]；
	}
	～Graphl()//析构函数
    {
		delete[] graList;
	}
	Edge firstEdge(int oneVertex)//返回顶点oneVertex的第一条边
	{
		Edge myEdge;
		myEdge.from = oneVertex;
		myEdge.to = -1;
		Link<listUnit> *temp = graList[oneVertex].head;//取对应链表的头
		if (temp->next != NULL)
		{
			myEdge.to = temp->next->element.vertex;
			myEdge.weight = temp->next->element.weight;
		}
		return  MyEdge;
	}
    Edge nextEdge(Edge preVertex)//返回与preEdge有相同顶点的下一条边
    {
        Edge myEdge;
        myEdge.from = preEdge.from;
        myEdge.to = -1;
        Link<listUnit> *temp = graList[preEdge.from].head;
        while (temp->next != NULL && temp->next->element.vertex<=preEdge.to)
            temp=temp->next;
        if (temp->next!=NULL)
        {
            myEdge.to = temp->next->element.vertex;
            myEdge.weight = temp->next->element.weight; 
            return  MyEdge;
		}
	}
	Void setEdge(int from, int to, int weight)//为图设定一条边；
    {
        Link <listUnit> * temp = graList[from].head;
        while (temp->next!=NULL && temp->next->element.vertex<to)
            temp=temp->next;//确定要插入边表的位置
        if (temp->next==NULL)//为空，在尾部插上这条边
        {
            temp->next=new Link<listUnit>;
            temp->next->element.vertex = to;
            temp->next->element.weight = weight;
            numEdge++;
            indegree[to]++;
            return;
		}
        if (temp->next->element.vertex == to)//边已经在图中存在，只改权值；
        {
            temp->next->element.weight = weight;
            return;
        }
        if (temp->next->element.vertex > to)//不存在，在边表中插入该条边；
        {
            Link <listUnit> * other = temp->next;
            temp->next=new Link<listUnit>;
            temp->next->element.vertex = to;
            temp->next->element.weight = weight;
            temp->next->next = other;
            numEdge++;
            indegree[to]++;
            return;
        }
    }
	Void delEdge(int from, int to)//删除图的一条边；
    {
	  Link <listUnit> * temp = graList[from].head;
	  while (temp->next!=NULL && temp->next->element.vertex<to)
		temp=temp->next;//确定要插入边表的位置
	  if (temp->next==NULL)//边在图中不存在；
		return;
	  if (temp->next->element.vertex > to)//边在图中不存在；
		return;
	  if (temp->next->element.vertex == to)//边在图中存在；
      {
		Link <listUnit> * other = temp->next->next;
		delete temp->next;
		temp->next = other;
		numEdge--;
		indegree[to]--;
		return;
	 }
   }
}

十字链表

另一种链式存储结构，是邻接表和逆邻接表的结合

• 顶点表：对应图的顶点，由3部分组成
  • data域
  • firstinarc指针指向第一条以该顶点为终点的边
  • firstoutarc指针指向第一条以该顶点为起点的边
• 边链表：对应于有向图的每一条边，一共5个域
  • 起点(fromvex)和终点(tovex)的顶点序号
  • 边的权值info域
  • fromnextarc指针指向下一个以fromvex为起点的边
  • tonextarc指针指向下一个以tovex为终点的边

图的周游

从一个顶点出发系统的访问图中所有顶点，每个顶点访问一次，一般每个顶点保留一个标志位，初始时标志位为未访问，当结点被访问则标志位记为以访问

void graph_traverse(Graph& G)//图的周游算法的实现
{
     for(int i=0;i<G.VerticesNum();i++)  //初始化标志位
         G.Mark[i]=UNVISITED;
     for(int i=0;i<G.VerticesNum();i++) 	
         if(G.Mark[i]== UNVISITED)
 			do_traverse(G, i); //do_traverse函数
} 

主要由深度优先和广度优先两种方式

深度优先搜索

void DFS(Graph& G, int V)
{
	Visit(G, V);//访问V
	G.Mark[V]= VISITED;//访问顶点V，并标记其标志位
    for(Edge e=G. FirstEdge(V); G.IsEdge(e); e=G. NextEdge(e))//递归地按照深度优先的方式访问V邻接的未被访问的顶点          	
    	if(G.Mark[G. ToVertices(e)]== UNVISITED)
      		DFS(G, G. ToVertices(e));   
}

对于每条边处理一次(无向图为两次),每个顶点访问一次

采用邻接表表示时，访问有向图的时间复杂度为O(|V|+|E|),无向图为O(|V|+2|E|)

采用邻接矩阵表示时时间复杂度为O(|V|²)

DFS检查是否有环

Stack <int> A; 
Set<int> S; 
void DFS(Graph& G, int V)
{      
    A.push(V); 
    S.insert(V);       
	Visit(G, V);//访问V
	G.Mark[V]= VISITED;//访问顶点V，并标记其标志位
     for(Edge e=G. FirstEdge(V); G.IsEdge(e); e=G. NextEdge(e))//递归地按照深度优先的方式访问V邻接的未被访问的顶点          	
        if(G.Mark[G.ToVertices(e)]== UNVISITED)
      		DFS(G,G.ToVertices(e));   
        else if(S.count(ToVertices(e))>0)//在一条路径上访问到V两次则有环
            cout<<"report a circle";
 		int x=A.top();
 	   	A.pop();
 		S.erase(x);
}

广度优先搜索

先访问一个顶点，再依次访问该顶点的邻居，再访问该顶点邻居的邻居，以此类推直到遍历所有的顶点

void BFS(Graph& G, int V)
{
	using std::queue;//初始化广度优先周游要用到的队列
	queue<int> Q; 
	G.Mark[V]= VISITED;//访问顶点V，并标记其标志位， V入队
    Visit(G, V);
    Q.push(V); 
	while(!Q.empty()//如果队列仍然有元素
    {
   		int V=Q.front();
        Q.pop(); //取顶部元素，并出队
		//将与该点相邻的每一个未访问点都入队
		for(Edge e=G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e))
        {
      		if(G.Mark[G.ToVertex(e)]== UNVISITED)
            {
                G.Mark[G.ToVertex(e)]=VISITED;
                Visit(G, G.ToVertex(e));
                Q.push(G.ToVertex(e)); //入队
         	}	
		}
 	}
} 

广度优先搜索实质于深度优先相同，只是访问顺序不同，二者的时间复杂度也相同

拓扑排序

将一个有向无环图中所有顶点排成一个序列，使得图中任意一对顶点u和v，若<u,v>是一条边，则线性序列中u在v之前

• 将图中所有顶点按照拓扑次序排成一行，则图中所有的有向边均是从左指向右的
• 拓扑序列不唯一
• 环存在时不存在拓扑序列

拓扑排序方法

• 从图中选择一入度为0的顶点并输出
• 从图中删掉此顶点及其所有的出边，出边关联顶点的入度减1
• 回到第一步

环路存在时

• 排序结束仍有顶点未被输出
• 剩下的图中找不到入度为0的顶点

拓扑排序算法

基于邻接矩阵的拓扑排序

• 入度为0的顶点对应的列全为0
• 删除某个顶点的出边就是把邻接矩阵中对应的行清0

基于邻接表的拓扑排序

BFS算法

void TopsortbyQueue(Graph& G)//队列方式实现的拓扑排序
{
	for(int i=0;i<G.VerticesNum();i++)
		G.Mark[i]=UNVISITED;//初始化标记数组
   	using std::queue;
   	queue<int> Q;//初始化队列
	for(i=0; i<G.VerticesNum(); i++)//图中入度为0的顶点入队
    {
	      if(G.Indegree[i]==0)            
		     Q.enqueue(i);            			     
     }
	while(!Q.empty())//如果队列中还有图的顶点
    {
 		V=Q.dequeue();//一个顶点出队
    	Visit(G, V);//访问该顶点
    	G.Mark[V]=VISITED;//边e的终点的入度值减1		
        for(Edge e= G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e))  
        {
        	G.Indegree[G.ToVertex(e)]--;   
            if(G.Indegree[G.ToVertex(e)]==0) 
           		Q.enqueue(G.ToVertex(e));//入度为0的顶点入队
        }
    }
	for(i=0; i<G.VerticesNum(); i++)
    { 
        if(G.Mark[i]==UNVISITED)
        {            
            Print("图有环");//图有环
            break;
        }
    }            
}

BFS可以判定有环存在

• 采用邻接矩阵时，找所有入度为0的点需要O(|V|²)的时间,对于|V|个顶点而言,总代价为O(|V|³)
• 采用邻接表时，找入度为0的点只需要O(|V|)的时间，加上处理边、顶点的时间，总时间复杂度为O(2|V|+|E|)

DFS算法

void TopsortbyDFS(Graph& G)//深度优先拓扑排序,结果逆序
{
	for(int i=0; i<G.VerticesNum(); i++)//初始化标志位
		G.Mark[i]=UNVISITED;
	int *result=new int[G.VerticesNum()];//最终输出的逆序结果
	int tag=0;
	for(i=0; i<G.VerticesNum(); i++)//对图的所有顶点进行处理
		if(G.Mark[i]== UNVISITED)
		        Do_topsort(G,i,result,tag);//调用递归函数
	for(i=G.VerticesNum()-1;i>=0;i--)//逆序输出
	        Visit(G, result[i]);
}
//深度优先搜索实现的拓扑排序
void Do_topsort(Graph& G, int V, int *result, int& tag)
{
	G.Mark[V]= VISITED; 
	//访问V邻接到的所有未被访问过的顶点
	for(Edge e= G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e))     
		if(G.Mark[G.ToVertex(e)]== UNVISITED)
			Do_topsort(G, G.ToVertex(e), result, tag); //递归调用
		result[tag++]=V;
}

DFS不能判断环的存在

最短路径问题

求两个顶点间长度最短的路径，其中长度一般指路径上各边的权值的和

单源最短路径

对于一个图，给定源点s，求出s到图中其它各顶点的最短路径

Dijkstra算法

适用于边权非负的情况，每次从距离已生成最短路径的结点集一步之遥的结点中选择距离源点s最近的边进行延伸

过程

• 初始化

  已知集只包括源点s，其它结点都是未知集，s距离值为0，若s和V右边，则V的距离为该边的权值，否则为正无穷

• 添加

  每次从未知集中选一个距离值最小的点加入到已知集中，每次加入后要对未知集中的顶点的距离值进行一次更新，若加入V做中间顶点比不加入V的距离小，则需要更新距离值

• 重复上述过程，直到未知集为空

算法

class Dist// Dist类，Dijkstra和Floyd算法用于保存最短路径信息
{
public:
    int index;// 顶点的索引值，仅Dijkstra算法用到
	int length;// 当前最短路径长度
	int pre;// 路径最后经过的顶点
};
void Dijkstra(Graph& G,int s, Dist* &D)
{
      D=new Dist[G.VerticesNum()];   	
	 for(int i=0;i<G.VerticesNum();i++)//初始化Mark数组、D数组
     {
      	G.Mark[i]=UNVISITED;
      	D[i].length= INFINITY;
		D[i].index=i;//顶点的索引值；
      	D[i].pre=s;//路径最后经过的顶点
    }
 	D[s].length=0;//源点为s；
	MinHeap<Dist> H(G.EdgesNum());//声明一个最小值堆；
	H.Insert(D[s]);//以源点s初始化堆；
	for(i=0;i<G.VerticesNum();i++)
    {
		Bool FOUND = false;
		Dist d;
		while(! H.empty())
        {
			d = H.RemoveMin();
	       	if( G.Mark[d.index]==UNVISITED)
           	{
			   	FOUND = true;//把该点加入已访问组;
               	break;
           	}
		}
		if (!FOUND)   
            break;
   		int v = d.index;
        G.Mark[v] = VISITED;
        Visit(v);//打印输出;
  	    for(Edge e=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e))
        {
	    	if(D[G.ToVertex(e)].length>(D[v].length + G.Weight(e)))
            {        
            	D[G.ToVertex(e)].length=D[v].length + G.Weight(e);
                D[G.ToVertex(e)].pre=v;
			    H.insert(D[G.ToVertex(e)]);//入堆；
            }
        }
    }
}

时间复杂度分析

如果不采用最小堆的方式，每次寻找权值最小的结点需要进行|V|次扫描，每次扫描|V|个顶点，时间复杂度为O(|V|²)

如果采用最小堆，时间复杂度为O((|V|+|E|log|E|))

每对顶点间的最短路径

对图中任意两个顶点，找到它们的最短路径

Floyd算法

过程

• 假设用邻接矩阵表示，其中任意两点的距离是边的权，如果没有边直接相连，则全为无穷大

• 在原图的邻接矩阵adj⁽⁰⁾上做n次迭代，递归的产生一个矩阵序列adj⁽¹⁾，adj⁽²⁾，……，adj⁽ⁿ⁾

  • 其中adj^(k)[i][j]等于从顶点i到顶点j中间顶点序号不大于k的最短路径长度

• adj⁽ⁿ⁾包括了所有最终的最短路径长度

递推公式

假设已经求得adj^(k-1)，那么从顶点i到j中间顶点的序号不大于k的最短路径右两种情况

• 中间顶点不经过顶点k：那么就有 a d j ( k ) [ i ] [ j ] = a d j ( k − 1 ) [ i ] [ j ] adj^{(k)}[i][j]=adj^{(k-1)}[i][j] adj(k)[i][j]=adj(k−1)[i][j]
• 中间顶点经过顶点k：那么 a d j ( k ) [ i ] [ j ] < a d j ( k − 1 ) [ i ] [ j ] , a d j ( k ) [ i ] [ j ] = a d j ( k − 1 ) [ i ] [ k ] + a d j ( k − 1 ) [ k ] [ j ] adj^{(k)}[i][j]<adj^{(k-1)}[i][j],adj^{(k)}[i][j]=adj^{(k-1)}[i][k]+adj^{(k-1)}[k][j] adj(k)[i][j]<adj(k−1)[i][j],adj(k)[i][j]=adj(k−1)[i][k]+adj(k−1)[k][j]

确定最短路径

设置一个nxn的矩阵path，path[i][j]是由顶点i到顶点j的最短路径上排在顶点j前面的那个顶点，即当k使得adj^(k)[i][j]达到最小值，那么使path[i][j]=path[k][j]

当前没有最短路径时，就令path[i][j]=-1

算法

void Floyd(Graph& G, Dist** &D)
{ 
	int i,j,v;//i, j, v作为计数器
    D=new Dist*[G.VerticesNum()];    
    for(i=0; ;i<G.VerticesNum();i++)//申请数据D的空间
        D[i]=new Dist[G.VerticesNum()];
	for(i=0;i<G.VerticesNum();i++)//初始化D数组
		for(j=0;j<G.VerticesNum();j++)
            if(i==j)
            {
                D[i][j].length=0;//权值矩阵
                D[i][j].pre=i;//path矩阵              
            }else
            {
                D[i][j]=INFINITY;
                D[i][j].pre=-1;
            } 
    for(v=0;v<G.VerticesNum();v++)//矩阵初始化，仅初始化邻接顶点
        for(Edge e=G.FirstEdge(v); G.IsEdge(e); e=G.NextEdge(e))
        {	
            D[v][G.ToVertex(e)].length=G.Weight(e);
            D[v][G.ToVertex(e)].pre=v;
        }
    //如果两顶点间最短路径经过顶点v，则有权值进行更新！
    for(v=0;v<G.VerticesNum();v++)
        for(i=0;i<G.VerticesNum();i++)
            for(j=0;j<G.VerticesNum();j++)
                if((D[i][v].length +D[v][j].length) < D[i][j].length)
                {
                    D[i][j].length =D[i][v].length +D[v][j].length;
                    D[i][j].pre=D[v][j].pre;
                } 
}

时间复杂度分析

三重for循环，时间复杂度为O(n³),适合稠密图

最小支撑树(MST)

对于带权连通无向图，其最小支撑树是包括该图的所有顶点和部分边的图，保证了图的连通性，且边权值总和最小

Prim算法

操作

• 从图中任意一个顶点开始，把这个顶点包括在MST里

• 在那些一个端点在MST里，另一个还不在的边中找一条最小的边，把这条边和对应的不在MST里的顶点包括在MST里

• 一直进行下去直到所有的顶点都在MST里

MST不唯一但是最小权值是确定的

算法

void Prim(Graph& G, int s, Edge* &MST )
{
    int MSTtag=0;//最小支撑树边的标号
    Edge *MST=new Edge[G.VerticesNum()-1];
    MinHeap<Edge> H(G.EdgesNum());     
    for(int i=0;i<G.VerticesNum();i++)//初始化Mark数组、距离数组
        G.Mark[i]=UNVISITED; 
    int v=s;//开始顶点
    G.Mark[v]=VISITED;//开始顶点首先被标记
    do{//将以v为顶点，另一顶点未被标记的边插入最小值堆H
        for(Edge e= G. FirstEdge(v);G.IsEdge(e);e=G. NextEdge(e))	
            if(G. Mark[G. ToVertex(e)]==UNVISITED)
                H.Insert(e);	 
        bool Found=false;
        while(!H.empty())//寻找下一条权最小的边
        {
            e=H.RemoveMin();
            if(G. Mark[G. ToVertex(e)]==UNVISITED)
            {
                Found=true;
                break;
            }
        }
        if(!Found)
        {
            Print("不存在最小支撑树。");
            delete [] MST;//释放空间
            MST=NULL;//MST是空数组
            return;
        } 
        v= G.ToVertex(e);	
        G.Mark[v]=VISITED;//在顶点v的标志位上做已访问的标记
        AddEdgetoMST(e,MST,MSTtag++);//将边e加到MST中
    }while(MSTtag<(G.VerticesNum()-1)) 	
}

时间复杂度与Dijkstra算法相同

Kruskal算法

过程

• 开始时将顶点分为|V|个等价类，每个等价类包括一个顶点
• 以权的大小为顺序处理各条边，如果某条边连接两个不同的等价类的顶点，则这条边被添加到MST中，两个等价类被合并为一个
• 反复执行此过程直到剩下一个等价类

算法

void Kruskal(Graph& G, Edge* &MST
{
    Partree A(G.VerticesNum());//等价类
    MinHeap<Edge> H(G.EdgesNum());//声明一个最小堆
    MST=new Edge[G.VerticesNum()-1];//最小支撑树
    int MSTtag=0;//最小支撑树边的标号 
    for(int i=0; i<G.VerticesNum(); i++)//将图的所有边插入最小值堆H中
        for(Edge e= G.FirstEdge(i); G.IsEdge(e);e=G. NextEdge(e))
            if(G.FromVertex(e)< G.ToVertex(e))
                H.Insert(e);
    int EquNum=G.VerticesNum();//开始时有|V|个等价类
    while(EquNum>1)//合并等价类
    {
        Edge e=H.RemoveMin();//获得下一条权最小的边
        int from=G.FromVertex(e);//记录该条边的信息
        int to= G.ToVertex(e);
        if(A.differ(from,to))//如果边e的两个顶点不在一个等价类
        {
            //将边e的两个顶点所在的两个等价类合并为一个
            A.UNION(from,to); 
            AddEdgetoMST(e,MST,MSTtag++);//将边e加到MST
            EquNum--;//将等价类的个数减1
        }
    }
}

时间复杂度为O(|E|log|E|),适合于稀疏图

这篇关于PKU 数据结构与算法笔记——图的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！