目录
1.什么是图
一个图就是一些顶点的集合，这些点通过一系列
边
结对（连接）。有时，顶点 会称为节点或交点，边称为链接。在社交网络中每个人就是一个顶点，互相认识的人之间通过边联系在一起，边表示彼此的关系。这种关系可以是单向的，也可以是双向的！
边可以是双向的，也可以是单向的！
地图导航——起点、终点和分岔路口（包括十字路口、T字螺口等）都是顶点，导航经过两顶点的路径就是边！
如上图所示，我们导航从一个点到另外一个点可以有条路径，选择不同的路径就会花费不同的时间，这种不同我们可以使用边的
权重
来表示，即根据每条边的实际情况给每一条边分配一个正数或者负数值。
考虑如下机票图，各个城市就是顶点，航线就是边。那么权重就是机票价格。
对于树和链表都是图的特例!
2.图的表示
2.1邻接表表示
在邻接表实现中，每一个顶点会存储一个从它这里开始相邻边的列表。比如如果顶点B有一条表到A、C、E，那么A的列表会有3条边。
邻接列表只描述指向外部的边。B有一条边到A，但是A没有边到B，所以B没有出现在A的临界列表中。查找两个顶点之间的边或者权重会比较费时，因为遍历临界列表直到找到为止。
2.2邻接矩阵
由二维数组对应的行和列都表示顶点，由两个顶点所决定的矩阵对应元素数值表示这里两个顶点是否相连（如，0 表示不相连，非 0 表示相连和权值）、如果相连这个值表示的是相连边的权重。例如，如下图我们用邻接矩阵表示：
往这个图添加顶点的成本非常昂贵，因为新的矩阵结果必须按照新的行/列创建，然后将以已有的数据复制到新的矩阵中。
所以使用哪一个呢？我们先来看看下表
注意：
V表示图中顶点的个划水，E表示边的个数。
结论：
大多数时候，选择邻接列表是正确的。（ 在图比较稀疏的情况下，每一个顶点都只会和少数几个顶点相连，这种情况下邻接列表是最佳选择。如果这个图比较密集，每一个顶点都和大多数其他顶点相连，那么邻接矩阵更合适。
3.图的算法实现
有A、B、C、D、E五个地点，箭头方向表示可从一个地点到达另一个地点，边上的时间表示需要花费的时间 。
邻接表结构的定义
#define MaxSize 1024
typedef struct _EdgeNode { //与节点连结边的定义
int weight; //邻接的顶点
int adjvex; //权重
struct _EdgeNode* next; //下一条边
}EdgeNode;
typedef struct _VertexNode { //顶点节点
char data; //节点数据
struct _EdgeNode* first; //指向邻接第一条边
}VertexNode ,AdjList;
typedef struct _AdjListGraph {
AdjList* adjlist;
int vex; //顶点数
int edge; //边数
}AdjListGraph;
邻接表的初始化
void Init(AdjListGraph& G) {
G.adjlist = new AdjList[MaxSize];
G.edge = 0;
G.vex = 0;
}
邻接表的创建
int Location(AdjListGraph& G, char vex);
void Create(AdjListGraph& G) {
cout << "请输入图的顶点数和边数：" << endl;
cin >> G.vex >> G.edge;
cout << "请输入相关的顶点：" << endl;
for (int i = 0; i < G.vex; i++) {
cin >> G.adjlist[i].data;
G.adjlist[i].first = NULL;
}
char v1, v2 = 0;//保存输入的顶点字符
int weight;//保存边的权重
int i1, i2;//保存顶点在数组中的下标
cout << "请输入相关联的顶点以及权重：" << endl;
for (int i = 0; i < G.edge; i++) {
cin >> v1 >> v2>>weight;
i1 = Location(G, v1);
i2 = Location(G, v2);
if (i1 != -1 && i2 != -1) {
EdgeNode* temp = new EdgeNode;
temp->adjvex = i2;
temp->weight=weight;
temp->next = G.adjlist[i1].first;
G.adjlist[i1].first = temp;
}
}
}
int Location(AdjListGraph& G, char vex) {
for (int i = 0; i < G.edge; i++) {
if (G.adjlist[i].data == vex)
return i;
}
return -1;
}
邻接表的深度遍历
深度优先遍历思想：
首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；
当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直到所有的顶点都被访问过。
使用深度优先搜索来遍历这个图的具体过程是：
1. 首先从一个未走到过的顶点作为起始顶点，比如 A 顶点作为起点。
2. 沿 A 顶点的边去尝试访问其它未走到过的顶点，首先发现 E 号顶点还没有走到过，于是访问 E 顶点。
3. 再以 E 顶点作为出发点继续尝试访问其它未走到过的顶点，接下来访问 D 顶点。
4. 再尝试以 D 顶点作为出发点继续尝试访问其它未走到过的顶点。
5. 但是，此时沿 D 顶点的边，已经不能访问到其它未走到过的顶点，接下来返回到 E 顶点。
6. 返回到 E 顶点后，发现沿 E 顶点的边也不能再访问到其它未走到过的顶点。此时又回到顶点 A（D->E->A），再以 A
顶点作为出发点继续访问其它未走到过的顶点，于是接下来访问 C 顶点。
7. 。。。。。。。。。。
8. 最终访问的结果是 A -> E -> D -> C -> B
//对图上的顶点进行深度遍历
bool visited[MaxSize];
void DFS(AdjListGraph& G, int v) {
int next = -1;
if (visited[v])
return;
cout << G.adjlist[v].data << " ";
visited[v] = true;
EdgeNode* temp = G.adjlist[v].first;
while (temp) {
next = temp->adjvex;
temp = temp->next;
if (visited[next] == false)
DFS(G, next);
}
}
void DFS_Main(AdjListGraph& G) {
for (int i = 0; i < MaxSize; i++) {
visited[i] = false;
}
for (int i = 0; i < G.vex; i++) {
if (visited[i] == false) {
DFS(G, i);
}
}
}
测试代码
int main() {
AdjListGraph G;
Init(G);
Create(G);
DFS_Main(G);
system("pause");
return 0;
}
运行结果
邻接表的广度遍历
广度优先遍历思想
首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点;
然后对每个相邻的顶点，再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。
void BFS(AdjListGraph& G, int v) {
queue<int>q;
q.push(v);
int cur;
int next = -1;
while (!q.empty()) {
cur = q.front();
if (visited[cur] == false) {
cout << G.adjlist[cur].data << " ";
visited[cur] = true;
}
q.pop();
EdgeNode* temp = G.adjlist[cur].first;
while (temp) {
next = temp->adjvex;
temp = temp->next;
q.push(next);
}
}
}
void BFS_Main(AdjListGraph& G) {
for (int i = 0; i < MaxSize; i++) {
visited[i] = false;
}
for (int i = 0; i < G.vex; i++) {
if (visited[i] == false) {
BFS(G, i);
}
}
}
测试代码
int main() {
AdjListGraph G;
Init(G);
Create(G);
BFS_Main(G);
system("pause");
return 0;
}
运行结果
4.图的导航——最短路径算法
从起点开始访问所有路径，则到达终点节点的路径有多条，其中路径权值最短的一条则为最短路径。最短路径算法有
深度优先遍历、广度优先遍历、Bellman-Ford 算法、弗洛伊德算法、 SPFA(Shortest Path Faster Algorithm)算法和迪杰斯特拉算法等。
这里将采用深度优先遍历寻找最短路径
int min_weight = 0x7FFFFFFF;
int steps = 0; //已走过的步数
int path[MaxSize] = { 0 }; //保存走过的路径
int shortest_path[MaxSize] = { 0 };//保存最短路径
//weights记录已走过路线的权重
void DFS_find(AdjListGraph& G, int start,int end,int weights) {
int cur = -1;
if (start == end) {//已找到终点，不用继续遍历
for (int i = 0; i < steps; i++) {
cout << G.adjlist[path[i]].data << " ";
}
cout << "该路径权重为：" << weights<<endl;
if (min_weight > weights) {
min_weight = weights;
memcpy(shortest_path, path, steps * sizeof(int));
}
return;
}
visited[start] = true;
EdgeNode* temp = G.adjlist[start].first;
while (temp) {
int weight = temp->weight;
cur = temp->adjvex;
if (visited[cur] == false) {
visited[cur] = true;
path[steps++] = cur;
DFS_find(G, cur, end, weights+weight);
visited[cur] = false;
path[--steps] = 0;
}
temp = temp->next;
}
}
测试代码
int main() {
AdjListGraph G;
Init(G);
Create(G);
char begin,end;
cout << "输入查找路径的起点与终点" << endl;
cin >> begin >> end;
int b, e;
b = Location(G, begin);
e = Location(G, end);
DFS_find(G, b, e, 0);
system("pause");
return 0;
}
运行结果
5.程序源码
#include<iostream>
#include<queue>
using namespace std;
#define MaxSize 1024
typedef struct _EdgeNode {
int adjvex;
int weight;
struct _EdgeNode* next;
}EdgeNode;
typedef struct _VertexNode {
char data;
struct _EdgeNode* first;
}VertexNode, AdjList;
typedef struct _AdjListGraph {
AdjList* adjlist;
int vex;
int edge;
}AdjListGraph;
void Init(AdjListGraph& G) {
G.adjlist = new AdjList[MaxSize];
G.edge = 0;
G.vex = 0;
}
int Location(AdjListGraph& G, char vex) {
for (int i = 0; i < G.edge; i++) {
if (G.adjlist[i].data == vex)
return i;
}
return -1;
}
void Create(AdjListGraph& G) {
cout << "请输入图的顶点数和边数：" << endl;
cin >> G.vex >> G.edge;
cout << "请输入相关的顶点：" << endl;
for (int i = 0; i < G.vex; i++) {
cin >> G.adjlist[i].data;
G.adjlist[i].first = NULL;
}
char v1, v2 = 0;//保存输入的顶点字符
int weight;//保存边的权重
int i1, i2;//保存顶点在数组中的下标
cout << "请输入相关联的顶点以及权重：" << endl;
for (int i = 0; i < G.edge; i++) {
cin >> v1 >> v2>>weight;
i1 = Location(G, v1);
i2 = Location(G, v2);
if (i1 != -1 && i2 != -1) {
EdgeNode* temp = new EdgeNode;
temp->adjvex = i2;
temp->weight=weight;
temp->next = G.adjlist[i1].first;
G.adjlist[i1].first = temp;
}
}
}
bool visited[MaxSize];
//对图上的顶点进行深度遍历
void DFS(AdjListGraph& G, int v) {
int next = -1;
if (visited[v])
return;
cout << G.adjlist[v].data << " ";
visited[v] = true;
EdgeNode* temp = G.adjlist[v].first;
while (temp) {
next = temp->adjvex;
temp = temp->next;
if (visited[next] == false)
DFS(G, next);
}
}
void DFS_Main(AdjListGraph& G) {
for (int i = 0; i < MaxSize; i++) {
visited[i] = false;
}
for (int i = 0; i < G.vex; i++) {
if (visited[i] == false) {
DFS(G, i);
}
}
}
int min_weight = 0x7FFFFFFF;
int steps = 0; //已走过的步数
int path[MaxSize] = { 0 }; //保存走过的路径
int shortest_path[MaxSize] = { 0 };//保存最短路径
//weights记录已走过路线的权重
void DFS_find(AdjListGraph& G, int start,int end,int weights) {
int cur = -1;
if (start == end) {//已找到终点，不用继续遍历
for (int i = 0; i < steps; i++) {
cout << G.adjlist[path[i]].data << " ";
}
cout << "该路径权重为：" << weights<<endl;
if (min_weight > weights) {
min_weight = weights;
memcpy(shortest_path, path, steps * sizeof(int));
}
return;
}
visited[start] = true;
EdgeNode* temp = G.adjlist[start].first;
while (temp) {
int weight = temp->weight;
cur = temp->adjvex;
if (visited[cur] == false) {
visited[cur] = true;
path[steps++] = cur;
DFS_find(G, cur, end, weights+weight);
visited[cur] = false;
path[--steps] = 0;
}
temp = temp->next;
}
}
void BFS(AdjListGraph& G, int v) {
queue<int>q;
q.push(v);
int cur;
int next = -1;
while (!q.empty()) {
cur = q.front();
if (visited[cur] == false) {
cout << G.adjlist[cur].data << " ";
visited[cur] = true;
}
q.pop();
EdgeNode* temp = G.adjlist[cur].first;
while (temp) {
next = temp->adjvex;
temp = temp->next;
q.push(next);
}
}
}
void BFS_Main(AdjListGraph& G) {
for (int i = 0; i < MaxSize; i++) {
visited[i] = false;
}
for (int i = 0; i < G.vex; i++) {
if (visited[i] == false) {
BFS(G, i);
}
}
}
int main() {
AdjListGraph G;
Init(G);
Create(G);
char begin,end;
cout << "输入查找路径的起点与终点" << endl;
cin >> begin >> end;
int b, e;
b = Location(G, begin);
e = Location(G, end);
DFS_find(G, b, e, 0);
system("pause");
return 0;
}