Graph

BFS And DFS

The two common way to traversal Graph.
The difference between the two ways is the sequence,

---

• BFS
  The BFS is a little bit like the level order of the tree traversal, it starts from a head node(1), and then traversal all the node(2) directly connected to the head node, next step is to keep traversal the node connects to node type(2), and until the end.

void BFS(ALGraph G, int v) {
    cout << G.vertices[v].data << " ";
    visited[v] = TRUE;
    queue<int> Q;
    Q.push(v);
    while (!Q.empty()) {
        v = Q.front();
            Q.pop(); 
            cout << G.vertices[v].data << " ";
            for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
                if (!visited[w]) {
                    visited[w] = TRUE;
                    Q.push(w);
                }
            }
    }
}

• DFS
  In this way, First, we start from the head node(1) and then select one node connected to head node(2), next keep selecting a node connected to node type(2), til the end like node(n).Then traversal back to the last node(), find if there is another node in the same level, if have

void DFS(ALGraph G, int v) {
    cout << G.vertices[v].data << " ";
    visited[v] = TRUE;
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w]) {
            visited[w] = TRUE;
            DFS(G, w);
        }
    }
}

---

Graph use

• Prim
  Combine a Graph with node one by one, the algorithm starts with a single node, then there is a min Union each time you just have to add the node with a min weight connect to your original node, it just like combine your graph with node one by one .though, the way we select node all depends on the weight of the node connect edge.
  Pics of the algorithm

First Second Third Fourth Fiveth Sixth
(pictures come from the internet)

• Kruskal
  Combine a Graph with the edge one by one, the algorithm starts with an edge connected with two node, we add an edge
  with the min weigh each time, the added edge don't have to connect with the original edge, just find the min weight edge, till all the node covered in.

• Dijkstra
  Here comes the critical algorithm, first let's have a look at the pic

Graph WordsDescription

Show you the code O(n*n)

void ShortestPath_Dijkstra(int v0, int* final, int*p, int *D)
     {
         int v, w, k, min;
         // 初始化数据
         for (v = 0; v < nVer; ++v)
         {
             final[v] = 0;    // 全部顶点初始化为未知对短路径状态
             D[v] = Edges[v0][v]; //将与V0点有连线的顶点加上权值
             p[v] = 0;    // 初始化路径数组p为0
         }
         D[v0] = 0;    // V0至V0路径为0
         final[v0] = 1;    // final[W]=1表示V0至V0不需要求路径
         // 开始主循环，每次求得V0到某个V顶点的最短路径
         for (v = 1; v < nVer; ++v)
         {
             min = INFINITY;    // 当前所知离V0顶点最近距离
             for (w = 0; w < nVer; ++w) // 寻找离V0最近的顶点
             {
                 if (!final[w] && D[w] < min)
                 {
                     min = D[w]; // w顶点离V0顶点更近
                     k = w;
                 }
             }
             
             final[k] = 1; // 将目前找到的最近的顶点置为1
             for (w = 0; w < nVer; ++w) // 修正当前最短路径距离
             {
                 // 如果经过V顶点的路径比现在这条路径的长度短的话
                 if (!final[w] && (min + Edges[k][w] < D[w]))
                 {
                     // 说明找到了最短的路径，修改D[w] 和 p[w]
                     D[w] = min + Edges[k][w]; // 修改当前路径长度
                     p[w] = k;
                 }
             }
         }
     }
 };

• Floyd
  O(nnn)
• AOV
• AOE
  updating....