1. 鄰接矩陣和鄰接表刪除有向圖或無向圖的一條邊的演算法。。。急用。。盡量簡單些就好。。。。
#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;
}
2. 存儲結構為鄰接矩陣，怎麼編寫無向圖添加、刪除一個頂點，添加、刪除一條邊的演算法
鄰接表，存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。
對於無向圖來說，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。
/* MGraph.cc: 圖的鄰接矩陣存儲表示和實現 */
/* 包含圖類型Graph定義；創建圖；深度優先遍歷；廣度優先遍歷 */
/* 用到引用型參數，在TC下無法通過編譯，VC等C++編譯器可通過 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //頂點值類型
#define EType int //邊權值類型
#define MAXVNUM 50 //最大頂點個數
#define DIGRAPH 0 //有向圖(網)
#define UNDIGRAPH 1 //無向圖(網)
#define INVALID INT_MAX //無效權值(最大整數表示無窮大)
#define EMPTY -1 //"空"頂點序號
3. 求一個數組的鄰接矩陣的演算法描述
1.先求出第1行和第2行中最大的數6
這個數就是頂點的個數
鄰接矩陣即為6階方陣
2.
構造6階矩陣,
元素全部賦值0
3.
循環(i=1,...,9)讀取每條邊的起點和終點，比如第一條邊的起點和終點:
1，3
將矩陣第1行第3列的元素賦值為
1.
4.
循環完畢退出.
可顯示看看鄰接矩陣
4. 用一個鄰接矩陣存儲有向圖g最多有多少條弧
矩陣的元素數目為N^2 也就是答案B 非零元素數目為E 也就是答案C
5. 無向圖添加，刪除一個頂點，添加，刪除一條邊的演算法，存儲結構為鄰接矩陣，寫得好的再加分！
/* MGraph.cc: 圖的鄰接矩陣存儲表示和實現 */
/* 包含圖類型Graph定義；創建圖；深度優先遍歷；廣度優先遍歷 */
/* 用到引用型參數，在TC下無法通過編譯，VC等C++編譯器可通過 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //頂點值類型
#define EType int //邊權值類型
#define MAXVNUM 50 //最大頂點個數
#define DIGRAPH 0 //有向圖(網)
#define UNDIGRAPH 1 //無向圖(網)
#define INVALID INT_MAX //無效權值(最大整數表示無窮大)
#define EMPTY -1 //"空"頂點序號
//定義鄰接矩陣表示的圖類型Graph:
typedef struct
{
VType v[MAXVNUM]; //頂點序列(頂點編號從0開始)
EType w[MAXVNUM][MAXVNUM]; //鄰接矩陣
int vn, en; //頂點數,邊數
int kind; //圖的種類：=DIGRAPH表示有向圖(網)，=UNDIGRAPH表示無向圖(網)
}Graph;
int visited[MAXVNUM]; //訪問標志數組(=1已訪問，=0未訪問)。遍歷時用到的全局量。
/* 創建圖G
參數Vex是存放頂點序列的數組
參數VVW是整數數組，以的形式依次存放各邊的起止點序號(Vi,Vj)和權(Wij)，-1是數據結束標志
參數kind=DIGRAPH表示有向圖(網)，=UNDIGRAPH表示無向圖(網)
*/
void CreateGraph(Graph &G, VType *Vex, int VVW[], int kind)
{
int i, j, p, n, w;
n = strlen(Vex);
G.vn = n; //頂點數
G.kind = kind; //圖的種類
//置頂點序列:
for (i = 0; i < n; i++)
G.v[i] = Vex[i];
//初始化鄰接矩陣:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
G.w[i][j] = INVALID;
//構造鄰接矩陣:
p = 0; //VVW數組元素「指針」
n = 0; //邊計數器
while (VVW[p] != -1)
{//只要p未到結束位置便繼續:
i = VVW[p]; //邊的起點序號
j = VVW[p + 1]; //邊的終點序號
w = VVW[p + 2]; //邊的權
G.w[i][j] = w; //置鄰接矩陣的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是無向圖(網),
G.w[j][i] = G.w[i][j]; //則置(i,j)的對稱位置(j,i)
n++; //邊計數器加1
p += 3; //p指向下一組(Vi,Vj,Wij)
}//end while
G.en = n; //邊數
}//CreateGraph
/* 返回G中頂點i的一個未曾訪問過的鄰接點(序號) */
int NextAdjVex(Graph &G, int i)
{
int j, a;
a = EMPTY; //鄰接點序號初始為"空"
//在鄰接矩陣的第v行找有效元素：
for (j = 0; j < G.vn; j++)
{
if (G.w[i][j] == INVALID) //若當前元素是無效元素,
continue; //則繼續找。
if (!visited[j])
{//若當前有效元素未曾訪問過,則作為鄰接點a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex
/* 訪問頂點i */
void visit(Graph &G, int i)
{
printf("%c", G.v[i]);
}//visit
/* 從第i個頂點出發深度優先遍歷連通圖G */
/* 調用DFS前可能需初始化數組visited[] */
void DFS(Graph &G, int i)
{int a;
visit(G, i); //訪問i頂點
visited[i] = 1; //標注i頂點已訪問
a = NextAdjVex(G, i); //找出一個i的鄰接點a
while (a != EMPTY)
{//只要a存在便繼續:
if (visited[a] == 0) //若a未曾訪問,
DFS(G, a); //則從a出發繼續進行深度優先遍歷。
a = NextAdjVex(G, i); //找出i的下一個鄰接點a
}//end while
}//DFS
/* 從第i個頂點出發深度優先遍歷圖G */
void DFSTrav(Graph &G, int i)
{int k;
//初始化各頂點的訪問標志為0(未曾訪問):
for (k = 0; k < G.vn; k++)
visited[k] = 0;
DFS(G, i); //從i出發遍歷
//若G非連通圖，執行一次DFS無法遍歷所有頂點，還需用如下for對尚未訪問的頂點DFS。
//若G是連通圖，執行一次DFS就已遍歷所有頂點，此時如下for什麼也不做，因所有visited=1。
for (k = 0; k < G.vn; k++)
if (!visited[k]) DFS(G, k); //對尚未訪問的頂點DFS
}//DFSTrav
//顯示圖的鄰接矩陣
void ShowM(Graph &G)
{
int row, col, n;
n = G.vn; //頂點數
//以表格形式輸出數組：
//輸出表頭：
printf(" ");
for(col = 0; col < n; col++)
printf("%3d",col);
printf("\n");
printf("---+");
for(col = 0; col < n; col++)
printf("---");
printf("\n");
//輸出表體(矩陣元素)：
for(row = 0; row < n; row++)
{
printf("%3d|", row);
for(col = 0; col < n; col++)
{
if (G.w[row][col] == INVALID)
printf("%3c", '*');
else
printf("%3d", G.w[row][col]);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM
你的串號我已經記下，採納後我會幫你製作
6. 用鄰接矩陣的 輸出 矩陣 弧
如下，c語言寫的~~
#define MAXNUM 30
#define INFINITY 10000
#define FALSE 0
#define TRUE 1
#define BACK -1
#include "stdio.h"
#include <stdio.h>
#include "malloc.h"
//定義圖的構造體
typedef struct{
char vexs[MAXNUM];
int edges[MAXNUM][MAXNUM];
int n,e;
}Mgraph;
//圖的輸入方法
void CreateGraph(Mgraph *g){
int i,j,k,w;
char ch;
printf("請輸入結點數與弧數，如：3,2：");
scanf("%d,%d",&(g->n),&(g->e));
//初始化權值
for(i=0;i<g->n;i++){
for(j=0;j<g->n;j++){
if(i==j){
g->edges[i][j]=0;
}else{
g->edges[i][j]=INFINITY;
}
}
}
//獲取權值
printf("\n為方便演示，結點內容默認為結點序號，無需輸入。\n\n下面請輸入弧及權值，例如：若點0到1有弧可達，且權值為10，則輸入:0,1,10。注意：輸入時不區分弧的順序。\n");
for(k=0;k<g->e;k++){
printf("\t請輸入第%d個弧及權值：",k+1);
scanf("%d,%d,%d",&i,&j,&w);
g->edges[i][j]=w;
}
//輸出鄰接矩陣
printf("\n鄰接矩陣：\n",k);
for(i=0;i<g->n;i++){
printf("\t");
for(j=0;j<g->n;j++){
if(g->edges[i][j]>=INFINITY){
printf("∞\t");
}else{
printf("%d\t",g->edges[i][j]);
}
}
printf("\n");
}
}
void ShortPath(Mgraph *g,int v0){
/*定義多個變數與數組，其中R數組為記錄路徑的數組，iterator為游標，
D為距離數組，final數組記錄是否已取到最短路徑
*/
int i,j,v,w,min;
int R[MAXNUM][MAXNUM];
int iterator[MAXNUM];
int D[MAXNUM];
int final[MAXNUM];
//初始化游標為零
for(i=0;i<MAXNUM;i++){
iterator[i]=0;
}
//初始化final為FALSE，D為弧的權值
for(v = 0;v < g->n; ++v){
final[v] = FALSE;
D[v] = g->edges[v0][v];
}
//初始化v0的路徑距離為零，設置已獲取最短路徑
D[v0] = 0;
final[v0] = TRUE;
//主循環，獲取其他的最短路徑
for(i = 1;i < g->n; ++i){
min = INFINITY;
//尋找最小的D[w]
for(w = 0;w < g->n; ++w){
if(final[w] != TRUE){
if(D[w]<min){
v=w;
min=D[w];
}
}
}
//將找到的v設置已獲取最短路徑
final[v]=TRUE;
//列印輸出該路徑
if(min!=INFINITY){
printf("\t點%d到點%d的最小路徑值為：%d\t",v0,v,D[v]);
printf("路徑為：%d->",v0,v,v0);
for(j=0;j<iterator[v];j++){
printf("%d->",R[v][j]);
}
printf("%d\n",v);
}
//更新D[w]
for(w = 0;w < g->n; ++w){
if((final[w] != TRUE) && (min+g->edges[v][w] < D[w])){
//更新路徑
iterator[w]=iterator[v];
for(j=0;j<iterator[v];j++){
R[w][j]=R[v][j];
}
R[w][iterator[w]]=v;iterator[w]++;
D[w] = min + g->edges[v][w];
}
}
}
//若final始終為FALSE，則不可達
for(w = 0;w<g->n; ++w){
if(final[w] != TRUE){
printf("\t點%d到點%d不可達\n",v0,w);
}
}
}
//主方法
void main(){
Mgraph * g;
int i=0;
g=(Mgraph *)malloc(sizeof(Mgraph));
printf("該程序實現了Dijkstra演算法，支持路徑顯示，請按提示輸入數據：\n\n");
CreateGraph(g);
printf("\n最小路徑判斷(以0點為起點)：\n");
ShortPath(g,0);
getch();
}
7. 用鄰接矩陣表示一個圖時 1、 輸出一個圖的邊數，以及兩端頂點 2、 增加、刪除一條邊（輸出新圖對應的鄰接
/*用鄰接矩陣實現圖*/
#include <stdio.h>
#include<stdlib.h>
#define WItem int
typedef struct graph *Graph;
struct graph
{
WItem NoEdge; /*無邊標記*/
int n; /*頂點數*/
int e; /*邊數*/
WItem **a; /*鄰接矩陣*/
}AWDgraph;
Graph Graphinit(int n,WItem noEdge) /*創建圖*/
{
int i,j;
Graph G=(struct graph *)malloc(sizeof (*G));
G->n=n;
G->e=0;
G->NoEdge=noEdge;
a=(WItem**)malloc(sizeof(WItem)*n*n);
for(i=0;i<G->n+1;i++)
{
for (j=0;j<G->n+1;j++)
G->a[i][j]=G->NoEdge;
}
return G;
}
int GraphEdges(Graph(G)) /*輸出邊數*/
{return G->e;}
int GraphVertices(Graph(G)) /*輸出頂點數*/
{return G->n;}
int GraphExist(int i,int j,Graph G) /*判斷邊是否存在*/
{
if(i<1||j<1||i>G->n||G->a[i][j]==G->NoEdge) return 0;
return 1;
}
void GraphAdd(int i,int j,WItem w,Graph G) /*加入一條邊*/
{
if(i<1||j<1||i>G->n||G->n||i==j||G->a[i][j]!=G->NoEdge)
printf("Bad input");
G->a[i][j]=w;
G->e++;
}
void GraphDelete(int i,int j,Graph G) /*刪除一條邊*/
{
if(i<1||j<1||i>G->n||j>G->n||G->a[i][j]==G->NoEdge)
printf("Bad input");
G->a[i][j]=G->NoEdge;
G->e--;
}
int OutDegree(int i,Graph G) /*計算出度*/
{
int j,sum=0;
if(i<1||i>G->n) printf("Bad input");
for(j=1;j<=G->n;j++)
if(G->a[i][j]!=G->NoEdge) sum++;
return sum;
}
int InDegree(int i,Graph G) /*計算入度*/
{
int j,sum=0;
if(i<1||i>G->n) printf("Bad input");
for(j=1;j<=G->n;j++)
if(G->a[i][j]!=G->NoEdge) sum++;
return sum;
}
/*輸出表*/
void GraphOut(Graph G)
{
int i,j;
for(i=1;i<=G->n;i++)
{
for(j=1;j<=G->n;j++)
{printf("%d",G->a[i][j]);
printf("\n");}
}
}
void main() /*測試該圖類型數據結構演算法*/
{
int p,q,n,e,i,j,w,noEdge;
Graph G;
noEdge=0;
printf("幾個結點\n");
scanf("%d",&n);
Graph Graphinit(int n,WItem noEdge);
printf("加入幾條邊\n");
scanf("%d",&e);
for(p=0;p<e;p++)
{
printf("邊的權值為多少？");
scanf("%d",&w);
printf("在哪加邊？");
scanf("%d,%d",&i,&j);
void GraphAdd(int i,int j, int w,Graph G);
}
for(i=1;i<=G->n;i++)
{
for(j=1;j<=G->n;j++)
printf("%d",G->a[i][j]);
}
}
8. 怎麼寫 如果1個圖採用鄰接矩陣表示，則實現求圖邊或弧個數的演算法
gi jerr
9. 把鄰接矩陣轉換成鄰接表的演算法
#include <stdio.h>
#include <malloc.h>
#define INF 32767 //INF表示∞
typedef int InfoType;
typedef int Vertex;
//--------------鄰接矩陣存儲表示------------
#define MAXV 20 //最大頂點個數
#define INF 32767 //INF表示∞
//以下定義鄰接矩陣類型
typedef struct{
int nunber; //頂點編號
InfoType info; //頂點其他信息
} VertexType; //頂點類型
typedef struct { //圖的定義
int edges[MAXV][MAXV]; //鄰接矩陣
int n,e; //頂點數，弧數
VertexType vexs[MAXV]; //存放頂點信息
} MGraph; //圖的鄰接矩陣類型
//-------------------鄰接表存儲表示----------
//以下定義鄰接表類型
typedef struct ANode{ //弧的結點結構類型
int adjvex; //該弧的終點位置
InfoType info; //該弧的相關信息,這里用於存放權值
struct ANode *nextarc; //指向下一條弧的指針
} ArcNode;
typedef struct Vnode { //鄰接表頭結點的類型
Vertex data; //頂點信息
int count; //存放頂點入度,只在拓撲排序中用
ArcNode *firstarc; //指向第一條弧
} VNode;
typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型
typedef struct{
AdjList adjlist; //鄰接表
int n,e; //圖中頂點數n和邊數e
} ALGraph; //圖的鄰接表類型
//將鄰接矩陣g轉換成鄰接表G
void MatToList(MGraph g,ALGraph *&G)
{
int i,j,n=g.n; //n為頂點數
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
// for (i=0;i<n;i++) //給鄰接表中所有頭結點的指針域置初值
// G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //檢查鄰接矩陣中每個元素
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0) //鄰接矩陣的當前元素不為0
{
p=(ArcNode *)malloc(sizeof(ArcNode)); //創建一個結點*p
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc; //將*p鏈到鏈表後
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
void ListToMat(ALGraph *G,MGraph &g)
//將鄰接表G轉換成鄰接矩陣g
{
int i,n=G->n;
ArcNode *p;
for (i=0;i<n;i++)
{
p=G->adjlist[i].firstarc;
while (p!=NULL)
{
g.edges[i][p->adjvex]=p->info;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
void DispMat(MGraph g)
//輸出鄰接矩陣g
{
int i,j;
for (i=0;i<g.n;i++)
{
for (j=0;j<g.n;j++)
if (g.edges[i][j]==INF)
printf("%3s","∞");
else
printf("%3d",g.edges[i][j]);
printf("\n");
}
}
void DispAdj(ALGraph *G)
//輸出鄰接表G
{
int i;
ArcNode *p;
for (i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
printf("%3d: ",i);
while (p!=NULL)
{
printf("%3d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
//以下主函數用作調試
void main()
{
int i,j;
MGraph g,g1;
ALGraph *G;
int A[6][6]={
{0,5,0,7,0,0},
{0,0,4,0,0,0},
{8,0,0,0,0,9},
{0,0,5,0,0,6},
{0,0,0,5,0,0},
{3,0,0,0,1,0}};
g.n=6;g.e=10;
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
printf("\n");
printf(" 有向圖G的鄰接矩陣:\n");
DispMat(g);
G=(ALGraph *)malloc(sizeof(ALGraph));
printf(" 圖G的鄰接矩陣轉換成鄰接表:\n");
MatToList(g,G);
DispAdj(G);
printf(" 圖G的鄰接表轉換成鄰接鄰陣:\n");
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
g1.edges[i][j]=0;
ListToMat(G,g1);
DispMat(g1);
printf("\n");
}
10. 有向圖G的鄰接矩陣為A，如果<Vi,Vj>是圖中的一條弧，則A[i][j]的值為_______。
帶權圖：邊<Vi，Vj>的權
無權圖：1