东北大学842（8）——图编程题

邻接表的数据结构，最为常考的结构；邻接矩阵、十字链表、邻接多重表不常考，定义放在文章的最后

typedef struct ArcNode {
    int adjvex;
    struct ArcNode* next;
}ArcNode;

typedef struct {
    VertexType data;
    ArcNode* first;
}VexNode;

typedef struct {
    VexNode vexlist[MaxVexNum];
    int vexnum, arcnum;
}ALGraph；

遍历模板，能解决大部分问题

int visited[MaxVexNum];
void traverse(Graph* G) {
    for(int i = 0; i < G->vexnum; ++i) {
        visited[MaxVexNum] = 0;
    }
    for(int i = 0; i < G->vexnum; ++i) {
        if(!visited[i]) {
            /*
            这里有个重要的性质，
            对于无线图，只要一次DFS或者BFS就能遍历一个联通分量，可以靠此知道无向图连通分量个数；
            对于有向图，一次DFS或者BFS，不一定能遍历一个强连通分量。
            考试曾考过几次求无向图连通分量个数。
            */
            DFS(G, i); //BFS(G, i);
        }
    }
}

void DFS(Graph* G, int v) {
    visited[v] = 1;
    //preVisit(G, v);  放在这里是图的先序遍历
    for(int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
    /*
    没时间时候，并要求全部函数都实现的情况下，这样写。
    for(ArcNode* p = G->vexlist[v].first; p; p = p->next) {
        int w = p->adjvex;
    */
        if(!visited[w]) {
            DFS(G, w);
        }
    }
    //postVisit(G, v);  放在这里是图的后序遍历
}

void BFS(Graph* G, int v) {
    visited[v] = 1;
    visit(G, v);
    Queue Q;
    InitQueue(&Q);
    EnQueue(&Q, v);
    while(!isEmpty(&Q)) {
        v = DeQueue(&Q);
        for(int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
            if(!visited[w]) {
                visited[w] = 1;
                visit(G, w);
                EnQueue(&Q, w);
            }
        }
    }
}

BFS能解决的问题，和点v的最短路径有关，类似树的层次遍历

求出有向图、无向图点v中最短路径长度为k的所有结点
- 把点v到当前点的最短距离长度d一起入队，当d等于k时输出

DFS能解决的问题，和点src到点dst的路径相关

有向图、无向图中是否存在从src到dst的路径

有向图、无向图中打印所有从src到dst的路径

再加一个全局的栈变量，保存遍历过的路径

Stack S;
void DFS(Graph* G, int src, int dst) {
    visited[src] = 1;
    push(&S, src);
    if(src == dst) {
        //print(&S); 打印栈里面的内容
    }
    for(int v = FirstAdjVex(G, src); v >= 0; w = NextAdjVex(G, src, v)) {
        if(!visited[v]) {
            DFS(G, v);
        }
    }
    pop(&S);
}

拓扑排序模板

int endegree[MaxVexNum];
int topoSort(Graph* G) {
    //获取所有结点入度
    FindEndegree(G, endegree);
    Stack S;
    InitStack(&S);
    for(int i = 0; i < G->vexnum; ++i) {
        //入度大于0，还不能遍历；等于0，可以遍历；少于0，已经遍历过了
        if(!endegree[i]) {
            Push(&S, i);
        }
    }
    int count = 0;
    while(!IsEmpty(&S)) {
        int v = Pop(&S);
        ++count;
        //print(v);
        for(int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
            --endegree[w];
            if(!endegree[w]) {
                Push(&S, w);
            }
        }
    }
    return count >= G.vexnum
}

拓扑排序解决的问题

获取拓扑序列
有向图是否存在环
给结点标序号，要求弧<i, j>符合i<j
逆邻接表中求逆拓扑序列，用出度代替入度
对图进行深度优先后序遍历，再把所得序列用栈来颠倒一下，同样可以获得拓扑排序

邻接表中不用遍历模板的应用，当场也可以自己手写

建立邻接表
- 输入结点集合序列，边集合序列
- 输入邻接矩阵
打印邻接表存储结构信息
添加一个从src到dst的弧/边（边还要添加另外一个结点的）
删除一个从src到dst的弧/边（边还要删除另外一个节点的）
复制邻接表
构建逆邻接表

邻接矩阵

typedef struct {
    VertexType vexlist[MaxVexNum];
    ArcType arcTable[MaxVexNum][MaxVexNum];
    int vexnum, arcnum;
}MGraph;

十字链表，有向图

typedef struct ArcNode {
    int tailvex, headvex;
    struct ArcNode* tlink, * hlink;
}ArcNode;

typedef struct {
    VertexType data;
    ArcNode* firstin, * firstout;
}VexNode;

typedef struct {
    VexNode vexlist[MaxVexNum];
    int vexnum, arcnum;
}GLGraph;

邻接多重表，无向图

typedef struct ArcNode {
    //int marked; 访问标记
    int ivex, jvex;
    struct ArcNode* ilink, * jlink;
}ArcNode;

typedef struct {
    VertexType data;
    ArcNode* first;
}VexNode;

typedef struct {
    VexNode vexlist[MaxVexNum];
    int vexnum, arcnum;
}AMLGraph；