基于C语言的图论汇编

非简单回路：又回到终点，并且路径无重叠。

    1建立一个顶点表：A = (V,E),Vexs[n]
    2.建立邻接矩阵：二维数组A.arcs[n][n]
        如果属于E的子集，或者（i,j）属于E的子集则添加1
        否则添加0
        顶点和它自身不存在邻接关系

邻接矩阵非对称
顶点的度数  = 所在行元素之和 + 所在列元素之和

邻接矩阵的元素为两个顶点之间的权重，如果两个顶点之间没有弧则记该元素为无穷大

#define MVN 100 // Matrix Vertex Number
#define Maxlnt 32767 // 无穷大
typedef char VerTexType; // Vertex type
typedef int ArcType;//Arc type
typedef struct
{
    VerTexType vex[MVN];// Vertext array
    ArcType arcs[MVN][MVN];// Adjacency Matrix Graph
    int Vexnum,Arcnum;// Current vertex nums & arc nums
}AMGraph;

输入总顶点数和总变数
以此输入点的信息存入顶点表中
初始化邻接矩阵，使每个权值初始化为极大值
构造邻接矩阵

Status CreateUDN(AMGraph &G)// Create Un Direction Net
{
    cin >> G.vexnum>>G.arcnum;//输入总的顶点数，创建无向有权图（也成为网）网
    for(int i = 0; i < G.vexnum;i++)
        cin>>G.vexs[i];// 以此输入顶点的值
    for(int i = 0; i< G.vexnum; i++)
        for(int j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = MaxInt;// 把邻接矩阵元素全部设为极大值
    for(int k = 0; k < G.arcnum; k++)
    {
        cin>>v1>>v2>>w;// 输入确定边的两个点和边的权值
        i = LocateVex(G,v1);//在顶点表中查找顶点的下标
        j = LocateVex(G,v2);
        G.arcs[i][j] = w;// 边确定的权值为w
        G.arcs[j][i] = G.arcs[i][j];//无向有权图矩阵特性：沿对角线对称
        
    }
    return OK;
    // 悟：邻接矩阵中的元素若不为极大值，则标志v1 和v2 是连通的，并且元素的值代表着边的权值。
    // 悟：学好邻接矩阵的关键在于心中要有图，要有表。
}

int LocateVex(AMGraph G, VertexType u)
{
    int i;
    for(i = 0;i < G.vexnum;i++)
    {
        if(u == G.vexs[i])// 如果该顶点和顶点表中的值相匹配的话。
            return i;// 返回顶点表中该顶点的下标。
    }
   
}

struct {
    VertexType data;
    ArcBox *firstin,*firstout;//分别指向该顶点第一条入弧和出弧
}

顶点构造：Data, firstedge,边节点:mark, ivex, ilink, jvex, jlink, infomark 显示该边是否被搜索过，ivex搭配jvex指示该边所依附的两个顶点在数组中的位置，ilink 搭配ivex指示ivex的其他连通的情况，jlink 搭配 jvex指示 jvex的其他连通情况。如果是网的话，info可以用来存储权值等信息。

• 1. 实现邻接表和逆邻接表
• 2. 学习离散数学中树和图的有关知识（了解）
• 3. 学习 王卓-数据结构与算法-的图的十字链表知识，并作笔记。

一条道走到黑沿着某一分支搜索到底，然后折返，看看折返后的顶点有没有未被访问过的分支，如果有搜索到底，然后折返重复以上动作，直到所有顶点的所有分支都被访问过为止。

void DFS(AMGraph G, int v)
{
    printf("%d",v);
    visited[v] = true;//已被访问过，打上标记
    for(int w = 0; w < G.Vexnum; w++)// 访问v的邻接点w
        if((G.arcs[v][w]!=0)&&(!visited[w]))//如果是邻接点，且未被访问过，则访问
            DFS(G,w);// 递归调用DFS继续访问
}

n^2,邻接表 n + e

使用邻接表来存储顶点
需要一个visited数组，用以记录该节点是否被访问过
需要一个循环队列，类似于树的层次遍历，从根节点到孩子节点依次入队

void BFS(Graph G, int v)//Breadth First Search
{
    printf("%d",v);
    visited[v] = true;
    InitQueue(Q);// 初始化循环队列
    EnQueue(Q,v);// v 进队
    while(!QueueEmpty(Q))// 队列非空
    {
        DeQueue(Q,u);// 对头元素出队，并置为u
        for(w = FirstAdjVex(G,u); w > = 0; w = NextAdjVex(G, u, w))
            if(!visited[w])
            {
                printf("%d",w);// 输出下一个节点
                visited[w] = true;//标记为已访问
                EnQueue(Q,w);// v的邻接点w入队
            }// if
    }//while
}//BFS

• 实现有向图的邻接表的存储结构
• 实现一个循环队列
• 翻看严蔚敏—数据结构与算法—深度&广度优先章节

生成树：所有顶点均由边连接在一起，但是不存在回路的图
一个图可以有许多生成树
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图，去掉一个边则不连通
在生成树中再加一条边必然形成回路
若图的节点个数是n则生成树的边数是n-1生成树要包含图中所有顶点
生成树中任意两个顶点间的路径是唯一的
具有n个节点，n-1条边的树不一定是生成树（主要考虑：连通性和回路）

**最小生成树性质：**设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。附带书面笔记。

迪克牛仔斯特拉：有效的程序员不应该浪费时间用于调试程序，而应该在一开始就把故障引入。

有向无环图：Directed Acycline Graphy DAG

在AOV网中没有回路的前提下，我们把图中的全部顶点（活动）排成一个有序序列，使得这个序列中的元素仍然能保持AOV网中前驱与后继的关系，那么这个有序序列也叫做拓扑有序序列。相应的算法，叫做拓扑排序。

AOE网： 用一个有向图表示一个工程的各个子工程及其相互制约关系，以弧表示活动本身，以顶点表示活动的开始或结束，我们称这种图为边表示活动的网（Activity of Edge network）解决关键路径问题

• 王卓-数据结构与算法往后学习
• 整理数据结构与算法笔记
• 实现十字链表

ve(vj) early, 事件vj的最早发生时间。
vl(vj) late，事件vj最晚发生时间。

e(i) 表示活动i的最早开始时间。
l(i) 表示活动i的最晚开始时间。

时间余量：最晚开始时间减去最早开始时间。
关键活动：没有时间余量， l(i) - e(i) = 0;

只需找出该活动所在两个顶点（事件）中，一事件的最早发生时间，一事件的最晚发生时间，求差值即可。
1.计算Ve(i),Vl(j)即每一个顶点的最早和最晚发生时间
2.求e(i),l(i)
3.计算l(i) - e(i)

1.若网中有几条关键路径存在，则需加快同时在几条关键路径上的关键活动
2.如果一个活动处于所有的关键路径上，那么提高这个活动的速度就能缩短整个工程完成的时间。
3 处于所有关键路径上的活动完成时间也不能缩短太多，否则会使原来的关键路径变成不是关键路径。这时，就需要重新寻找关键路径，这可能导致时间资源的浪费。

• 实现深度遍历和广度遍历
• 聚合整理笔记。