【数据结构】——【图】算法代码实现（C/C++语言实现）（整理不易，请多关注）

目录

1.用图邻接矩阵表示实现的一些基本运算

2.用图邻接表表示实现的一些基本运算

3.用邻接矩阵表示的图的广度优先遍历算法

4.用邻接表表示的图的广度优先遍历算法

5.用邻接矩阵表示的图的深度优先遍历的递归算法

6.用邻接矩阵表示的图的深度优先遍历的非递归算法

7.用邻接表表示的图的深度优先遍历的非递归算法

8.用邻接矩阵表示的图的Kruskal算法

9.用邻接矩阵表示的图的prim算法

10.用邻接矩阵表示的图的Dijkstra算法

11.用邻接矩阵表示的图的Floyd算法

12.用邻接表表示图的拓扑排序算法

13.用邻接矩阵表示图的拓扑排序算法

14.图的关键路径问题的算法

1.用图邻接矩阵表示实现的一些基本运算

#define MAXVEX 20
#define NON -1

typedef char VexType;

typedef float AdjType;

typedef struct {
    int n;                                 
    VexType vexs[MAXVEX];                 
    AdjType arcs[MAXVEX][MAXVEX];           
} GraphMatrix;

int firstVertex(GraphMatrix* pgraph) 
{    
    return pgraph->n == 0 ? NON : 0;
}

int nextVertex(GraphMatrix* pgraph,int n) 
{    
    return n == pgraph->n-1 ? NON : n+1;
}

int firstAdjacent(GraphMatrix* pgraph, int i) 
{
    int k;
    for (k = 0; k < pgraph->n; k++)
        if(pgraph->arcs[i][k] != 0) return k;
    return NON; 
}  

int  nextAdjacent(GraphMatrix* pgraph, int i, int j) 
{
    int k;
    for (k = j+1; k < pgraph->n; k++)
        if (pgraph->arcs[i][k] != 0) return k;
    return NON; 
}   


int main() 
{
    return 0;
}

2.用图邻接表表示实现的一些基本运算

#include
#define MAXVEX 20
#define NON -1

typedef char VexType;

typedef float AdjType;

typedef int Vertex;

struct EdgeNode;
typedef struct EdgeNode * PEdgeNode;
typedef struct EdgeNode * EdgeList;

struct EdgeNode {
    int endvex;                
    AdjType weight;            
    PEdgeNode nextedge;        
};                          
                                      
typedef struct {
    VexType vertex;            
    EdgeList edgelist; 
} VexNode;               

typedef struct {
        int n;                         
        VexNode vexs[MAXVEX];
} GraphList;

int firstVertex(GraphList* pgraph) 
{    
    return pgraph->n == 0 ? NON : 0;
}

int nextVertex(GraphList* pgraph,int n) 
{    
    return n == pgraph->n-1 ? NON : n+1;
}

int firstAdjacent(GraphList* pgraph, int i) 
{
    if (pgraph->vexs[i].edgelist != NULL)
        return pgraph->vexs[i].edgelist->endvex;
    else return NON; 
}  

int nextAdjacent(GraphList* pgraph, int i, int j) 
{
    PEdgeNode p;
    for (p = pgraph->vexs[i].edgelist; p != NULL; p = p->nextedge)
        if (p->endvex == j) 
{
            if (p->nextedge != NULL)
                return p->nextedge->endvex;
            else 
                return NON;
        }
    return NON; 
}   


int main()  
{
    return 0;
}

3.用邻接矩阵表示的图的广度优先遍历算法

#include
#include

#define MAXVEX 6
#define MAX 0

typedef char VexType;
typedef float AdjType;

typedef struct {
    int n;                                           
    
    AdjType arcs[MAXVEX][MAXVEX];           
} GraphMatrix;

#define  MAXNUM   8
typedef int DataType;
struct  SeqQueue {             
    int  f, r;
    DataType  q[MAXNUM];
};

typedef  struct SeqQueue  *PSeqQueue; 

PSeqQueue  createEmptyQueue_seq( void ) 
{  
    PSeqQueue paqu;
    paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    if (paqu == NULL)
        printf("Out of space!! n");
    else 
        paqu->f = paqu->r = 0;

    return paqu;
}

int isEmptyQueue_seq( PSeqQueue paqu ) 
{
    return paqu->f == paqu->r;
}


void  enQueue_seq( PSeqQueue paqu, DataType x ) 
{
    if( (paqu->r + 1) % MAXNUM == paqu->f  )
        printf( "Full queue.n" );
    else {
        paqu->q[paqu->r] = x;
        paqu->r = (paqu->r + 1) % MAXNUM;
    }
}


void  deQueue_seq( PSeqQueue paqu ) 
{
    if( paqu->f == paqu->r )
        printf( "Empty Queue.n" );
    else
        paqu->f = (paqu->f + 1) % MAXNUM;
}


DataType  frontQueue_seq( PSeqQueue paqu ) 
{
    return (paqu->q[paqu->f]);
}

#define NON  -1

int firstVertex(GraphMatrix* pgraph) 
{    
    if (pgraph->n == 0)
        return NON;
    else return 0;

}

int nextVertex(GraphMatrix* pgraph,int n) 
{    
    if (n == pgraph->n-1)
        return NON;
    else return n + 1;
}

int firstAdjacent(GraphMatrix* pgraph, int i) 
{
    int k;
    for (k = 0; k < pgraph->n; k++)
        if(pgraph->arcs[i][k] != 0) return k;
    return NON; 
}  


