[数据结构与算法]数据结构~图（只记录部分）

数据结构~图（只记录部分）

1：邻接表：

1-1：表示无向图：
代码如下：（java）

import java.util.*;
public class MyMap {
    static int n,m;//n个点，m条路径
    //创建一个，顶点名称 对应 与这个顶点连接的所有顶点坐标
    static Map<String, LinkedList<Integer>> map=new HashMap<>();
    ///邻接表构建无向图：
    public static Boolean CreateUDG(){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        int arc;//顶点位置下标
        String adjVex;//顶点名称
        Map<Integer,String> tem = new HashMap<>();
        sc.nextLine();
        for(int i=0;i<n;i++){
            adjVex = sc.nextLine();
            //存放顶点名称+对应的坐标
            tem.put(i,adjVex);
            //无向图，先分配好内存
            map.put(adjVex,new LinkedList<>());
        }
        int x,y;
        for(int i=0;i<m;i++){
            //输入这两个有连接的顶点的坐标
            x=sc.nextInt();
            y=sc.nextInt();
            //每次插入的时候，是链表的头插入
            map.get(tem.get(x)).add(0,y);
            map.get(tem.get(y)).add(0,x);
        }
        for(int i=0;i<n;i++){
            System.out.print(tem.get(i));
            //map.get(tem.get(i)).forEach(System.out::print);
            for (Integer kk : map.get(tem.get(i))) {
                System.out.print(" ->"+kk);
            }
            System.out.println();
        }
        return true;
    }
    public static void main(String[] args) {
        CreateUDG();
    }
}

运行截图：

1-2：表示有向图：
代码如下：（java）同上个代码（区别就是记录边的时候，把反向的路不加入）：//map.get(tem.get(y)).add(0,x);

运行截图：

说到邻接表了，那么也提一下逆邻接表，就是邻接表记录的是出，而逆邻接表记录的是入。（不多提了）另外，十字链表就是结合了邻接表和逆邻接表，而且优于他俩的结合。

2：搜索：

2-1：DFS（深度优先搜索）
此处直接链接一下以前的文章：
DFS文章链接

2-2：BFS（广度优先搜索）
此处直接链接一下以前的文章：
BFS文章链接

3：迪杰斯特拉算法+案例解析：

此处直接链接一下以前的文章：
迪杰斯特拉算法案例链接

4：弗洛依德算法：

它跟迪杰斯特拉算法的区别就在于，迪是以一个点作为中间节点更新节点1到别的节点的权值；弗是使用邻接表矩阵以每个点为中间点，更新此点的入点到此点的出点的距离。
所以循环有三层，如下：
第一层遍历所有点，
第二层遍历此点的所有入点，
第三层遍历此点的所有出点
接着判断+更新即可（例如：A为中间点，B为A的入点，C为A的出点
BC<BA+AC或者BC不可达的话，就更新BC为BA+AC）

核心代码：

for(int i=0;i<N;i++)
    ///先遍历i的入度，即邻接表的行数
    for(int j=0;j<N;j++)
        ///接着遍历i的出度，即遍历i这一行，
        for(int k=0;k<N[i].length;k++)
            ///小于0代表不可达
            if(L[j][k]<0 || L[j][k]<L[j][i]+L[i][k])
                L[j][k] = L[j][i]+L[i][k]

噢对，还有一个拓扑排序，最短工期问题。
所谓最短工期，可以对比木桶装水问题。
木桶装水：取决于最短木条
最短工期：取决于工期最长的那条权重，在不耽误这个工期的基础上，可以研究别的工期的最晚开始时间。
所谓拓扑排序，也就是要想达到某个点，必须先把他入度的点走完才能开始。后面再加吧，先这样。
请评论多多指正文章中的错误之处，感谢。