圖（Graph）的基礎操作（C++）

#include<stdio.h>
#include<queue>
#include<stack>
#include<stdlib.h>
using namespace std;
typedef char VertexType;//頂點類型
typedef int EdgeType;//邊的權重
#define MAXVEX 100//最大頂點數
#define INFINITY 65535//代表無窮 
#define MAXEDGE 1000
typedef struct
{
	VertexType vexs[MAXVEX];//頂點表 
	EdgeType arc[MAXVEX][MAXVEX];//鄰接矩陣 
	int numVertexes,numEdges;//目前的頂點數和邊數 
} MGraph;

拓撲排序&關鍵路徑

求拓撲排序的基本思想：

1）從有向圖中選一個無前驅（入度為0）的頂點輸出；

2）将此頂點和以它為起點的孤删除；

3）重複1）和2），直到不存在無前驅的頂點；

4）若此時輸出的頂點數小于有向圖中的頂點數，則說明有向圖中存在回路，否則輸出的頂點的順序即為一個拓撲序列。

typedef struct EdgeNode//邊表結點 (用于拓撲排序)
{
	int adjvex;//鄰接頂點的下标 
	int weight;//權，用于關鍵路徑算法 
	struct EdgeNode *next;//指向下一個鄰接點 
}EdgeNode;

typedef struct VertexNode//頂點表結點 (用于拓撲排序)
{
	int in;//頂點的入度 
	int data;//頂點的值 
	EdgeNode *firstedge;//邊表的頭指針 
}VertexNode,AdjList[MAXVEX];

typedef struct//(用于拓撲排序)
{
	AdjList adjList;
	int numVertexes,numEdges;//頂點數和邊數  
}graphAdjList,*GraphAdjList;

//拓撲排序，若GL無回路則輸出拓撲排序序列并傳回true，否則傳回false 
bool TopologicalSort(GraphAdjList GL)
{
	EdgeNode *e;
	int i,k,gettop,count=0;//gettop用于儲存出棧的數，count用于統計輸出頂點的個數 
	stack<int> s;
	for(i=0;i<GL->numVertexes;i++)//将入度為0的頂點入棧 
	{
		if(GL->adjList[i].in==0)s.push(i);
	}
	while(!s.empty())
	{
		gettop=s.top();
		s.pop();
		printf("%d -> ",GL->adjList[gettop].data);
		count++;
		for(e=GL->adjList[gettop].firstedge;e;e=e->next)
		{
			k=e->adjvex;
			if(!(--GL->adjList[k].in))s.push(k);//若入度為0則入棧，友善下次循環輸出 
		} 
	}
	if(count<GL->numVertexes)return false;//count<頂點數說明存在環 
	else return true;
}


int *etv,*ltv;//指向earliest time of vertex & latest time of vertex數組的指針 
stack<int> s2;//用于儲存拓撲序列 
//增加了一些代碼的拓撲排序，用于尋找關鍵路徑
//若GL無回路則輸出拓撲排序序列并傳回true，否則傳回false 
bool TopologicalSort2(GraphAdjList GL)
{
	EdgeNode *e;
	int i,k,gettop,count=0;//gettop用于儲存出棧的數，count用于統計輸出頂點的個數 
	stack<int> s;
	for(i=0;i<GL->numVertexes;i++)//将入度為0的頂點入棧 
	{
		if(GL->adjList[i].in==0)s.push(i);
	}
	etv=(int*)malloc(GL->numVertexes*sizeof(int));//建立事件最早發生時間數組 
	for(i=0;i<GL->numVertexes;i++)etv[i]=0;//數組的初始化 
	while(!s.empty())
	{
		gettop=s.top();
		s.pop();
		count++;
		s2.push(gettop);//将拓撲序列入棧 
		for(e=GL->adjList[gettop].firstedge;e;e=e->next)
		{
			k=e->adjvex;
			if(!(--GL->adjList[k].in))s.push(k);//若入度為0則入棧，友善下次循環輸出 
			if(etv[gettop]+e->weight>etv[k])etv[k]=etv[gettop]+e->weight;
		} 
	}
	if(count<GL->numVertexes)return false;//count<頂點數說明存在環 
	else return true;
}

//尋找關鍵路徑
void CriticalPath(GraphAdjList GL)
{
	EdgeNode* e;
	int i,gettop,k,j;
	int ete,lte;//earliest time of edge & latest time of edge
	TopologicalSort(GL);
	ltv=(int*)malloc(GL->numVertexes*sizeof(int));
	for(i=0;i<GL->numVertexes;i++)ltv[i]=etv[GL->numVertexes-1];//數組的初始化 
	while(!s2.empty())
	{
		gettop=s2.top();
		s2.pop();
		for(e=GL->adjList[gettop].firstedge;e;e=e->next)
		{
			k=e->adjvex;
			if(ltv[k]-e->weight<ltv[gettop])ltv[gettop]=ltv[k]-e->weight;
		}
	}
	for(j=0;j<GL->numVertexes;j++)
	{
		for(e=GL->adjList[j].firstedge;e;e=e->next)
		{
			k=e->adjvex;
			ete=etv[j];
			lte=ltv[k]-e->weight;
			if(ete==lte)
				printf("<v%d-v%d> length:%d\n",GL->adjList[j].data,GL->adjList[k].data,e->weight);
		}
	}
}