int nextAdjacent(GraphMatrix* pgraph, int i, int j) 
{
    int k;
    for (k = j+1; k < pgraph->n; k++)
        if (pgraph->arcs[i][k] != 0) return k;
    return NON; 
}   

typedef int Vertex;
#define TRUE 1
#define FALSE 0

int visited[MAXVEX];

void bfs ( GraphMatrix* g , Vertex v );
void bft ( GraphMatrix* g ) 
{
    Vertex v ;
    for ( v =firstVertex ( g ) ; v != NON ; v = nextVertex ( g , v ) )
        if ( visited[v] == FALSE ) bfs ( g , v ) ;
} 

void bfs ( GraphMatrix* g , Vertex v ) 
{
    Vertex v1 , v2;
    PSeqQueue q = createEmptyQueue_seq();       

    enQueue_seq ( q, v ) ;
    printf("%d ", v);
    visited[v] = TRUE ;

while ( !isEmptyQueue_seq(q) ) 
{
        v1 = frontQueue_seq ( q ) ;
        deQueue_seq ( q );
        v2 = firstAdjacent ( g, v1 );

        while ( v2!= NON ) {
            if ( visited[v2] == FALSE ) 
{
                enQueue_seq ( q,  v2 );
                visited[v2] = TRUE ;
                printf("%d ", v2);
            }
            v2 = nextAdjacent ( g, v1 , v2 ) ;
        }
    }
}

GraphMatrix graph = {
    6,
    {{0,10,MAX,MAX,19,21},
     {10,0,5,6,MAX,11},
     {MAX,5,0,6,MAX,MAX},
     {MAX,6,6,0,18,14},
     {19,MAX,MAX,18,0,33},
     {21,11,MAX,14,33,0}
    }
};

int main()
{
    bft(&graph);
    return 0;
}

4.用邻接表表示的图的广度优先遍历算法

#include
#include
#define MAXVEX 20

typedef struct EdgeNode EdgeNode;
typedef struct EdgeNode * PEdgeNode;
typedef struct EdgeNode * EdgeList;
struct EdgeNode {
    int endvex;                
    PEdgeNode nextedge;        
};                                            
typedef struct {
                   
    EdgeList edgelist;         
} VexNode;                            

typedef struct {
    int n;                            
    VexNode vexs[MAXVEX];
} GraphList;


void insert(GraphList* p,int a,int b) 
{
    EdgeList pp;
    PEdgeNode temp;
    temp = (PEdgeNode)malloc(sizeof(EdgeNode));
    temp->endvex = b;
    temp->nextedge = NULL;
    pp = p->vexs[a].edgelist;
        if (pp == NULL)
        p->vexs[a].edgelist = temp;
    else {
        while(pp->nextedge != NULL)
            pp = pp->nextedge;
        pp->nextedge = temp;
    }
}
        

GraphList* makeList() 
{
    GraphList* p;
    int i;
    p = (GraphList*)malloc(sizeof(GraphList));
    p->n = 8;
    for (i = 0; i < p->n; i++)
        p->vexs[i].edgelist = NULL;
    insert(p,0,1);
    insert(p,0,2);
    insert(p,1,3);
    insert(p,1,4);
    insert(p,2,5);
    insert(p,2,6);
    insert(p,3,7);
    insert(p,4,7);
    insert(p,5,6);
    return p;
}


#define  MAXNUM   20
typedef int DataType;
struct SeqQueue {              
    int  f, r;
    DataType  q[MAXNUM];
};

typedef  struct SeqQueue  *PSeqQueue; 

PSeqQueue  createEmptyQueue_seq( void ) 
{  
    PSeqQueue paqu;
    paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    if (paqu == NULL)
        printf("Out of space!! n");
    else 
        paqu->f = paqu->r = 0;

    return paqu;
}

int isEmptyQueue_seq( PSeqQueue paqu ) 
{
    return paqu->f == paqu->r;
}


void  enQueue_seq( PSeqQueue paqu, DataType x ) 
{
    if( (paqu->r + 1) % MAXNUM == paqu->f  )
        printf( "Full queue.n" );
else 
{
        paqu->q[paqu->r] = x;
        paqu->r = (paqu->r + 1) % MAXNUM;
    }
}


void  deQueue_seq( PSeqQueue paqu ) 
{
    if( paqu->f == paqu->r )
        printf( "Empty Queue.n" );
    else
        paqu->f = (paqu->f + 1) % MAXNUM;
}


DataType  frontQueue_seq( PSeqQueue paqu ) 
{
    return (paqu->q[paqu->f]);
}


#define NON -1

int  firstVertex(GraphList* pgraph) 
{    
    if (pgraph->n == 0)
        return NON;
    else return 0;
}

int  nextVertex(GraphList* pgraph,int n) 
{    
    if (n == pgraph->n - 1)
        return NON;
    else return n+1;
}

int  firstAdjacent(GraphList* pgraph, int i) 
{
    if (pgraph->vexs[i].edgelist != NULL)
        return pgraph->vexs[i].edgelist->endvex;
    else return NON; 
}  

int nextAdjacent(GraphList* pgraph, int i, int j) 
{
    PEdgeNode p;
    for (p = pgraph->vexs[i].edgelist; p != NULL; p = p->nextedge)
        if (p->endvex == j) 
{
            if (p->nextedge != NULL)
                return p->nextedge->endvex;
            else 
                return NON;
        }
    return NON; 
}   

typedef int Vertex;
#define TRUE 1
#define FALSE 0

int visited[MAXVEX];

