图论

系统性去总结图论的知识点，有关于邻接矩阵等多方面知识点，有利于我巩固专业课上的知识点，也是自己认真去了解各项学习任务的进度。

图的表示，矩阵，邻接矩阵

  • 用邻接矩阵表示顶点间的相邻关系

  • 用一个顺序表来存储顶点信息
    设G=(V,E)是具有n个顶点的图,以1和0来表示是否是E(G)的边

  • 邻接表是图的一种顺序存储与链式存储结合的存储方法，类似于树的孩子链表表示法
    构造邻接表，链表的方式，理解简单，效率不高

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    #pragma once
    #include<iostream>
    using namespace std;

    enum GraphKind{DG,WDG,UDG,WUDG};

    template<typename VertexType,typename InfoType>
    class ALGraph
    {
    public:
    	static const int MAX_VERTEX_NUM = 20;
    	ALGraph(int verNum, GraphKind _kind)
    		:vexnum(verNum), arcnum(0), kind(_kind)
    	{
    		for (int i = 0; i < MAX_VERTEX_NUM; i++)//初始化
    			vertices[i].firstarc = NULL;
    	}
    	void Create()
    	{
    		switch (kind)
    		{
    		case DG://构造一个有向图
    			CreateDG();
    			break;
    		case WDG://构造一个带权有向图
    			CreateWDG();
    			break;
    		case UDG://构造一个无向图
    			CreateUDG();
    			break;
    		case WUDG://构造一个带权无向图
    			CreateWUDG();
    			break;
    		}
    	}
    	void displayGraph()
    	{
    		for (int i = 0; i < vexnum; i++)
    		{
    			cout << "第" << i + 1 << "个顶点是：" << vertices[i].data
    				<< "邻接表为：";
    			ArcNode *arcNode = vertices[i].firstarc;
    			while (arcNode)
    			{
    				cout << "->" << vertices[arcNode->adjvex].data
    					<< "(" << arcNode->info << ")";
    				arcNode = arcNode->nextarc;
    			}
    			cout << endl;
    		}
    	}
    private:
    	void InitVertics()//初始化头列表
    	{
    		cout << "请输入每个顶点的关键字：" << endl;
    		VertexType val;
    		for (int i = 0; i < vexnum; i++)
    		{
    			cin >> val;
    			vertices[i].data = val;
    		}
    	}
    	void insertArc(int vHead, int vTail, InfoType w)
    	{
    		ArcNode *newArcNode = new ArcNode;
    		newArcNode->adjvex = vTail;
    		newArcNode->nextarc = NULL;
    		newArcNode->info = w;

    		ArcNode *arcNode = vertices[vHead].firstarc;
    		if (NULL == arcNode)
    			vertices[vHead].firstarc = newArcNode;
    		else
    		{
    			while (arcNode->nextarc != NULL)
    			{
    				arcNode = arcNode->nextarc;
    			}
    			arcNode->nextarc = newArcNode;
    		}
    		arcnum++;
    	}
    	//构造一个有向图
    	void CreateDG()
    	{
    		InitVertics();
    		int vhead, vtail;
    		cout << "请依次输入每条边的开始顶点和结束顶点：" << endl;
    		while (cin >> vhead >> vtail)
    		{
    			insertArc(vhead, vtail, 0);
    		}
    	}
    	//构造一个带权有向图
    	void CreateWDG()
    	{
    		InitVertics();
    		int vhead, vtail;
    		InfoType w;
    		cout << "请依次输入每条边的开始顶点和结束顶点和权值：" << endl;
    		while (cin >> vhead >> vtail >> w)
    		{
    			insertArc(vhead, vtail, w);
    		}
    	}
    	//构造一个无向图
    	void CreateUDG()
    	{
    		InitVertics();
    		int vhead, vtail;
    		cout << "请依次输入每条边的开始顶点和结束顶点：" << endl;
    		while (cin >> vhead >> vtail)
    		{
    			insertArc(vhead, vtail, 0);
    			insertArc(vtail, vhead, 0);
    		}
    	}

    	//
    	void CreateWUDG()
    	{
    		InitVertics();
    		int vhead, vtail;
    		InfoType w;
    		cout << "请依次输入每条边的开始顶点和结束顶点和权值：" << endl;
    		while (cin >> vhead >> vtail>>w)
    		{
    			insertArc(vhead, vtail, w);
    			insertArc(vtail, vhead, w);
    		}
    	}

    	struct ArcNode//表结点
    	{
    		int adjvex;//该弧所指向的顶点的位置
    		ArcNode *nextarc;//指向下一条弧的指针
    		InfoType info;//该弧相关信息的指针
    	};
    	struct VNode//头结点
    	{
    		VertexType data;//顶点信息
    		ArcNode *firstarc;//指向第一条依附在该顶点的弧的指针
    	};

    	VNode vertices[MAX_VERTEX_NUM];//头列表
    	int vexnum; //图的当前顶点数
    	int arcnum;//图的弧数
    	GraphKind kind;//图的种类
    };
                           //邻接表结构体

    邻接矩阵

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    #include<iostream>
    #include<vector>
    using namespace std;
    //枚举类型，图的种类 DG：有向图；WDG：带权值的有向图；
    //UDG: 无向图；WUDG: 带权值的无向图
    enum GraphKind{DG,WDG,UDG,WUDG};
    template<typename VertexType,typename VRType,typename InfoType>
    class MGraph
    {
    public:
    	MGraph(int vexNum, GraphKind __kind) :vexnum(vexNum), arcnum(0), kind(__kind)
    	{
    		vvec = new VertexType[vexnum];
    		arcs = new ArcCell *[vexnum];//二维数组动态分配（vexnum*vexnum)
    		for (int i = 0; i < vexnum; i++)
    		{
    			arcs[i] = new ArcCell[vexnum];
    		}
    	}
    	void Create()
    	{
    		switch (kind)
    		{
    		case DG:
    			CreateDG();
    			break;
    		case WDG:
    			CreateWDG();
    			break;
    		case UDG:
    			CreateUDG();
    			break;
    		case WUDG:
    			CreateWUDG();
    			break;
    		default:
    			return;
    		}
    	}
    	void Init()
    	{
    		cout << "请输入每个顶点的关键字：" << endl;
    		VertexType val;
    		for (int i = 0; i < vexnum; i++)
    		{
    			cin >> val;
    			vvec[i] = val;
    		}
    		for (int i = 0; i < vexnum; i++)
    		{
    			ArcCell ac;
    			ac.adj = 0;
    			ac.info = NULL;
    			for (int j = 0; j < vexnum; j++)
    				arcs[i][j] = ac;
    		}
    	}
    	void CreateDG()//构造一个有向图
    	{
    		Init();
    		int vhead, vtail;
    		cout << "请依次输入每条边的开始顶点和结束顶点：" << endl;
    		while (cin >> vhead >> vtail)
    		{
    			arcnum++;
    			arcs[vhead][vtail].adj = 1;
    		}
    	}
    	void CreateWDG()//构造一个带权有向图
    	{
    		Init();
    		int vhead, vtail;
    		InfoType w;
    		cout << "请依次输入每条边的开始顶点和结束顶点和权值：" << endl;
    		while (cin >> vhead >> vtail >> w)
    		{
    			arcnum++;
    			arcs[vhead][vtail].adj = w;
    		}
    	}

    	void CreateUDG()//构造一个无向图
    	{
    		Init();
    		int vhead, vtail;
    		cout << "请依次输入每条边的开始顶点和结束顶点：" << endl;
    		while (cin >> vhead >> vtail)
    		{
    			arcnum += 2;
    			arcs[vhead][vtail].adj = 1;
    			arcs[vtail][vhead].adj = 1;
    		}
    	}

    	void CreateWUDG()//构造一个带权无向图
    	{
    		Init();
    		int vhead, vtail;
    		InfoType w;
    		cout << "请依次输入每条边的开始顶点和结束顶点和权值：" << endl;
    		while (cin >> vhead >> vtail>>w)
    		{
    			arcnum += 2;
    			arcs[vhead][vtail].adj = w;
    			arcs[vtail][vhead].adj = w;
    		}
    	}

    	void displayGraph()
    	{
    		cout << "总共有" << vexnum << "个顶点，" << arcnum << "条边" << endl;
    		for (int i = 0; i < vexnum; i++)
    		{
    			cout << "第" << i + 1 << "个顶点是：" << vvec[i] << "相邻的边有：";
    			for (int j = 0; j < vexnum; j++)
    			{
    				if (arcs[i][j].adj != 0)
    					cout << vvec[j] << "(" << arcs[i][j].adj << ")";
    			}
    			cout << endl;
    		}
    	}
    private:
    	struct ArcCell
    	{
    		VRType adj;//两连接点之间的权值
    		InfoType info;
    	};
    	VertexType *vvec;//顶点向量
    	ArcCell **arcs;//邻接矩阵
    	int vexnum;//图的结点个数
    	int arcnum;//图的边的个数
    	GraphKind kind;//图的种类
    };

    dijkstra(迪杰斯特拉) 算法(利用贪心算法）

  • 解释：首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的。所谓松弛操作就是遍历一遍看通过刚刚找到的距离的最短点作为中转站会不会更近。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define Inf 0x3f3f3f3f
     
    using namespace std;
     
    int map[1005][1005];
     
    int vis[1005],dis[1005];
    int n,m;//n个点，m条边
     
    void Init ()
    {
    	memset(map,Inf,sizeof(map));
    	for(int i=1;i<=n;i++)
    	{
    		map[i][i]=0;
    	}
    }
     
    void Getmap()
    {
    	int u,v,w;
        for(int t=1;t<=m;t++)
    	{
    	  	scanf("%d%d%d",&u,&v,&w);
    	  	if(map[u][v]>w)
    		  {
    		  map[u][v]=w;
    		  map[v][u]=w;
    	      }
    	}	
    	
    }
     
    void Dijkstra(int u)
    {
    	memset(vis,0,sizeof(vis));
    	for(int t=1;t<=n;t++)
    	{
    		dis[t]=map[u][t];
    	}
    	vis[u]=1;
    	for(int t=1;t<n;t++)
    	{
    		int minn=Inf,temp;
    		for(int i=1;i<=n;i++)
    		{
    			if(!vis[i]&&dis[i]<minn)
    			{
    				minn=dis[i];
    				temp=i;
    			}
    		}
    		vis[temp]=1;
    		for(int i=1;i<=n;i++)
    		{
    			if(map[temp][i]+dis[temp]<dis[i])
    			{
    				dis[i]=map[temp][i]+dis[temp];
    			}
    		}
    	}
    	
    }
     
    int main()
    {
    	
    	scanf("%d%d",&m,&n);
    	Init();
    	Getmap();
    	Dijkstra(n);
    	printf("%d\n",dis[1]);
    	
    	
    	return 0;
    }

    参考文献

    prim(普里姆算法)

  1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；
  2. 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
  3. 重复下列操作，直到Vnew = V：

a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4. 输出：使用集合Vnew和Enew来描述所得到的最小生成树。
图例：


参考文献

kruskal(克鲁斯卡尔算法)

  1. 记Graph中有v个顶点，e个边

  2. 新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边

  3. 将原图Graph中所有e个边按权值从小到大排序

  4. 循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中

             if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中

                                  添加这条边到图Graphnew中



    科鲁斯卡算法代码:主要是先排序权值，然后再选择最短的权值，禁止形成回路，判断是否两个端点是否同色

floyd(弗洛伊德算法、插点法)

  • floyd算法是解决给定的加权图中顶点间的最短路径的一种算法，是一种动态规划算法，稠密图效果最佳

参考文献

总结

  1. dijkstra(迪杰斯特拉算法) 时间复杂度O(n2)，依此遍历所有方向，然后获取最短路径
  2. prim(普里姆算法) 时间复杂度O(n2)，先确定一个点，然后去寻找最短路径的点，然后根据确定的点再重复去找最短的点
  3. kruskal(克鲁斯卡尔算法) 时间复杂度O(n)，先确定图中权重最小的，然后再找下一个权重小的
  4. floyd(弗洛伊德算法) 时间复杂度O(n3)，分别顶点作为中介点，不断更新矩阵