本文共 2905 字，大约阅读时间需要 9 分钟。

1.邻接矩阵

2.邻接表和逆接表

typedef struct ArcNode{
       int adjV;    struct ArcNode* next;}ArcNode;typedef struct{
       int data;    ArcNode* first;}VNode;typedef struct{
       VNode adjList[maxSize];    int n,e;}AGraph;

3.十字链表

4.邻接多重表

5.DFS(深度优先遍历)

void DFS(int v,AGraph *G){
       visit[v]=1;    cout<
   
    <
    
     adjList[v].first;    while(q!=NULL)    {
           if(visit[q->adjV]==0)            DFS(q->adjV,G);        q=q->next;    }}
    
   

6.BFS(广度优先遍历)

void BFS(AGraph *G,int v){
       ArcNode *p;    int que[maxSize],front=0,rear=0;    int j;    cout<
   
    <
    
     adjList[j].first;        while(p!=NULL)        {
               if(visit[p->adjV]==0)            {
                   cout<
     
      adjV<
      
       adjV]=1;                rear=(rear+1)%maxSize;                que[rear]=p->adjV;            }            p=p->next;        }    }}
      
     
    
   

7.prim算法

void Prim(int n,float MGraph[][maxSize],int v0,float &sum){
       int lowCost[n],vSet[n];    int v,k,min;    for(int i=0;i

8.kruskal算法

int v[maxSize];int getRoot(int p){
       while(p!=v[p])        p=v[p];    return p;}void selectionSort1(Road arr[],int n){
       for(int i=0;i

9.Dijkstra算法

void Dijkstra(int n,float MGrph[][maxSize],int v0,int dist[],int path[]){
       int set[maxSize];    int min,v;    for(int i=0;i

10.Floyd算法

void Floyd(int n,float MGraph[][maxSize],int path[][maxSize]){
       int i,j,v;    int A[n][n];    for(i=0;i
   
    A[i][v]+A[v][j])                {
                       A[i][j]=A[i][v]+A[v][j];                    path[i][j]=v;                }}void printPath(int u,int v,int path[][maxSize]){
       if(path[u][v]==-1)        cout<<1<
   

11.拓扑排序

typedef struct ArcNode{
       int adjV;    struct ArcNode* next;}ArcNode;typedef struct {
       int data;    int count;    ArcNode* first;}VNode;typedef struct{
       VNode adjList[maxSize];    int n,e;}AGraph;int TopSort(AGraph *G){
       int i,j,n=0;    int stack[maxSize],top=-1;    ArcNode *p;    for(i=0;i
   
    n;++i)    {
           if(G->adjList[i].count==0)            stack[++top]=i;    }    while(top!=-1)    {
           i=stack[top--];        ++n;        cout<
    <
     
      adjList[i].first;        while(p!=NULL)        {
               j=p->adjV;            --(G->adjList[j].count);            if(G->adjList[j].count==0)                stack[++top]=j;            p=p->next;        }    }    if(n==G->n)        return 1;    else           return 0;}
     
   

12.逆拓扑排序

typedef struct ArcNode{
       int adjV;    struct ArcNode* next;}ArcNode;typedef struct {
       int data;    int count;    ArcNode* first;}VNode;typedef struct{
       VNode adjList[maxSize];    int n,e;}AGraph;void endSort(int v,AGraph *G){
       visit[v]=1;    ArcNode* q=G->adjList[v].first;    while(q!=NULL)    {
           if(visit[q->adjV]==0)            DFS(q->adjV,G);        q=q->next;    }    cout<
   
    <
   

13.关键路径

转载地址：http://vfezi.baihongyu.com/