void bfs ( GraphList* g , Vertex v );
void bft ( GraphList* g ) 
{
    Vertex v ;
    for ( v = firstVertex ( g ) ; v != NON ; v = nextVertex ( g , v ) )
        if ( visited[v] == FALSE ) bfs ( g , v ) ;
} 

void bfs ( GraphList* g , Vertex v ) 
{
    Vertex v1 , v2;
    PSeqQueue q  = createEmptyQueue_seq ( ) ;   

    enQueue_seq ( q ,v ) ;
    printf("%d ",v);
    visited[v] = TRUE ;

while ( !isEmptyQueue_seq(q) ) 
{
        v1 = frontQueue_seq ( q ) ;
        deQueue_seq ( q );
        v2 = firstAdjacent ( g ,v1 );

        while ( v2 != NON ) {
            if ( visited[v2] == FALSE ) 
{
                enQueue_seq ( q,  v2 );
                visited[v2] = TRUE ;
                printf("%d ",v2);
            }
            v2 = nextAdjacent ( g , v1 , v2 ) ;
        }
    }
}

int main()
{
    GraphList* p = makeList();
    bft(p);
    return 0;
}

5.用邻接矩阵表示的图的深度优先遍历的递归算法

#include
#define MAXVEX 6
#define MAX 0
#define NON -1

typedef char VexType;
typedef float AdjType;

typedef struct {
    int n;                                           
    
    AdjType arcs[MAXVEX][MAXVEX];           
} GraphMatrix;


int  firstVertex(GraphMatrix* pgraph) 
{    
    if (pgraph->n == 0)
        return NON;
    else return 0;
}

int  nextVertex(GraphMatrix* pgraph,int n) 
{    
    if (n == pgraph->n-1)
        return NON;
    else return n+1;
}

int  firstAdjacent(GraphMatrix* pgraph, int i) 
{
    int k;
    for (k = 0; k < pgraph->n; k++)
        if (pgraph->arcs[i][k] != 0) return k;
    return NON; 
}  

int  nextAdjacent(GraphMatrix* pgraph, int i, int j) 
{
    int k;
    for(k=j+1; kn; k++)
        if(pgraph->arcs[i][k]!=0) return k;
    return NON; 
}   

typedef int Vertex;
#define TRUE 1
#define FALSE 0

int visited[MAXVEX];
void dfs ( GraphMatrix* g , Vertex v );

void dft ( GraphMatrix* g ) 
{
    Vertex v ;
    for ( v =firstVertex ( g ) ; v != NON ; v = nextVertex ( g , v ) )
        if ( visited[v] == FALSE ) dfs ( g , v ) ;
}

void dfs ( GraphMatrix* g , Vertex v ) 
{
    Vertex v1;
    visited[v] = TRUE ;
    printf("%d ",v);
    for ( v1 = firstAdjacent(g , v); v1 != NON ; v1=nextAdjacent(g ,v, v1) )
        if(visited[v1]==FALSE) dfs ( g ,v1 );
}

GraphMatrix graph = {
    6,
    {{0,10,MAX,MAX,19,21},
     {10,0,5,6,MAX,11},
     {MAX,5,0,6,MAX,MAX},
     {MAX,6,6,0,18,14},
     {19,MAX,MAX,18,0,33},
     {21,11,MAX,14,33,0}
    }
};

int main()
{
    dft(&graph);
    return 0;
}

6.用邻接矩阵表示的图的深度优先遍历的非递归算法

#include
#include

#define MAXVEX 6
#define MAX 0
#define  NON  -1

typedef char VexType;
typedef float AdjType;

typedef struct {
    int n;                                           
    
    AdjType arcs[MAXVEX][MAXVEX];           
} GraphMatrix;


int  firstVertex(GraphMatrix* pgraph) 
{    
    if(pgraph->n == 0)
        return NON;
    else return 0;
}

int  nextVertex(GraphMatrix* pgraph,int n) 
{    
    if(n==pgraph->n-1)
        return NON;
    else return n+1;
}

int  firstAdjacent(GraphMatrix* pgraph, int i) 
{
    int k;
    for(k=0;kn;k++)
        if(pgraph->arcs[i][k]!=0) return k;
    return NON; 
}  

int  nextAdjacent(GraphMatrix* pgraph, int i, int j) 
{
    int k;
    for(k=j+1; kn; k++)
        if(pgraph->arcs[i][k]!=0) return k;
    return NON; 
}   

typedef int Vertex;
#define TRUE 1
#define FALSE 0

typedef struct {
    Vertex v;
    Vertex k;
} DataType;

#define MAXNUM 20     
struct  SeqStack {       
        int  t;                        
        DataType  s[MAXNUM];
};

typedef  struct SeqStack  *PSeqStack; 


PSeqStack  createEmptyStack_seq( void ) 
{
    PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
    if (pastack == NULL)
        printf("Out of space!! n");
    else
        pastack->t = -1;
    return  (pastack);
}


int  isEmptyStack_seq( PSeqStack pastack ) 
{
    return pastack->t == -1;
}


void  push_seq( PSeqStack pastack, DataType x ) 
{
    if( pastack->t >= MAXNUM - 1  )
        printf( "Overflow! n" );
    else {
        pastack->t++;
        pastack->s[pastack->t] = x;
    }
}


void  pop_seq( PSeqStack pastack ) 
{
    if (pastack->t == -1 )
        printf( "Underflow!n" );
    else
        pastack->t--;
}


DataType  top_seq( PSeqStack pastack ) 
{
    return pastack->s[pastack->t];
}

int visited[MAXVEX];
void dfs ( GraphMatrix* g , Vertex v );

