一、基本概念

        深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:

        首先访问图中某一起始顶点 V，然后由 V 出发，访问与 V 邻接且未被访问的任一顶点 W₁ ，再访问与 W₁  邻接且未被访问的任一顶点…...重复上述过程，当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

二、代码实现

         由于图的储存结构不同，DFS的实现代码不同，但实际的思想依旧是“深度优先”。但是在实际的DFS的实现中，存在递归和非递归(栈)的两大类实现方法。

① 递归形式

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct Graph{
    int data;
    int edge[100][100];
    int numVerties,numEdges;
}Graph;

void initGraph(Graph *G,int n){
    G->numVerties = n;
    G->numEdges = 0;
    for(int i=0;i<G->numVerties;i++){
        for(int k=0;k<G->numVerties;k++){
            G->edge[i][k] = 0;
        }
    }
}

void addEdge(Graph *G,int u,int v,int val){
    G->edge[u][v] = val;
    G->edge[v][u] = val;
    G->numEdges++;
}

void DijkstraUtil(Graph *G,int start,int dist[],bool visited[]){
    int u=-1;
    int min = 0;
    dist[start] = 0;
    for (int k = 0; k < G->numVerties-1; k++) {
        u=-1;
        min = 99999;
        for (int i = 0; i < G->numVerties; i++) {
            if (dist[i] < min && !visited[i]) {
                u = i;
                min = dist[i];
            }
        }
        if (u == -1) break;
        visited[u] = true;
        for (int j = 0; j < G->numVerties; j++) {
            if (!visited[j] && G->edge[u][j] > 0 && dist[u] + G->edge[u][j] < dist[j]) {
                dist[j] = dist[u] + G->edge[u][j];
            }
        }
    }

    /*int pos,max;

    for (int i = 0; i < G->numVerties-1; i++) {
        max = dist[i];
        pos = i;
        for (int j = i+1; j < 10; j++) {
            if (max < dist[j]) {
                max = dist[j];
                pos = j;
            }
        }

        dist[pos] = dist[i];
        dist[i] = max;
    }*/

    for(int i=0;i<G->numVerties;i++){
        printf("%d ",dist[i]);
    }

}

void Dijkstra(Graph *G,int start){
    int dist[G->numVerties];
    bool *visited = (bool *)malloc(G->numVerties * sizeof(bool));
    for (int i = 0; i < G->numVerties; i++) {
        dist[i] = 99999;
        visited[i] = false;
    }

    DijkstraUtil(G,start,dist,visited);

    free(visited);
}
int main(){
    system("chcp 65001");
    int n;
    scanf("%d",&n);

    Graph G;
    initGraph(&G,n);

    int val;

    for(int k=0;k<n;k++){
        for(int j=0;j<n;j++){
            scanf("%d",&val);
            addEdge(&G,k,j,val);
        }
    }

    Dijkstra(&G,0);

    return 0;
}