1.學習總結
1.1思維導圖
1.2圖結構學習體會
- 深度周遊算法
- 從圖中某個初始頂點v出發，首先通路初始頂點v,然後選擇一個與頂點v相鄰且沒被通路過的頂點w為初始頂點，再從w出發進行深度優先周遊，直到圖中與目前頂點v鄰接的所有頂點都被通路過為止。
- 廣度周遊算法
- 首先通路初始頂點v,接着通路頂點v的所有未被通路的鄰接點，然後按照次序，通路每一個頂點的所有未被通路的鄰接點，以此類推，直到圖中所有和初始頂點v有路徑相通的頂點都被通路過為止。
- Prim和Kruscal算法
- 普裡姆算法： 1).輸入：一個權重連通圖，其中頂點集合為V，邊集合為E； 2).初始化：Vnew = {x}，其中x為集合V中的任一節點（起始點），Enew = {},為空； 3).重複下列操作，直到Vnew = V： a.在集合E中選取權值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，并且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）； b.将v加入集合Vnew中，将<u, v>邊加入集合Enew中； 4).輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。
- 克魯斯卡爾算法：
- 克魯斯卡爾算法是一種用來尋找最小生成樹的算法。在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構成回路，則放棄，選取次小邊。
- Dijkstra算法
- 是從一個頂點到其餘各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪傑斯特拉算法主要特點是以起始點為中心向外層層擴充，直到擴充到終點為止。
- 拓撲排序算法
- 對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是将G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u線上性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列
2.PTA實驗作業
1.圖着色問題
1.1設計思路：
當t=1時，對目前第t個頂點開始着色：若t>n，則已求得一個解，輸出着色方案即可。否則，依次對頂點t着色1-m， 若t與所有其它相鄰頂點無顔色沖突，則繼續為下一頂點着色；否則，回溯，測試下一顔色
1.2 代碼截圖
1.3 送出清單
2.排座位
2.1設計思路：
此題用并查集算法較為簡單。
2.2代碼截圖
2.3送出清單
3.公路村村通
代碼截圖
3.本周最後排名
總分:80
4.閱讀代碼：
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
int indegree;
struct Node *next;
};
//初始化鄰接表
struct Node* initAdjList(int n) {
struct Node* headers;
headers = (struct Node*)malloc(sizeof(struct Node) * n);
int i = 0;
for(i; i < n; i++) {
headers[i].next = NULL;
headers[i].value = 0;
headers[i].indegree = 0;
}
return headers;
}
void addAdj(struct Node* header, int m, int n) {
struct Node* p = &header[m];
p->value++;
while(p->next != NULL)
p = p->next;
p->next = (struct Node*)malloc(sizeof(struct Node));
p->next->value = n;
p->next->next = NULL;
}
//列印鄰接表
void printAdjList(struct Node* header, int n) {
int i = 0;
for(i; i < n; i++) {
struct Node* p = &header[i];
printf("Number of %d' adj : %d\t", i, p->value);
while(p->next!= NULL) {
printf("%d --->%d\t", i, p->next->value);
p = p->next;
}
printf("\n");
}
}
//拓撲排序
int* topSort(struct Node* headers, int n) {
int* zeroStack = (int*)malloc(sizeof(int) * n);
int* result = (int*)malloc(sizeof(int) * n);
int count = 0;
int pIndex = -1;
int i = 0;
while(i < n) {
struct Node* p = &headers[i];
//入度為0，直接進棧
if(p->indegree == 0)
zeroStack[++pIndex] = i;
i++;
}
while(1) {
//從top裡面出棧一個Node Index
int zeroIndex = zeroStack[pIndex--];
result[count++] = zeroIndex;
struct Node* zeroNode = &headers[zeroIndex];
//将zeroNode的連接配接點，對應的頭結點的值減一
while(zeroNode->next != NULL) {
struct Node* q = &headers[zeroNode->next->value];
if(--q->indegree == 0)
zeroStack[++pIndex] = zeroNode->next->value;
zeroNode = zeroNode->next;
}
//棧空
if(pIndex < 0)
break;
}
return result;
}
int main()
{
int a[7][7] = { {0,1,1,1,0,0,0},
{0,0,0,0,1,1,0},
{0,0,0,0,0,0,1},
{0,0,1,0,0,1,1},
{0,0,0,1,0,0,1},
{0,0,0,0,0,0,0},
{0,0,0,0,0,1,0}
};
int n = 7;
struct Node* headers = initAdjList(n);
int i = 0;
int j = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++) {
if(a[i][j] == 1)
addAdj(headers, i, j);
}
//生成各節點indegree
for(i = 0; i < n; i++) {
struct Node* p = &headers[i];
while(p->next != NULL) {
headers[p->next->value].indegree++;
p = p->next;
}
}
int* q = topSort(headers, n);
printAdjList(headers, n);
for(i = 0; i < n; i++) {
printf("%d \n", *q++ + 1);
}
return 0;
}
轉載于:https://www.cnblogs.com/leonsehun/p/9195080.html