void dft ( GraphMatrix* g ) 
{
    Vertex v ;
    for ( v = firstVertex ( g ) ; v != NON ; v = nextVertex ( g , v ) )
        if ( visited[v] == FALSE ) dfs ( g , v ) ;
}

void dfs ( GraphMatrix* g , Vertex v ) 
{
    DataType element;
    Vertex v1,v2;
    PSeqStack s ;       
    s = createEmptyStack_seq ( ) ;
    element.v = v;
    element.k = firstAdjacent(g, v);
    push_seq ( s, element) ;
    printf("%d ", v);
    visited[v] = TRUE ;
while ( !isEmptyStack_seq(s) ) 
{
        element = top_seq ( s ) ;
        pop_seq ( s );
        v1 = element.v;
        v2 = element.k;
        while (v2 != NON ) {
            if ( visited[v2] == FALSE ) 
{
                element.v = v1;
                element.k = v2;
                push_seq ( s,  element);
                visited[v2] = TRUE ;
                printf("%d ", v2);
                v1 = v2;
                v2 = firstAdjacent(g, v1);
            }
            else v2 = nextAdjacent(g , v1 , v2) ;
        }
    }
}

GraphMatrix graph = {
    6,
    {{0,10,MAX,MAX,19,21},
     {10,0,5,6,MAX,11},
     {MAX,5,0,6,MAX,MAX},
     {MAX,6,6,0,18,14},
     {19,MAX,MAX,18,0,33},
     {21,11,MAX,14,33,0}
    }
};

int main(){
    dft(&graph);
    return 0;
}

7.用邻接表表示的图的深度优先遍历的非递归算法

#include
#include
#define MAXVEX 20

typedef struct EdgeNode EdgeNode;
typedef struct EdgeNode * PEdgeNode;
typedef struct EdgeNode * EdgeList;
struct EdgeNode {
    int endvex;                
    PEdgeNode nextedge;        
};                                    

typedef struct {
                   
    EdgeList edgelist;         
} VexNode;                            

typedef struct {
    int n;                            
    VexNode vexs[MAXVEX];
} GraphList;


void insert(GraphList* p,int a,int b) 
{
    EdgeList pp;
    PEdgeNode temp;
    temp = (PEdgeNode)malloc(sizeof(EdgeNode));
    temp->endvex = b;
    temp->nextedge = NULL;
    pp = p->vexs[a].edgelist;
    if (pp == NULL)
        p->vexs[a].edgelist = temp;
    else {
        while (pp->nextedge != NULL)
            pp = pp->nextedge;
        pp->nextedge = temp;
    }
}
        

GraphList* makeList() 
{
    GraphList* p;
    int i;
    p = (GraphList*)malloc(sizeof(GraphList));
    p->n = 8;
    for (i = 0; i < p->n; i++)
        p->vexs[i].edgelist = NULL;
    insert(p,0,1);
    insert(p,0,2);
    insert(p,1,3);
    insert(p,1,4);
    insert(p,2,5);
    insert(p,2,6);
    insert(p,3,7);
    insert(p,4,7);
    insert(p,5,6);
    return p;
}

#define NON  -1

int firstVertex(GraphList* pgraph) 
{
    if(pgraph->n == 0)
        return NON;
    else return 0;
}

int  nextVertex(GraphList* pgraph,int n) 
{    
    if (n == pgraph->n - 1)
        return NON;
    else return n+1;
}

int firstAdjacent(GraphList* pgraph, int i) 
{
    if(pgraph->vexs[i].edgelist != NULL)
        return pgraph->vexs[i].edgelist->endvex;
    else return NON; 
}  

int nextAdjacent(GraphList* pgraph, int i, int j) 
{
    PEdgeNode p;
    for(p = pgraph->vexs[i].edgelist; p != NULL; p = p->nextedge)
        if(p->endvex==j) {
            if(p->nextedge!=NULL)
                return p->nextedge->endvex;
            else 
                return NON;
        }
    return NON; 
}

typedef int Vertex;
#define TRUE 1
#define FALSE 0

typedef struct {
    Vertex v;
    Vertex k;
} DataType;

#define MAXNUM 20   
struct  SeqStack {     
    int  t;            
    DataType  s[MAXNUM];
};

typedef  struct SeqStack  *PSeqStack;  


PSeqStack  createEmptyStack_seq( void ) 
{
    PSeqStack pastack;
    pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
    if (pastack == NULL)
        printf("Out of space!n");
    else
        pastack->t = -1;
    return  (pastack);
}


int  isEmptyStack_seq( PSeqStack pastack ) 
{
    return pastack->t == -1;
}


void  push_seq( PSeqStack pastack, DataType x ) 
{
    if( pastack->t >= MAXNUM - 1  )
        printf( "Overflow! n" );
    else {
        pastack->t++;
        pastack->s[pastack->t] = x;
    }
}


void  pop_seq( PSeqStack pastack ) 
{
    if (pastack->t == -1 )
        printf( "Underflow!n" );
    else
        pastack->t--;
}


DataType  top_seq( PSeqStack pastack ) {
    return (pastack->s[pastack->t]);
}


int visited[MAXVEX];

void dfs ( GraphList* g , Vertex v );

void dft ( GraphList* g ) {
    Vertex v ;
    for ( v = firstVertex ( g ) ; v != NON ; v = nextVertex ( g , v ) )
        if ( visited[v] == FALSE ) dfs ( g , v ) ;
}