最短路徑

typedef int Patharc[MAXVEX];//儲存最短路徑(用于Dijkstra算法尋找最短路徑)
typedef int ShortPathTable[MAXVEX];//儲存從起點到各點的最短路徑的權值和(用于Dijkstra算法尋找最短路徑)

typedef int Patharc1[MAXVEX][MAXVEX];//儲存最短路徑(用于Floyd算法尋找最短路徑)
typedef int ShortPathTable1[MAXVEX][MAXVEX];//儲存從起點到各點的最短路徑的權值和(用于Floyd算法尋找最短路徑)

//Floyd算法求最短路徑
void ShortestPath_Floyd(MGraph *G,Patharc1 *P,ShortPathTable1 *D)
{
	int v,w,k;
	for(v=0;v<G->numVertexes;v++)//初始化D和P 
	{
		for(w=0;w<G->numVertexes;w++)
		{
			(*D)[v][w]=G->arc[v][w];
			(*P)[v][w]=w;
		}
	}
	for(k=0;k<G->numVertexes;k++)//k為中轉頂點的下标 
	{
		for(v=0;v<G->numVertexes;v++)//v為起點 
		{
			for(w=0;w<G->numVertexes;w++)//w是終點 
			{
				if((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
				{
					(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
					(*P)[v][w]=(*P)[v][k];
				}
			}
		}
	}
	//列印最短路徑
	printf("各頂點間最短路徑如下：\n"); 
	for(v=0;v<G->numVertexes;v++)
	{
		for(w=v+1;w<G->numVertexes;w++)
		{
			printf("v%d-v%d weight:%d",v,w,(*D)[v][w]);
			k=(*P)[v][w];// 獲得第一個路徑頂點下标 
			printf(" path: %d",v);//列印源點 
			while(k!=w)
			{
				printf(" ->%d",k);//列印路徑頂點 
				k=(*P)[k][w];//獲得下一個路徑頂點的下标 
			}
			printf(" ->%d\n",w);//列印終點 
		}
		printf("\n");
	}
} 

//Dijkstra算法求最短路徑及相應的長度 
//*P[v]為前驅點下标，D[v]表示從v0到v的最短路徑長度 
void ShortestPath_Dijkstra(MGraph *G,int v0,Patharc P,ShortPathTable D) 
{
	int v,w,k,min;
	int final[MAXVEX];//final[w]=1 表示已經求得v0和vw的最短路徑 
	for(v=0;v<G->numVertexes;v++)//初始化 
	{
		final[v]=0;//全部頂點初始化為未知最短路徑狀态 
		D[v]=G->arc[v0][v];//将與v0有連線的頂點加上權值 
		P[v]=-1;//初始化路徑數組為-1 
	}
	D[v0]=0;
	final[v0]=1;
	
	//每次循環求得起點v0到頂點V的最短路徑
	for(v=1;v<G->numVertexes;v++)
	{
		min=INFINITY;
		for(w=0;w<G->numVertexes;w++)//尋找離v0最近且尚未找到最短路徑的頂點 
		{
			if(!final[w]&&D[w]<min)
			{
				k=w;
				min=D[w];
			}
		}
		final[k]=1;
		for(w=0;w<G->numVertexes;w++)///修正目前的最短路徑及距離 
		{
			if(!final[w]&&(min+G->arc[k][w]<D[w]))
			{
				D[w]=min+G->arc[k][w];
				P[w]=k;
			}
		}
	} 
}

最小生成樹

//Prim算法生成最小生成樹
void MiniSpanTree_Prim(MGraph *G)
{
	int min,i,j,k;
	int adjvex[MAXVEX];//儲存相關頂點間邊的權值點下标 
	int lowcost[MAXVEX];//儲存相關頂點間邊的權值
	lowcost[0]=0;//初始化第一個權值為0，即将v0加入生成樹 
	adjvex[0]=0;//初始化第一個頂點下标為0
	for(i=1;i<G->numNodes;i++)//周遊除下标為0外的所有頂點 
	{
		lowcost[i]=G->arc[0][i];//v0與其他頂點的權值存入數組 
		adjvex[i]=0;//初始化都為v0的下标 ?????
	} 
	for(i=1;i<G->numNodes;i++)
	{
		min=INFINITY;
		j=1;k=0;
		while(j<G->numNodes)//整個while循環的作用：找到與已聯通結點相連的、不會形成環路的最短邊 
		{
			if(lowcost[j]!=0&&lowcost[j]<min)//若權值不為0且小于min
			{
				min=lowcost[j];//則讓目前權值成為最小值
				k=j;// 并将其下标存入k 
			}
			j++;
		}
		printf("(%d,%d)\n",adjvex[k],k);//列印目前頂點的邊中權最小的那條
		lowcost[k]=0;//将目前頂點權設為0，表示此頂點已經完成任務
		
		
		for(j=1;j<G->numNodes;j++)
		{
			if(lowcost[j]!=0&&G->arc[k][j]<lowcost[j])//若下标為k的頂點的各邊權值小于這些頂點未被加入生成樹時的權值 
			{
				lowcost[j]=G->arc[k][j];//将較小的權值存入lowcost相應位置 
				adjvex[j]=k;//将下标為k的頂點存入adjvex 
			}
		} 
	}
} 

typedef struct //邊集數組 (用于Kruskal算法)
{
	int begin;
	int end;
	int weight;
}Edge;

//(用于Kruskal算法)查找連線頂點的尾部下标 
int Find(int *parent,int f)
{
	while(parent[f]>0)
	{
		f=parent[f];
	}
	return f;
} 

//Kruskal算法生成最小生成樹 
void MiniSpanTree_Kruskal(MGraph *G)
{
	int i,n,m;
	Edge edges[MAXEDGE];//邊集數組，其中的元素按照權值從小到大排序 
	int parent[MAXVEX];//判斷邊與邊是否形成回路,下标和儲存的值分别代表邊的起點和終點  
	
	//省略将鄰接矩陣轉換為邊集數組并排序的過程 
	
	for(i=0;i<G->numNodes;i++)
		parent[i]=0;//初始化 
	for(i=0;i<G->numEdges;i++)
	{
		n=Find(parent,edges[i].begin);
		m=Find(parent,edges[i].end);
		if(n!=m)//n!=m說明此邊沒有和現有的生成樹形成環路 
		{
			parent[n]=m;//将結尾頂點放入下标為起點的parent中，表示該邊已經在生成樹裡 
			printf("(%d,%d) %d\n",edges[i].begin,edges[i].end,edges[i].weight);
		}
	} 
}

DFS（深度優先搜尋）&BFS（廣度優先搜尋）

bool visited[MAXVEX];//記錄結點是否被通路過 (用于DFS&BFS)

void DFS(MGraph *G,int i)
{
	int j;
	visited[i]=true;
	printf("%c ",G->vexs[i]);
	for(j=0;j<G->numNodes;j++)
	{
		if(G->arc[i][j]==1&&!visited[j])
		DFS(G,j);
	}
}

void DFSTraverse(MGraph *G)
{
	int i;
	for(i=0;i<G->numNodes;i++)
		visited[i]=false;
	for(i=0;i<G->numNodes;i++)//如果是連通圖則本循環隻執行一次
		if(!visited[i]) DFS(G,i);
}

void BFSTraverse(MGraph *G)
{
	int i,j;
	queue <int> Q;
	for(i=0;i<G->numNodes;i++)
		visited[i]=false;
	Q.pop();
	for(i=0;i<G->numNodes;i++)
	{
		if(!visited[i])
		{
			visited[i]=true;
			printf("%c ",G->vexs[i]);
			Q.push(i);
			while(!Q.empty())
			{
				Q.pop();
				for(j=0;j<G->numNodes;j++)
				{
					if(G->arc[i][j]==1&&!visited[j])
					{
						visited[j]=true;
						printf("%c ",G->vexs[j]);
						Q.push(j);
					}
				}
			}
		}
	}
}

建立無向圖的鄰接矩陣

//建立無向圖的鄰接矩陣 
void CreateMGragh(MGraph *G) 
{
	int i,j,k,w;
	printf("依次輸入頂點數和邊數：\n");
	scanf("%d %d",&G->numNodes,&G->numEdges);
	for(i=0;i<G->numNodes;i++)
		scanf(&G->vexs[i]);//建立頂點表 
		//上面這行看不懂 
	for(i=0;i<G->numNodes;i++)
		for(j=0;j<G->numNodes;j++)
			G->arc[i][j]=INFINITY;//鄰接矩陣初始化 
	for(k=0;k<G->numNodes;k++)
	{
		printf("輸入邊(vi,vj)的下标i,下标j和權w,中間用空格分隔:\n");
		scanf("%d %d %d",&i,&j,&w);
		G->arc[i][j]=w;
		G->arc[j][i]=w;
	}	
}

聯系之前的文章：廣度優先搜尋（BFS）尋找最短路徑_mirrorboat的部落格-CSDN部落格#include<iostream>using namespace std;void EnQueue(int i, int j, int k); //入隊一個節點void DeQueue(int* i, int* j, int* k); //擷取目前節點的序号和對應的迷宮坐标，然後出列int GetNextPos(int* i, int* j, int count); //得到下一個鄰接點的位置void ShortestPath_BFS(int i, int j); //廣度優先遍.

圖（Graph）的基礎操作（C++）

https://blog.csdn.net/mirrorboat/article/details/122638680?spm=1001.2014.3001.5502

圖（Graph）的基礎操作（C++）

繼續閱讀

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

PAT 1089 Insert or Merge[難]

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希