数据结构-图

邻接矩阵中的两个最短路径算法，Djkstra，Floyd

#include <stdio.h>
#define maxSize 100
#define INF 999
typedef struct
{
    int no;  //节点编号
}VertexType;

typedef struct
{
    int n,e; //顶点数 边数
    VertexType vex[maxSize];  //顶点
    int edges[maxSize][maxSize];  // 邻接矩阵
}Mgraph;

void Dijkstra (Mgraph * G, int v, int path[], int dist[])
{
    int set[maxSize];
    int min, i , j, u = 0;
    //初始化数组
    for (i = 0; i < G->n; ++i)
    {
        dist[i] = G->edges[v][i];
        set[i] = 0; // 初始化顶点全部不加入在最短路径
        if (dist[i] < INF)
            path[i] = v;  //vi的前一个顶点设置为v
        else
            path[i] = -1;
    }
    path[v] = -1; set[v] = 1;
    
    //关键步骤
    for (i = 0; i < G->n; ++i)
    {
        min = INF;
        for (j = 0; j < G->n; j++)  //将路径最短的加入到其中
            if (set[j] == 0 && dist[j]<min)
            {
                u = j;
                min = dist[j];
            }
        set[u] = 1;   //将u加入顶点中
        
        for (j = 0; j < G->n; ++j)
            if (set[j]==0 && dist[j]  > dist[u]+G->edges[u][j])
            {
                path[j] = u; // 将j的前一个顶点设置为u
                dist[j] = dist[u]  + G->edges[u][j];
            }
    }
    
}

void Floyd (Mgraph g, int path[][maxSize])
{
    int i, j , k;
    int A[maxSize][maxSize];
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
        {
            A[i][j] = g.edges[i][j];
            path[i][j] = -1;
        }
    
    for (k = 0; k < g.n; k++)
        for (i = 0; i < g.n; i++)
          for (j = 0; j < g.n; j++)
          {
              if (A[i][j] < A[i][k] + A[k][j])
              {
                  A[i][j] = A[i][k] + A[k][j];
                  path[i][j] = k;
              }
          }
}

以邻接表存储的两种遍历，深度优先遍历和广度优先遍历，类比于树的前序遍历和层次遍历，但还是有很多差别的

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

typedef struct
{
    int data;
    ArcNode * firstarc;
}VNode;

typedef struct
{
    int n,e; //顶点数，边数
    VNode * adjlist[maxSize];  //邻接表
}AGraph;

void Visit(int v)
{
    
}

void DFS (AGraph * G, int v)  //深度搜索
{
    int visit[maxSize];
    for (int i = 0 ;i  < G->n; ++i) visit[i] = 0;
    
    visit[v] = 1;
    Visit(v);
    ArcNode * p;
    p = G->adjlist[v]->firstarc;
    while (p != NULL)
    {
        if (visit[p->adjvex] == 0)
            DFS(G, p->adjvex);
    }
    p = p->nextarc;
}

void BFS(AGraph G, int v, int visit[maxSize]) //广度搜索
{
    ArcNode * p;
    int j;
    int que[maxSize], front = 0, rear = 0;
    Visit(v);
    visit[v] = 1;   //访问v节点
    rear = (rear + 1) % maxSize;
    que[rear] = v;
    while (rear != front)
    {
        front = (front + 1) % maxSize;
        j = que[front];
        p = G.adjlist[j]->firstarc;
        while (p != NULL)
        {
            if (visit[p->adjvex] == 0)
            {
                Visit(p->adjvex);
                visit[p->adjvex] = 1;
                
                rear = (rear + 1) % maxSize;
                que[rear] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
    
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    return 0;
}