void dfs ( GraphList* g , Vertex v ) 
{
    DataType element;
    Vertex v1, v2;
    PSeqStack s ;       
    s = createEmptyStack_seq ( ) ;
    element.v = v;
    element.k = firstAdjacent(g, v);
    push_seq(s ,element) ;
    printf("%d ", v);
    visited[v] = TRUE ;
while ( !isEmptyStack_seq(s) ) 
{
        element = top_seq ( s ) ;
        pop_seq ( s );
        v1 = element.v;
        v2 = element.k;
        while (v2 != NON ) {
            if ( visited[v2] == FALSE ) 
{
                element.v = v1;
                element.k = v2;
                push_seq (s, element);
                visited[v2] = TRUE ;
                printf("%d ", v2);
                v1 = v2;
                v2 = firstAdjacent(g, v1);
            }
            else 
                v2 = nextAdjacent(g , v1 , v2) ;
        }
    }
}

int main()
{
    GraphList* p = makeList();
    dft(p);
    return 0;
}

8.用邻接矩阵表示的图的Kruskal算法

#include
#define MAXVEX 6

typedef char VexType;

typedef float AdjType;

typedef struct {
    int n;                          
    
    AdjType arcs[MAXVEX][MAXVEX];   
} GraphMatrix;

typedef struct{
    int start_vex, stop_vex;        
    AdjType weight;                 
} Edge;

Edge mst[5];

#define MAX 1e+8

void prim(GraphMatrix * pgraph, Edge mst[]) 
{
    int i, j, min, vx, vy; 
    float weight, minweight; Edge edge;

for (i = 0; i < pgraph->n-1; i++) 
{
        mst[i].start_vex = 0;
        mst[i].stop_vex = i+1;
        mst[i].weight = pgraph->arcs[0][i+1];
    }

for (i = 0; i < pgraph->n-1; i++) 
{               
        minweight = MAX;  min = i;
        for (j = i; j < pgraph->n-1; j++)
            if(mst[j].weight < minweight) 
{
                minweight = mst[j].weight; 
                min = j;
            }

        
        edge = mst[min];  
        mst[min] = mst[i];   
        mst[i] = edge;
        vx = mst[i].stop_vex;            

        for(j = i+1; j < pgraph->n-1; j++) { 
            vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy];
            if (weight < mst[j].weight) {
                mst[j].weight = weight;  
                mst[j].start_vex = vx;
            }
        }
    }
}

GraphMatrix graph = {
    6,
    {{0,10,MAX,MAX,19,21},
     {10,0,5,6,MAX,11},
     {MAX,5,0,6,MAX,MAX},
     {MAX,6,6,0,18,14},
     {19,MAX,MAX,18,0,33},
     {21,11,MAX,14,33,0}
    }
};

int main()
{
    int i;
    prim(&graph,mst);
    for (i = 0; i < graph.n-1; i++)
        printf("(%d %d %.0f)n", mst[i].start_vex,
                mst[i].stop_vex, mst[i].weight);
    return 0;
}

9.用邻接矩阵表示的图的prim算法

#include
#include
#define MAXVEX 6
enum{FALSE,TRUE};

typedef char VexType;
typedef float AdjType;

typedef struct {
    int n;                                           
    
    AdjType arcs[MAXVEX][MAXVEX];           
} GraphMatrix;

typedef struct {
    int start_vex, stop_vex;              
    AdjType weight;                  
} Edge;

Edge mst[5];


#define MAX 1e+8

int kruskal(GraphMatrix  graph, Edge mst[]) 
{   
    int i, j, num = 0, start, stop;
    float minweight;
    int* status = (int *)malloc(sizeof(int)*graph.n);
    for (i = 0; i < graph.n; i++)
        status[i] = i;
    while (num < graph.n - 1){
        minweight = MAX;
        for (i = 0; i < graph.n-1; i++)
            for (j = i+1; j < graph.n; j++)
                if (graph.arcs[i][j] < minweight)
{
                    start = i; stop = j;
                    minweight = graph.arcs[i][j];
                }
        if (minweight == MAX) return FALSE;
        
        if (status[start] != status[stop])
{
            mst[num].start_vex = start;
            mst[num].stop_vex = stop;
            mst[num].weight = graph.arcs[start][stop];
            num++;
            j = status[stop];
            for (i = 0; i < graph.n; i++)     
                if(status[i] == j)
                    status[i] = status[start];
        }
        
        graph.arcs[start][stop] = MAX;
    }          
    return TRUE;
}

GraphMatrix graph = {
    6,
    {{0,10,MAX,MAX,19,21},
     {10,0,5,6,MAX,11},
     {MAX,5,0,6,MAX,MAX},
     {MAX,6,6,0,18,14},
     {19,MAX,MAX,18,0,33},
     {21,11,MAX,14,33,0}
    }
};

int main()
{
    int i;
    if (kruskal(graph,mst) == TRUE)
        for (i = 0; i < graph.n-1; i++)
            printf("(%d %d %.0f)n", mst[i].start_vex,
                mst[i].stop_vex, mst[i].weight);
    return 0;
}

10.用邻接矩阵表示的图的Dijkstra算法

#include
#define MAXVEX    100
                       
typedef char VexType;
typedef float AdjType;

typedef struct {
    int n;                                           
    VexType vexs[MAXVEX];                   
    AdjType arcs[MAXVEX][MAXVEX];           
} GraphMatrix;

typedef struct {
    VexType vertex;        
    AdjType length;        
    int prevex;           
} Path;

Path dist[6];                    

#define MAX 1e+8

