鄰接矩陣銷毀圖的演算法

① 求一個數組的鄰接矩陣的演算法描述

1.先求出第1行和第2行中最大的數6
這個數就是頂點的個數
鄰接矩陣即為6階方陣
2.
構造6階矩陣,
元素全部賦值0
3.
循環(i=1,...,9)讀取每條邊的起點和終點，比如第一條邊的起點和終點:
1，3
將矩陣第1行第3列的元素賦值為
1.
4.
循環完畢退出.
可顯示看看鄰接矩陣

② 鄰接矩陣和鄰接表刪除有向圖或無向圖的一條邊的演算法。。。急用。。盡量簡單些就好。。。。

#include <iostream>

using namespace std;

const int DoctorCount = 7;

struct Constraint
{
int doc1;
int relation;
int doc2;
int days;
};

bool check(int *doctors, Constraint *constrains, int n, int index)
{
if (index < 0 || index > DoctorCount || doctors[index] == -1)
{
return false;
}

for (int i = 0; i <= index; i++)
{
for (int j = 0; j < index; j++)
{
if (doctors[i] == doctors[j] && i != j)
{
return false;
}
}
}

for (int i = 0; i < n; i++)
{
Constraint *p = &constrains[i];
if (p->doc1 <= index && p->doc2 <= index)
{
if (p->relation == 1)
{
if (doctors[p->doc2] - doctors[p->doc1] != p->days)
{
return false;
}
}
else
{
if (doctors[p->doc1] - doctors[p->doc2] != p->days)
{
return false;
}
}
}
}
return true;
}

bool slove(int *doctors, Constraint *constrains, int n, int index)
{
if (index >= DoctorCount)
{
return true;
}

if (doctors[index] != -1)
{
return slove(doctors, constrains, n, index + 1);
}

for (int i = 1; i <= 7; i++)
{
doctors[index] = i;
if (check(doctors, constrains, n, index))
{
if (slove(doctors, constrains, n, index + 1))
{
return true;
}
}
doctors[index] = -1;
}

return false;
}

int main( )
{
int n;
cin>>n;

int doctors[7];
for (int i = 0; i < 7; i++)
{
doctors[i] = -1;
}
Constraint *constraints;
constraints = new Constraint[n];

int constraints_count = 0;
for (int i = 0; i < n; i++)
{
char tmp[20];
cin>>tmp;
if (tmp[1] == '=')
{
doctors[tmp[0] - 'A'] = tmp[2] - '0';
}
else
{
constraints[i].doc1 = tmp[0] - 'A';
constraints[i].relation = tmp[1] == '>' ? 1 : 0;
constraints[i].doc2 = tmp[2] - 'A';
constraints[i].days = tmp[3] - '0';
constraints_count++;
}
}

slove(doctors, constraints, constraints_count, 0);
for (int i = 0; i < 7; i++)
{
cout<<(char)(i + 'A')<<" "<<doctors[i]<<endl;
}
delete []constraints;
return 0;
}

③ 存儲結構為鄰接矩陣，怎麼編寫無向圖添加、刪除一個頂點，添加、刪除一條邊的演算法

1. 鄰接表，存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。

2. 對於無向圖來說，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。

3. /* MGraph.cc: 圖的鄰接矩陣存儲表示和實現 */
   

4. /* 包含圖類型Graph定義；創建圖；深度優先遍歷；廣度優先遍歷 */
   

5. /* 用到引用型參數，在TC下無法通過編譯，VC等C++編譯器可通過 */
   

6. #include <stdio.h>
   

7. #include <string.h>
   

8. #include <limits.h> //含INT_MAX
   

9. #define VType char //頂點值類型
   

10. #define EType int //邊權值類型
    

11. #define MAXVNUM 50 //最大頂點個數
    

12. #define DIGRAPH 0 //有向圖(網)
    

13. #define UNDIGRAPH 1 //無向圖(網)
    

14. #define INVALID INT_MAX //無效權值(最大整數表示無窮大)
    

15. #define EMPTY -1 //"空"頂點序號
    

④ 求解鄰接表建圖的演算法

這個都好說，不過你要用鄰借表保存圖，還是已知鄰接表列印圖？這兩個是不同的演算法。