图
1.图的遍历
1.1DFS深度遍历（类似二叉树的先序遍历）
思路:
1.为了防止多次访问，设置标志位；由于结点多，所以设置一个数组，将其全部初始化为0，如果访问过该节点，则将对应下标的元素置1
2.找到当前节点的第一条边，如果边存在则说明有邻接点，可以继续往下走
3.找到邻接点后，如果下标为0，则说明未被访问，那就递归访问，直到无邻接点
4.无邻接点则回退，回退后则访问前一个结点的下一条边
#include<stdio.h>
#include<iostream>
#define maxsize 10
using namespace std;
typedef struct ArcNode //边
{
int adjvex; //边所指向的结点的位置
struct ArcNode* next;//指向下一条边的指针
int info;//
}Edge;
typedef struct VNode
{
char data;
ArcNode* firstarc;
};
typedef struct AGraph
{
VNode adjlist[maxsize];
int n, e;//顶点数和边数
};
int visit[maxsize]; //0 1 2 3 4 visit[1]=1; 全局数组
//DFS
void DFS(AGraph* G, int v)//起点编号
{
ArcNode* p;
visit[v] = 1;
// Visit(v);
p = (G->adjlist[v]).firstarc;
while (p != NULL)
{
if (visit[p->adjvex] == 0)
{
DFS(G, p->adjvex);
}
p = p->next;
}
}
1.2BFS广度遍历（类似二叉树的层序遍历）
思路：
1.为了防止多次访问，设置标志位，初始为0，访问置1
2.将第一个结点入队列
3.如果队列不为空则出队，出队的同时将该节点的邻接点入队
入队的具体操作：(先让指针指向该节点的第一条边，如果存在且未被访问，则入队，接着访问下一条边；若被访问过则直接指向该节点下一条边）
/BFS
int visit[maxsize];
void BFS(AGraph* G, int v)
{
ArcNode* p;
int que[maxsize], front = 0, rear = 0;
int j;
// Visit(v);
visit[v] = 1;
rear = (rear + 1) % maxsize;//入队
que[rear] = v;
while (front != rear)
{
front = (front + 1) % maxsize;//出队
j = que[front];
p = G->adjlist[j].firstarc;
while (p != NULL)
{
if (visit[p->adjvex] == 0)
{
// Visit(p->adjvex);
visit[p->adjvex] = 1;
rear = (rear + 1) % maxsize;//邻接点入队
que[rear] = p->adjvex;
}
p = p->next;
}
}
}
1.3一点点注解
定义结点结构体时会碰到以下这种形式：
typedef可以掩饰复合类型，如指针和数组。例如不需要像这样定义一个字符数组：
char arr[5];
char brr[5];
每当要用到相同类型和大小的数组是，可以：
typedef char Array[5];
Array arr,brr;
so:
typedef struct VNode
{
int a;
struct VNode* next;
}Adjlist[maxsize];
Adjlist A;
//使用Adjlist可以定义一个长度为maxsize的结构体数组，数组中的每个元素都是struct VNode类型
2.最小生成树（Prim）
时间复杂度O（n²），只与顶点有关，因此适合稠密图
思路：
1.设置结点数组以及最小权值数组
2.以v0为起点，记录为权值数组的值
3.将所有节点，在数组里置为0，即未被并入生成树中
4.将起点并入生成树，将初始权值sum置为0，之后每次并入都将权值累加
5.在以v为起点的权值数组里，找最小的权值，将其并入生成树中，并记录其终点结点的位置
6.以终点结点作为起点，更新权值数组
7.循环步骤56，n-1次，n个结点都并入生成树中，结束！
#define INF 10000000
typedef struct VertexType//顶点类型
{
int no; //顶点编号
char info; //顶点其他信息
};
typedef struct MGraph //邻接矩阵类型
{
int edges[maxsize][maxsize];//边的权值
int n, e;//顶点数和边数
VertexType vex[maxsize];//结点信息
};
void Prim(MGraph g,int v0,int &sum)
{
int lowcost[maxsize], vset[maxsize], v;
//lowcost数组是生成树到剩余各顶点最短边的权值
//vset数组是记录顶点的访问情况，如果vset[i]=0表示顶点i还未并入生成树
int i, j, k, min;
v = v0;
for (i = 0; i < g.n; ++i)
{
lowcost[i] = g.edges[v0][i];//顶点到各点的权值
vset[i] = 0;//初始化各点未入生成树
}
vset[v0] = 1;//顶点并入生成树
sum = 0;//权值初始值为0
for (i = 0; i < g.n - 1; ++i)//控制次数，更新n-1次
{
min = INF;//INF是一个被定为比图中所有边权值都大的常量
for (j = 0; j < g.n; ++j)//选出以v0为起点，候选边中的最小值
{
if (vset[j] == 0 && lowcost[j] < min)//未被并入且权值小
{
min = lowcost[j];//更新min值
k = j;//记录该结点的序号
}
}
vset[k] = 1;//将上个结点并入，置1
v = k;//记录结点序号
sum += min;//权值累加
for (j = 0; j < g.n; ++j)//
{
//以最后一个被并入的结点，为起点更新最小权值
if (vset[j] == 0 && g.edges[v][j] < lowcost[j])//未被并入且从其出发找到下一个顶点的权值<记录的最小权值
{
lowcost[j] = g.edges[v][j];//最小权值更新（同一个终点，更新成最短的值）
}
}
}
}
3.拓扑排序
拓扑排序的一般步骤为：
1.找出入度为0的结点，输出该结点并删除其出度的边
2.重复1
思路:
1.找到第一个入度为0的结点入栈
2.如果栈不为空则出栈，每次出栈计数器+1
3.该节点邻接点的入度需要-1（具体操作为：指针先指向该结点的第一条边，如果存在边则入度-1，[如果减的过程中度为0则入栈,不为0就跳过]，指针指向下一条边，入度-1）
4.如果计数器的值等于总结点数，则拓扑排序成功，否则失败返回0
//拓扑排序
typedef struct VNode
{
char data;
int count;//当前结点的入度
ArcNode* firstarc;
};
int TopSort(AGraph* G)
{
int i, j, n = 0;
int stack[maxsize], top = -1; //定义并初始化
ArcNode* p;
for (i = 0; i < G->n; ++i)
{
if (G->adjlist[i].count == 0) //入度为0入栈
{
stack[++top] = i;//top=top+1; stack[top]=i;
}
}
while (top != -1) //栈不为空
{
i = stack[top--]; //出栈
++n;//计数器
cout << i << " ";
p = G->adjlist[i].firstarc;
while (p != NULL) //如果存在边 指向的顶点入度-1
{
j = p->adjvex;
--(G->adjlist[j].count);
if (G->adjlist[j].count == 0)//度为0就入栈
{
stack[++top] = j;
}
p = p->next;
}
}
if (n == G->n)//出栈一次 n+1，出栈==总数则成功
{
return 1;
}
else
{
return 0;
}
}