void init(GraphMatrix* pgraph, Path dist[]) 
{
    int i; 
    dist[0].length = 0;
    dist[0].prevex = 0;      
    dist[0].vertex = pgraph->vexs[0];

    pgraph->arcs[0][0] = 1;                    

for(i = 1; i < pgraph->n; i++) 
{             
        dist[i].length=pgraph->arcs[0][i];
        dist[i].vertex=pgraph->vexs[i];
        if (dist[i].length != MAX)
            dist[i].prevex=0;
        else  dist[i].prevex= -1;
    }
}


void dijkstra(GraphMatrix graph, Path dist[]) 
{
    int i,j,minvex;
    AdjType min;
        init(&graph,dist); 
for(i = 1; i < graph.n; i++) 
{
        min=MAX;       minvex=0;
        for (j = 1; j < graph.n; j++) 
            if( graph.arcs[j][j] == 0 && dist[j].length < min ) 
{
                min=dist[j].length;  minvex=j;  
            }

        if(minvex == 0) break; 
        graph.arcs[minvex][minvex] = 1;       
        for (j = 1; j < graph.n; j++) 
{      
            if(graph.arcs[j][j] == 1)  continue;
            if(dist[j].length > dist[minvex].length + graph.arcs[minvex][j]) 
{
                dist[j].length = dist[minvex].length + graph.arcs[minvex][j];
                dist[j].prevex = minvex;
            }
        }
    }
}

GraphMatrix graph;

void initgraph()
{
    int i,j;
    graph.n=6;
    for (i = 0; i < graph.n; i++)
        for (j = 0; j < graph.n; j++)
            graph.arcs[i][j] = (i == j ? 0 : MAX);
    graph.arcs[0][1] = 50;
    graph.arcs[0][2] = 10;
    graph.arcs[1][2] = 15;
    graph.arcs[1][4] = 5;
    graph.arcs[2][0] = 20;
    graph.arcs[2][3] = 15;
    graph.arcs[3][1] = 20;
    graph.arcs[3][4] = 35;
    graph.arcs[4][3] = 30;
    graph.arcs[5][3] = 3;
    graph.arcs[0][4] = 45;
}

int main()
{
    int i;
    initgraph();
    dijkstra(graph, dist);
    for (i = 0; i < graph.n; i++)
        printf("(%.0f %d)", dist[i].length,dist[i].prevex);
    return 0;
}

11.用邻接矩阵表示的图的Floyd算法

#include
#define MAXVEX  100
#define MAX 1e+8                         

typedef char VexType;
typedef float AdjType;

typedef struct {
    int n;                                           
    VexType vexs[MAXVEX];                   
    AdjType arcs[MAXVEX][MAXVEX];           
} GraphMatrix;

typedef struct {
    AdjType a[MAXVEX][MAXVEX];
    int nextvex[MAXVEX][MAXVEX];
                
} ShortPath;

void floyd(GraphMatrix * pgraph, ShortPath * ppath) 
{
    int i, j, k;

    for (i = 0; i < pgraph->n; i++)
        for (j = 0; j < pgraph->n; j++) 
{
            if (pgraph->arcs[i][j] != MAX) 
                ppath->nextvex[i][j] = j;
            else ppath->nextvex[i][j] = -1;

            ppath->a[i][j] = pgraph->arcs[i][j];
        }

    for (k = 0; k < pgraph->n; k++)
        for (i = 0; i < pgraph->n; i++)
            for (j = 0; j < pgraph->n; j++) 
{ 
                if ( ppath->a[i][k] >= MAX || ppath->a[k][j] >= MAX )
                    continue;
                if ( ppath->a[i][j] > ppath->a[i][k]+ ppath->a[k][j] ) {
                    ppath->a[i][j] = ppath->a[i][k] + ppath->a[k][j];
                    ppath->nextvex[i][j] = ppath->nextvex[i][k];
                }
            }
}


GraphMatrix graph;
ShortPath path;

void init()
{
    int i,j;
    graph.n = 6;
    for(i = 0; i < graph.n; i++)
        for(j = 0; j < graph.n; j++)
            graph.arcs[i][j] = (i == j ? 0 : MAX);
    graph.arcs[0][1] = 50;
    graph.arcs[0][2] = 10;
    graph.arcs[1][2] = 15;
    graph.arcs[1][4] = 5;
    graph.arcs[2][0] = 20;
    graph.arcs[2][3] = 15;
    graph.arcs[3][1] = 20;
    graph.arcs[3][4] = 35;
    graph.arcs[4][3] = 30;
    graph.arcs[5][3] = 3;
    graph.arcs[0][4] = 45;
}

int main()
{
    int i,j;
    init();
    floyd(&graph, &path);
for (i = 0; i < graph.n; i++)
{
        for (j = 0; j < graph.n; j++)
            printf("%d ", path.nextvex[i][j]);
        putchar('n');
    }
    return 0;
}

12.用邻接表表示图的拓扑排序算法

#include
#include
#define MAXVEX 100
#define TRUE 1
#define FALSE 0

typedef struct EdgeNode EdgeNode;
typedef struct EdgeNode * PEdgeNode;
typedef struct EdgeNode * EdgeList;

struct EdgeNode {
    int endvex;                
    PEdgeNode nextedge;        
};                                    

typedef struct {
                   
    EdgeList edgelist;         
} VexNode;                            

typedef struct{
    int n;                            
    VexNode vexs[MAXVEX];
} GraphList;

typedef struct {
    int vexsno[MAXVEX];               
       
} Topo;



