图的应用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void MiniSpanTree_PRIMI(Graph G,int u){
    //从顶点u出发找G的最小生成树
    for (int i = 0; i <G.vexnum; ++i) {//辅助数组初始化
        if(i!=u){
            closedge[i]={u,G.arcs[u][i]};
        }        
    }
    closedge[u].lowcost=0;
    for (int j = 0; j < G.vexnum; j++) {
        k=minimum(closedge);//求生成树的下一个节点
        cout<<cloedge[k].adjvex<<G.vex[k];
        closedge[k].lowcost=0;
        for (int i = 0; i < G.vexnum; i++) {
            if (G.arc[k][j].adj<closedge[j].lowcost) {
                closedge[j]={G.vexs[k],G.arcs[k][j].adj};
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void Kruskal(Graph G){
    //定义保存一条边的权值的数组，任意两个顶点之间的边权值都可能被保存进去
    int SortVal[G.arcnum][G.arcnum];
    for (int i = 0; i < G.vexnum; i++) 
        for (int j = 0; j < G.vexnum; j++) 
            if (Adjacent(G,G.Vex[i],G.Vex[j])) {//如果存在边|弧
                SortVal[i][j]=Get_edge_value(G,G.Vex[i],G.Vex[j]);//获取权值并保存
            }
    // Paixu(SortVal);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){
    bool visited[MAX_VERTEX_NUM];
    SqQueue Q;//辅助队列
    
    int d[G.vexnum];//d[i]表示从u到i的最短路径
    int path[G.vexnum];//path[i]表示最短路径从哪个结点出来（前驱）
    for (int i = 0; i < G.vexnum; ++i) {//初始化
        d[i]=INIFINITY;
        path[i]=-1;
    }
    d[u]=0;
    visited[u]=true;
    EnQueue(Q,u);
    while(!isEmpty(Q)){
        DeQueue(Q,u);
        for (w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
            if (!visited[w]) {
                // visit(w);
                d[w]=d[u]+1;
                path[w]=u;
                visited[w]=true;
                EnQueue(Q,w);
            }//if
    }//while
}

1
2
3
4
5
6

//从V0出发，总共需要n-1轮处理
//每一轮处理：循环遍历所有个结点，找到 lowCost最低的，且还没加入树的顶点。
//再次循环遍历，更新还没加入的各个顶点的 lowCost值
bool fina[G.vexnum];//是否已经找到最短路径
int dist[G.vexnum];//最短路径长度
int path[G.vexnum];//路径上的前驱

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

//...准备工作，初始化矩阵A和path
    for (int k = 0; k < n; k++) {//考虑以Vk作为中转点
        for (int i = 0; i < n; i++) {//遍历矩阵，i为行，j为列
            for (int j = 0; j < n; j++) {
                if (A[i][j]>A[i][k]+A[k][j]) { //以Vk为中转点的路径是否更短
                    A[i][j]=A[i][k]+A[k][j];//更新最短路径长度
                    path[i][j]=k;//修改中转点
                }//if
            }
        }
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

bool TopologicalSort(Graph G){
    InitStack(S);//初始化栈，存储顶点的入度
    for (int i = 0; i < G.vexnum; i++) {
        if (indegree[i]==0) {
            Push(S,i);//入度为0的顶点入栈
        }
    }
    int count=0;//记录已经输出的顶点数
    while(!isEmpty(S)){
        Pop(S,i);
        print[count++]=i;//输出顶点i，并计数
        for (p=G.vextices[i].firstarc;p;p=p->nextarc) {
            //将所有i指向的顶点入度减1，并且将入度减为0的顶点入栈scanf
            v=p->adjvex;
            if (!(--indegree[v])) {
                Push(S,v);//入度为0，入栈
            }
        }//for
    }//while
    if (count<G.vexnum) {
        return false;//排序失败，有向图中有回路
    }else{
        return true; //成功
    }
}

1

//abababa

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

//如果图中存在回路，应该怎么判断？？
void DFSTraverse(Graph G){
    for (int i = 0; i < G.vexnum; ++i)
        visited[i]=false;
    for (int v = 0; v < G.vexnum; ++v)
        if (!visited[v])
            DFS(G,v);
}

bool TopologicalSort_DFS(Graph G,int v){
    visit(v);
    visited[v]=true;
    for (w=FirstNeighbor(G,v);w>=0;w=FirstNeighbor(G,v))//处理v的所有邻接点
        if (!visited[w]) {
            TopologicalSort_DFS(G,w);
        }
    print(v);//输出顶点    
}

1

//adada