void findInDegree(GraphList* g, int *inDegree)
{
    int i; PEdgeNode p;        
    for (i = 0; i < g->n; i++)
        inDegree[i] = 0;
for (i = 0; i < g->n; i++)
{
        p = g->vexs[i].edgelist;
        while (p) 
{
            ++inDegree[p->endvex];
            p = p->nextedge;
        }
    }
}

void makeNewAOV(EdgeList p, int* indegree, int* top) 
{
    int k;
while (p) 
{                        
        k = p->endvex; 
        indegree[k]--;
        if (indegree[k] == 0) 
{        
            indegree[k] = *top;
            *top = k; 
        }
        p = p->nextedge;
    }
}

int topoSort(GraphList * paov, Topo * ptopo) 
{
    EdgeList p;
    int i, j, nodeno = 0, top = -1;
    int indegree[MAXVEX];
    findInDegree(paov, indegree); 
    for (i = 0; i < paov->n; i++)
        if (indegree[i] == 0) 
{          
            indegree[i] = top; top = i; 
        }
        while (top != -1) 
{                           
            j = top;
            top = indegree[top];               
             
            ptopo->vexsno[nodeno++] = j;
            p = paov->vexs[j].edgelist;    
            
            
            makeNewAOV(p, indegree, &top);
        }
        if (nodeno < paov->n) 
{      
            printf("The aov network has a cyclen");
            return FALSE;
        }
    return TRUE;
}


void insert(GraphList* p,int a,int b)
{
    EdgeList pp;
    PEdgeNode temp;
    temp = (PEdgeNode)malloc(sizeof(EdgeNode));
    temp->endvex = b;
    temp->nextedge = NULL;
    pp = p->vexs[a].edgelist;
    if (pp == NULL) p->vexs[a].edgelist = temp;
    else {
        while (pp->nextedge != NULL)
            pp = pp->nextedge;
        pp->nextedge = temp;
    }
}
        

GraphList* makeList()
{
    GraphList* p;
    int i;
    p = (GraphList*)malloc(sizeof(GraphList));
    p->n = 9;
    for (i = 0; i < p->n; i++)
        p->vexs[i].edgelist = NULL;
    insert(p, 0, 2);
    insert(p, 0, 7);
    insert(p, 1, 2);
    insert(p, 1, 3);
    insert(p, 1, 4);
    insert(p, 2, 3);
    insert(p, 3, 5);
    insert(p, 3, 6);
    insert(p, 4, 5);
    insert(p, 7, 8);
    insert(p, 8, 6);
    return p;
}

Topo topo;

int main()
{
    GraphList* p;
    int i;
    p = makeList();
    if (topoSort(p, &topo) == TRUE)
        for (i = 0; i < p->n; i++)
            printf("%d ", topo.vexsno[i]);
    return 0;
}

13.用邻接矩阵表示图的拓扑排序算法

#include
#include
#define MAXVEX 100
#define TRUE 1
#define FALSE 0
                                      
typedef char VexType;
typedef int AdjType;
typedef struct {
    int n;                                                           
                            
    AdjType arcs[MAXVEX][MAXVEX];             
} GraphMatrix;

typedef struct {
       
    int vexsno[MAXVEX];               
} Topo;



void findInDegree(GraphMatrix* g, int *inDegree) 
{
    int i, j;       
for (i = 0; i < g->n; i++) 
{
        inDegree[i] = 0;
        for (j = 0; j < g->n; j++)
            if (g->arcs[j][i]) ++inDegree[i];
    }
}

void makeNewAOV(GraphMatrix* g, int p, int* indegree, int* top) 
{
    int k;
    for (k = 0; k < g->n; k++)
        if (g->arcs[p][k]) {
            indegree[k]--;
            if (indegree[k] == 0) 
{         
                indegree[k] = *top;
                *top = k; 
            }
        }
}

int topoSort(GraphMatrix * paov, Topo * ptopo) 
{
    int i, j, nodeno = 0, top = -1;
    int indegree[MAXVEX];

    findInDegree(paov, indegree); 

    for (i = 0; i < paov->n; i++)
        if (indegree[i] == 0) 
{           
            indegree[i] = top; top = i;
        }

while (top != -1) 
{                           
        j = top;
        top = indegree[top];               
         
        ptopo->vexsno[nodeno++] = j;
        
        
        
        makeNewAOV(paov, j, indegree, &top);
    }
if (nodeno < paov->n) 
{        
        printf("The aov network has a cyclen");
        return FALSE;
    }
    return TRUE;
}


GraphMatrix* makeMatrix()
{
    GraphMatrix* p;
    int i,j;
    p = (GraphMatrix*)malloc(sizeof(GraphMatrix));
    p->n = 9;
    for (i = 0; i < p->n; i++)
        for (j = 0; j < p->n; j++)
            p->arcs[i][j] = 0;
    p->arcs[0][2] = 1;
    p->arcs[0][7] = 1;
    p->arcs[1][2] = 1;
    p->arcs[1][3] = 1;
    p->arcs[1][4] = 1;
    p->arcs[2][3] = 1;
    p->arcs[3][5] = 1;
    p->arcs[3][6] = 1;
    p->arcs[4][5] = 1;
    p->arcs[7][8] = 1;
    p->arcs[8][6] = 1;
    return p;
}

Topo topo;

int main()
{
    int i;
    GraphMatrix* p;
    p = makeMatrix();
    if (topoSort(p, &topo) == TRUE)
        for (i = 0; i < p->n; i++)
            printf("%d ", topo.vexsno[i]);
    return 0;
}

14.图的关键路径问题的算法

#include
#include
#define MAXVEX 100
#define TRUE 1
#define FALSE 0

typedef struct EdgeNode EdgeNode;
typedef struct EdgeNode * PEdgeNode;
typedef struct EdgeNode * EdgeList;
typedef float AdjType;

struct EdgeNode {
    int endvex;                
    AdjType weight;
    PEdgeNode nextedge;        
};                                            

typedef struct {
                    
    EdgeList edgelist;         
} VexNode;                            

typedef struct {
    int n;                            
    VexNode vexs[MAXVEX];
} GraphList;


typedef struct {
       
    int vexsno[MAXVEX];               
} Topo;




void findInDegree(GraphList* g, int *inDegree) 
{
    int i; 
    PEdgeNode p;        

    for (i = 0; i < g->n; i++)
        inDegree[i] = 0;

for (i = 0; i < g->n; i++) 
{
        p = g->vexs[i].edgelist;
        while(p) 
{
            inDegree[p->endvex]++; 
            p = p->nextedge; 
        }
    }
}

void makeNewAOV(EdgeList p, int* indegree, int* top) 
{
    int k;
while (p) 
{                       
        k = p->endvex; 
        indegree[k]--;
        if (indegree[k] == 0) 
{         
            indegree[k] = *top;
            *top = k; 
        }
        p = p->nextedge;
    }
}


int topoSort(GraphList * paov, Topo * ptopo) 
{
    EdgeList p;
    int i, j, nodeno = 0, top = -1;
    int indegree[MAXVEX];

    findInDegree(paov, indegree);    
    for (i = 0; i < paov->n; i++)
        if (indegree[i] == 0) 
{         
            indegree[i] = top; top = i;
        }

while (top != -1) 
{                
        j = top;
        top = indegree[top];               
         
        ptopo->vexsno[nodeno++] = j;
        p = paov->vexs[j].edgelist;    
                
        makeNewAOV(p, indegree, &top);
    }

if (nodeno < paov->n) 
{       
        printf("The aov network has a cyclen");
        return FALSE;
    }
    
    return TRUE;
}

void insert(GraphList* p,int a,int b,float weight)
{
    EdgeList pp;
    PEdgeNode temp;
    temp = (PEdgeNode)malloc(sizeof(EdgeNode));
    temp->endvex = b;
    temp->nextedge = NULL;
    temp->weight = weight;
    pp = p->vexs[a].edgelist;
    if (pp == NULL)
        p->vexs[a].edgelist = temp;
else 
{
        while (pp->nextedge != NULL)
            pp = pp->nextedge;
        pp->nextedge = temp;
    }
}
        

GraphList* makeList()
{
    GraphList* p;
    int i;
    p = (GraphList*)malloc(sizeof(GraphList));
    p->n = 9;
    for (i = 0; i < p->n; i++)
        p->vexs[i].edgelist = NULL;
    insert(p,0,1,6);
    insert(p,0,2,4);
    insert(p,0,3,5);
    insert(p,1,4,1);
    insert(p,2,4,1);
    insert(p,3,5,2);
    insert(p,4,6,9);
    insert(p,4,7,7);
    insert(p,5,7,4);
    insert(p,6,8,2);
    insert(p,7,8,4);
    return p;
}

int CriticalPath(GraphList * paoe);


int main()
{
    GraphList* p;
    
    p = makeList();
    
    if (CriticalPath(p) == FALSE)
        printf("There is no critical path!n");
    return 0;
}



#define MAXEDGE 100 


void countee(GraphList* paoe,Topo* ptopo, AdjType* ee) 
{
    int i, j, k;
    EdgeList p;

    for (i = 0; i < paoe->n; i++) ee[i] = 0;
for (k = 0; k < paoe->n; k++) 
{       
        i = ptopo->vexsno[k];
        p = paoe->vexs[i].edgelist;
        while (p != NULL) 
{
            j = p->endvex;
            if (ee[i] + p->weight > ee[j])
                ee[j] = ee[i] + p->weight;
            p = p->nextedge;
        }
    }
}



void countle(GraphList * paoe,Topo* ptopo, AdjType* ee, AdjType* le) 
{
    int i, j, k;
    EdgeList p;
    for (i = 0; i < paoe->n; i++)         
        le[i] = ee[paoe->n - 1];
for (k = paoe->n - 2; k >= 0; k--) 
{
        i = ptopo->vexsno[k];
        p = paoe->vexs[i].edgelist;
        while (p != NULL) 
{
            j = p->endvex;
            if( le[j] - p->weight < le[i] )
                le[i] = le[j] - p->weight;
            p = p->nextedge;
        }
    }
}


void counte_l(GraphList * paoe,Topo* ptopo, AdjType* ee,
                AdjType* le, AdjType* e, AdjType* l) 
{
    int i, j, k = 0;
    EdgeList p;
    
for (i = 0; i < paoe->n; i++) 
{
        p = paoe->vexs[i].edgelist;
        while (p != NULL) 
{
            j = p->endvex;
            e[k] = ee[i];
            l[k] = le[j] - p->weight;
            if (e[k] == l[k])
                printf(", ", i, j);
            k++;
            p = p->nextedge;
        }
    }
}


int CriticalPath(GraphList * paoe) 
{
    AdjType ee[MAXVEX], le[MAXVEX], l[MAXEDGE], e[MAXEDGE];
    Topo topo;
    if (topoSort(paoe, &topo) == FALSE)               
        return FALSE;
    countee(paoe, &topo, ee); 
    countle(paoe, &topo, ee, le);
    counte_l(paoe, &topo, ee, le, e, l);
    printf("n");
    return TRUE;
}